什么是索引

索引是一种数据结构，用于提高mysql查询效率。
数据库查询是数据库最主要的功能之一。设计者们都希望查询数据库的速度尽可能的快。因此数据库系统的设计者会从查询算法的角度来进行优化。

最基本的的查询算法：顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是非常糟糕的，所以有很多其它优秀的算法，例如：顺序查找、折半查找、快速查找等。

但是每种查找算法都只能应用于特定的数据结构之上，例如顺序查找依赖于顺序结构，折半查找通过二叉查找树或者红黑树实现二分搜索。因此在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这种数据结构就叫做：索引。

MySQL索引原理

目前大多数数据库系统及文件系统都采用B-tree或其变种B+tree作为索引结构。B+tree索引是B+tree在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。

从最早的平衡二叉树演化而来。B+tree由二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-tree）逐步优化而来。

为什么MySQL的索引选择B+tree？

红黑树也可以作为数据结构也可以用来实现索引，但是文件系统以及数据库系统普遍采用B-tree或者B+tree，这里结合计算机的组成原理深入分析。

一般来说，索引本身很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，磁盘的I/O操作耗时会高几个数量级，查找过程中需要最优磁盘I/O的存取次数。

提高磁盘数据读写速度原理

局部性原理与磁盘预读。由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动的耗时，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。

为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。

所以，程序运行期间所需要的数据通常应当比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）4k的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为4k），主存和磁盘以页为单位交换数据。

当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

在硬盘中由于涉及到机械运动，所以一次的磁盘IO消耗的时间是非常大的，于内存的读取速度相比，就好比光速与声速的比较。那么回到我们的主题上为什么使用B+树作为数据结构呢？

二叉查找平衡树、B-tree、B+tree、红黑树性能分析

1.二叉查找平衡树：所有的非叶子节点最多拥有两个子节点树；所有节点存储一个关键字；节点的左右子节点，左子节点比该节点小，右子节点比该节点大。

缺点：一个节点存储一个关键字，在大量数据的时候，树高非常大，性能低下。

2.B-tree：基于减少树的高度上，B-tree是一种多路搜索树（M叉树），如下图所示：

特点：

• 所有非叶子节点最多有M个儿子（M>2)，根节点的儿子数为[2,M]，其它非叶子节点儿子数为[M/2, M]；
• 每个节点存放至少M/2-1和至多M-1个关键字；（至少2个关键字）
• 非叶子节点关键字个数=指向儿子的指针个数-1；
• 非叶子结点的关键字中从左到右由小到大排序。即A[1]<A[2]<A[3],…,A[k-1]<A[k]。
• 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])范围的子树，最后一个指针P[M]指向大于随后一个关键字A[M-1]范围的值。
• 关键字集合分布在整颗树中，并且只会在节点中出现一次。
• 搜索可能在非叶子节点或者叶子节点结束，即非叶子节点也存储数据的身，这个与B+树有根本区别。
• 所有叶子节点位于同一层。

检索一次最多需要访问H（树高）个节点。将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。且在一次检索中最多需要h-1次I/O（跟节点常驻于内存）。

3.B+tree：B+tree是B-tree的一种变体，也是一种多路搜索树。使其更适合实现外存索引结构，InnoDB存储引擎就是用B+tree实现其索引结构。如下图所示：

B+tree与B-tree树基本相同，以下是与B-tree的区别：

• 非叶子结点的指针与关键字个数相等，而B-树的关键字=指针个数-1；
• 指针P[i]，指向关键字值属于[K[i], K[i+1])范围的子树，而在B-树是开区间。
• 指针P[i]，指向关键字值属于[K[i], K[i+1])范围的子树，而在B-树是开区间。
• 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的，搜索只会在叶子节点结束，叶子节点存储所有关键字的值。
• 不可能在非叶子结点命中；非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储。

B+tree所有的叶子节点包含了全部关键字信息，及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大的顺序链接。非叶子节点可以看成索引部分，节点中仅含有其子树根节点中最小（或最大）关键字。

在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

在B+树的结构中，只在叶子节点存储数据，在非叶子节点中只存储的索引，在非叶子节点中可以有更大的空间储存更多的索引，这样B+树的出度d就可以大大的增加，从而降低的B+树的高度h，B树中一个节点的大小为一个page的大小，也就是一次IO的读取，h越小IO的次数就可以减少：
$d_{max} = floor(pagesize/(keysize+datasize+pointsize))$dmax​=floor(pagesize/(keysize+datasize+pointsize))
floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

MySQL引擎

MyISAM

在MyISAM储存引擎中，数据和索引文件是分开储存的，MyISAM的存储文件有三个，后缀名分别是 .frm、.MYD、MYI，其中 .frm 是表的定义文件，.MYD 是数据文件，.MYI 是索引文件。

MyISAM 只支持表锁，且不支持事务。MyISAM由于有单独的索引文件，在读取数据方面的性能很高 。

MyISAM也是B+树结构，但是MyISAM索引的叶子节点的数据保存的是行数据的地址。因此，MyISAM中索引检索的算法首先在索引树中找到行数据的地址，然后根据地址找到对应的行数据。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB

在InnoDB中，数据和索引文件是合起来储存的，如图所示，InnoDB 的存储文件有两个，后缀名分别是 .frm 和 .idb，其中 .frm 是表的定义文件，而 idb 是数据文件。

在InnoDB虽然底层也是B+树实现的方式，当时与MyISAM却有明显的区别，在InnoDB实现的索引结构中，索引文件和数据文件是一起的，InnoDB中索引文件中的key就是数据表中的主键索引，因此InnoDB的索引文件也是主索引文件。如下图所示：

在InnoDB中的叶子节点中把保存和完整的数据，这就是聚集索引。因为InnoDB是按照主键聚集的，要是InnoDB没有主键就会找数据表中的位置标志的字段作为主键，要是没有这种字段就会隐世的生成唯一标识的主键，生成的主键默认为长整型，6个字节。

而MyISAM可以要求没有主键，这是这两者的一个明显的区别。另一个区别就是辅助索引的叶子节点的data域存储的是主键的值，而不是行数据。

所以，当查询不是按照主键查询时候就会先在辅助索引树上先找到主键的值，然后再到主索引树找到对应的行数据的值，这叫做回表，回表降低了表的查询效率。

知道了索引的底层原理的实现还是有很大的帮助的，例如：主键至不要过大，因为所有的普通索引都引用主索引，索引本身是占内存的，若是索引过大，这样就会大大影响查询的效率。

[1] B-tree、B+tree、B*tree
[2] MySQL搜索引擎InnoDB和MyISAM对比
[3] mysql索引底层原理