为什么要有索引？为了更快的从数据库中查询到数据，那么有哪些数据结构可以实现索引呢？常见的有哈希表、有序数组和树。
    哈希表实现索引的思路很简单，哈希表就是键值对，所以哈希表只支持通过特定字段来查询数据行，而且只适用于等值查询，使用哈希表实现的索引进行范围查询实际上就是使用了多次等值查询，所以使用哈希索引进行范围查询的速度很慢，为什么是多次等值查询而不是先找到第一个符合要求的数据行，然后依次顺序读取呢？因为哈希表的键在数组中是无序的，所以没办法这么做。使用哈希表实现索引的优点在于添加删除数据行时很方便，直接插入到数组中或者从数组中移除就可以了。
    使用有序数组怎么实现索引呢？使用有序数组同样只能通过特定字段来查询数据行（如果有序数组的维度足够高，那么所有的字段都可以查询数据行了），但是使用有序数组实现的索引在进行等值查询和范围查询时速度都很快，因为有序数组本身是有序的，而且可以使用二分法来快速定位数据行的位置。使用有序数组实现索引的缺点向有序数组中插入删除元素时需要移动后面元素的位置，最坏时间复杂度为o(n)。索引的实现方式是以存储引擎为单位的，所以使用有序数组来实现索引的存储引擎适用于创建静态表以及数据不常被修改的表。什么是静态表？
    使用二叉搜索树怎么实现索引功能的呢？二叉搜索树的结构天生就是用来作为索引的，那么二叉搜索树是怎么定义的？在二叉搜索树中父节点的左子树中所有的节点值都小于父节点的值，父节点的右子树中所有节点的值都大于父节点的值。如果是一个平衡的二叉搜索树，那么到达某个节点的最坏时间复杂度是o(logn)，那么什么样的二叉搜索树是平衡的呢？怎么将一个二叉搜索树保持平衡呢？将一个二叉搜索树保持平衡的最坏时间复杂度又是多少呢？
    既然使用二叉搜索树来实现索引功能，具有查询和更新数据的时间复杂度都是o(logn)的优势，那么在Mysql中存储引擎的索引是用二叉搜索树来实现的吗？并不是，那是用什么来实现的呢？是用多叉搜索树来实现的，多叉搜索树的结构是什么样的？多叉搜索树查询和更新数据的时间复杂度是多少？为什么不用二叉搜索树来实现呢？在Mysql中索引是怎么保存的？可以理解为把内存中的多叉搜索树对象持久化到磁盘上保存吗？在Mysql中，搜索树的不同层位于不同的随机数据块上，所以如果树的层数过高，那么在访问某个数据行时就需要分别访问很多的数据块，随机访问磁盘上的某个数据块是很耗时的一个操作，再加上多个数据块，语句的执行时间就会很长，所以我们要尽可能地减少需要访问的数据块的个数，也就是尽可能地减少搜索树的层高，因此我们使用多叉搜索树来实现这一点。
    那么在Mysql中多叉搜索树中的n一般会设置为多少呢？磁盘是以数据页为单位进行读取和写入的，一个数据页的大小为16K，把多叉搜索树中的节点想成一个对象，在节点对象中有两个属性，第一个属性是占用8个字节的BIGINT类型的字段，第二个属性是占用6个字节的指向子节点的指针，那么一个节点对象就会占用14个字节，16K/14=1170个节点，所以在对一个BIGINT类型的字段建立索引时，多叉搜索树中的n最好设置为接近于1170的一个值，就能够尽可能减少搜索树的层高，进而减少访问的数据块的个数。假如使用了1170叉搜索树，那么第二层就能存放1170个数据行，第三层就能存放100w条数据，第四层就能存放10E条数据，只需要访问有限次的磁盘，就可以访问到10E条数据中的任何一个。
    为什么举例时以BIGINT类型为例，而不用Int类型为例呢？可能是因为在实际创建数据表时，更常创建BIGINT类型的字段。
    在Innodb中，表的数据都是保存在主键索引中的，每当我们创建一个索引，在磁盘上都会多一个b+树。根据b+树的叶子节点的内容，索引可以被划分为主键索引和非主键索引，主键索引的叶子节点中保存的是整个数据行，非主键索引的叶子节点中保存的是主键的值，在Innodb中，主键索引又被称为聚簇索引，非主键索引又被称为二级索引（为什么要起这么多乱七八糟的名字）。那么使用主键索引执行查询语句和使用非主键索引执行查询语句有什么区别呢？区别在于主键查询只需要搜索主键索引这棵b+树就可以拿到完整的数据行，而非主键查询需要先在非主键索引上取到主键值，再回到主键索引上根据主键值找到完整的数据行，也就是说非主键查询需要经过一次回表（人们把回到主键索引再次进行搜索的过程称为回表）才能取得完整的数据行，所以在写sql语句时更推荐使用主键索引。
    多叉搜索树本身就是有序的，才能起到加快查询的目的，所以当我们向多叉搜索树插入新数据时需要对多叉搜索树进行维护，使其继续保持有序的特性。如果插入的新值比多叉搜索树上现有的所有节点的值都大，那我们只需要找到多叉搜索树中已有最大节点所在的数据页，然后把新值放在已有最大节点的后面。前面我们提到在Mysql中即使搜索树的一层节点很少，也会占用一个数据页（为什么会这么设置？），不同层的节点一定位于不同的数据页上，那么当搜索树的某层中的节点个数很多时，就会占用很多个数据页，在同一个数据页上的节点是按顺序存放的，如果这时我们需要向一个已经放满数据的数据页的中间插入新值，那么会发生什么呢？就会发生页分裂，什么是页分裂呢？页分裂就是指Mysql再申请一个空的数据页，然后把一部分的数据迁移到这个数据页上的现象，这样原来的数据页就有位置存放新值了。很显然页分裂的过程是需要时间的，所以插入语句的执行时间会变长。而且页分裂还有别的缺点，那就是会降低数据页的利用率，增加了数据页的数量，数据页的使用空间却基本没变。那么会有提高数据页利用率的情况吗？如果逻辑上相邻的两个数据页由于删除数据导致这两个数据页的利用率很低，那么Mysql就会合并这两个数据页上的数据，从而提高数据页的利用率。
    使用自增列作为主键的优点是什么？第一个优点是在插入新值时总是会插入到在逻辑上位于最后的未满的数据页上，如果最后一个数据页已经放满了数据，那么会再次申请一个新的空白数据页，而不会发生页分裂，第二个优点在于非主键索引的叶子节点中存放的是主键的值，所以主键占用的空间越小，节省的空间就越多。
    那么什么时候适合用业务字段来作为主键，而不是自增列呢？只能创建一个索引，在业务字段上建立的索引是唯一索引，因为主键索引必须是唯一索引。既然只能创建一个索引，那么就不需要考虑非主键索引的叶子节点的占用空间问题，再考虑到”尽量使用主键进行查询”的原则，把业务字段作为主键，可以节省回表的耗时，考虑到这个原则了就要把业务字段设置为主键吗？我觉得并不充分。但还是没有解决可能会出现的页分裂现象。什么是业务字段？比如记录订单号的字段。那么这种情况下使用业务字段作为主键比使用自增列作为主键有什么优点呢？优点在于业务字段是有实义的，而自增列是没有具体含义的，使用业务字段写sql语句会更简单一些。