索引原理

写在前面

在前面我们对一些常用的数据检索算法和数据结构进行了学习，后面还遗留了B-树和B+树，因此接下来就开始学习这些知识。

B-树

B-树读作B杠树，B-树是在平衡二叉树（AVL）上进化而来的，前面学习的几种树，每个节点上只有一个元素，而B-树节点中可以存放多个元素，其目的是为了降低树的高度。

一棵m阶的B-Tree有如下特点：
（1）每个节点最多有m个孩子，m称为b树的阶；
（2）除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子；
（3）若根节点不是叶子节点，则至少有2个孩子；
（4）所有叶子节点都在同一层，且不包含其它关键字信息；
（5）每个非终端节点包含n个关键字（键值）信息；
（6）关键字的个数n满足：ceil(m/2)-1 <= n <= m-1；
（7）ki(i=1,…n)为关键字，且关键字升序排序；
（8）Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)。

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元的数组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键之外的数据。对于不同的记录，key值互不相同。

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，下图为一个3阶的B-Tree：

每个节点占用一个磁盘块的空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个键将数据划分为三个范围域，对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，p1指针指向的子树的数据范围为小于17，p2指针指向的子树的数据范围为17~35，p3指针指向的子树的数据范围为大于35。

接下来将通过查询关键字29来模拟这一查询过程：

1、根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】；
2、比较关键字29在区间（17,35），找到磁盘块1的指针p2；
3、根据p2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】；
4、比较关键字29在区间（26,30），找到磁盘块3的指针p2；
5、根据p2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】；
6、在磁盘块8中的关键字列表中找到关键字29。

通过上面的分析可以知道，想找到关键字29，需要发生3次磁盘I/O操作，和3次内存查找操作，由于内存中的关键字是一个有序表结构，可以利用二分法快速定位到目标数据，而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。

B-树相对于AVL树而言，B-树通过在节点中增加节点内部数据的个数来减少磁盘的IO操作。

前面我们说过MySQL采用页方式来读写数据，每页是16KB。如果我们用B-树来存储MySQL记录，那么每个节点对应MySQL中的一页（16KB），假如每行记录加上树节点中的1个指针一共占160Byte，那么每个节点可以存储1000（16KB/160Byte）条数据，树高度为3的节点大概可以存储（第一层1000+第二层1000²+第三层1000³）10亿条记录，这个存储量是非常惊人的。也就是说一个高度为3的B-树，大概可以存储10亿条记录，而我们从10亿条记录中查找数据，只需3次IO操作就能定位到目标数据所在的页，而页内部的数据又是有序的，然后将其加载到内存中使用二分法查找，这个速度其实是非常快的。

从上面的分析中可以知道，使用B-Tree定位某个值其实是非常快的，但是它也存在缺点—不利于范围查找。举个例子，假设我们需要查找[15,36]区间的数据，那么此时需要访问7个磁盘块（1、2、7、3、8、4和9），这样导致IO次数又增加了，而范围查找却是我们经常会用到的，因此这么来看，B-Tree也不太适合在磁盘中存储需要检索的数据。

B+树

首先看一个B+数的结构示意图：

一棵m阶的B+Tree有如下特点：
（1）每个节点至多有m个孩子，m称为b树的阶；
（2）除根节点外，每个结点至少有Ceil(m/2)个孩子，根结点至少有两个孩子；
（3）有k个子女的节点必有k个关键字；
（4）父节点中持有访问子节点的指针；
（5）父节点的关键字在子节点中都存在（如上面的1、20、35在每层都存在），要么是最小值，要么是最大值，如果节点中关键字是升序的方式，父节点的关键字是子节点的最小值；
（6）最底层的节点是叶子节点；
（7）除叶子节点外，其他节点不保存数据，只保存关键字和指针；
（8）叶子节点包含了所有数据的关键字以及data，叶子节点之间用链表连接起来，可以非常方便的支持范围查找。

B+树和B-树的区别

（1）B+树中一个节点如果有k个关键字，最多可以包含k个子节点（k个关键字对应k个指针）；而b-树对应k+1个子节点（多了一个指向子节点的指针）；

（2）B+树除叶子节点之外其他节点值存储关键字和指向子节点的指针，而B-树还存储了数据，这样同样大小情况下，B+树可以存储更多的关键字；

（3）B+树叶子节点中存储了所有关键字及data，并且多个节点用链表连接，从上图中看子节点中数据从左向右是有序的，支持范围查找（先定位范围的最大值和最小值，然后子节点中依靠链表遍历范围数据）。

B+树和B-树使用选择

（1）B-树因为非叶子节点也保存具体数据，所以在查找某个关键字的时候，找到即可返回；而B+树所有的数据都在叶子节点，每次查找都得到叶子节点。因此在同样高度的B-树和B+树中，B-树查找某个关键字的效率更高；
（2）由于B+树所有的数据都在叶子节点，并且叶子节点之间有指针连接，因此在查找大于或者小于某个关键字的数据的时候，B+树只需找到给关键字然后沿着链表遍历即可；而B-树还需要遍历该关键字节点的根节点去搜索数据；
（3）由于B-树的每个节点（这里的节点可以理解为一个数据页）都存储主键+数据，而B+树的非叶子节点只存储关键字信息，而每个页的大小是有限的，所以同一页能存储的B-树的数据比B+树存储的要少。这样同样总量的数据，B-树的深度会更大，会增加查询时磁盘的IO次数，进而影响查询效率。

MySQL的存储引擎和索引

MySQL内部索引是由不同的引擎实现的，这里主要说一下InnoDB和MyISAM这两种引擎中的索引，这两种引擎中的索引都是使用B+树的结构来存储的。

密集索引

密集索引：文件中的每个搜索码值都对应一个索引值。可以理解为密集索引的叶子节点保存的不只是键值，还保存了位于同一行记录里的其他列的信息，由于密集索引决定了表的物理排列顺序，一个表只有一个物理排列顺序，所以一个表只能创建一个密集索引。

稀疏索引

稀疏索引：文件只为索引码的某些值建立索引项。可以理解为稀疏索引的叶子节点仅保存了键位信息以及该行数据的地址，有的稀疏索引仅保存了键位信息及其主键，那么定位到叶子节点之后仍然需要地址或者主键信息进一步定位到数据。

上面是对于一般的数据库而言，接下来对MySQL做具体分析。MySQL主要有两种存储引擎：MyISAM和InnoDB，这两种是主流引擎。

InnoDB中的索引

InnoDB中有2种索引：主键索引（也称聚集索引）和辅助索引（也称非聚集索引）。

主键索引：每个表只有一个主键索引，叶子节点同时保存了主键的值和数据记录。

辅助索引：叶子节点保存了索引字段的值以及主键的值。

MyISAM中的索引

不管是主键索引还是辅助索引，其结构都是一样的，叶子节点保存了索引字段的值以及数据记录的地址。

示例

为了更好的说明这两种索引的区别，这里假定有一个学生表，它存储了4行数据，其中Id作为主键索引，Name作为辅助索引，那么下图就清晰的展示了主键索引和辅助索引的差异：

InnoDB数据检索过程

（1）如果需要查询Id=14的数据，只需在左侧的主键索引中检索即可；
（2）如果要搜索Name=’Ellison’的数据，那么需要两个步骤：（i）首先在辅助索引中检索到Name=’Ellison’的数据，进而获取到其Id为14；（ii）再到主键索引中检索Id为14的记录。

辅助索引这个查询过程在MySQL中称之为回表。

MyISAM数据检索过程

（1）在索引中找到对应的关键字，获取关键字对应的记录的地址；
（2）通过记录的地址查找到对应的数据记录。

解惑

由于我们日常用的最多的是InnoDB引擎，因此这里着重介绍InnoDB索引的情况。在InnoDB引擎中，最好使用主键索引，这样只需一次索引就能找到对应数据；如果使用辅助索引，那么会涉及到回表操作，因此会比主键索引消耗的时间多一些。

现在有一个疑问，就是InnoDB中的辅助索引为什么不和MyISAM那样存储记录的地址？

我们知道，表中的数据发生变更时，会影响其他记录地址的变化，如果辅助索引中记录数据的地址，此时会受到影响，而主键的值一般很少会更新，因此当页中的记录发生地址变更的时候，对辅助索引是没有影响的。

页结构

接下来学习Mysql中的页结构，页是真正存储记录的地方，对应B+树中的一个节点，页也是MySQL中读写数据的最小单位，页结构的设计的好坏会影响数据的查询速度。

页结构详解

MySQL中的页是InnoDB中存储数据的基本单位，也是MySQL中管理数据的最小单位，和磁盘交互的时候都是以页进行，默认大小是16K。前面也说了MySQL使用B+树来存储数据，而且页就相当于B+树中的一个节点。

页的结构如下所示：

由上图可以知道，每个Page都有通用的头和尾，不同的是中间的部分会根据Page的类型而发生变化。Page头部中有些我们关系的数据，因此接下来看一下Page头部的详细信息，如下所示：

这里重点关注和数据组织结构相关的字段，可以发现其中Page的头部保存了两个指针，分别指向前一个和后一个Page，言外之意Page连接起来的结构就是双向链表，如下所示：

再来看一下Page的主体内容，这里着重关注行数据和索引的存储，可以发现它们都位于Page的User Records部分。User Records占据了Page的大部分空间，User Records由一条一条的Record组成。在一个Page内部，单链表的头尾由固定内容的两条记录来表示，字符串形式的“Infimum”代表开头，“Supremum”代表结尾，这两个用来代表开头结尾的Record存储在System Records中。“Infimum”、“Supremum”和“User Records”组成了一个单向链表结构。

起初数据是按照插入的先后顺序进行排列，但是后来随着新数据的插入和旧数据的删除，数据的物理顺序会变得混乱，但是它们之间依然通过链表来保持逻辑上的先后顺序，如下所示：

把User Record的组织形式和若干Page组合起来，就可以形成一个较为完整的形式，如下所示：

再来看一下B+树的结构，如下所示：

InnoDB为了快速查找记录，在页中定义了一个称之为Page Directory的目录槽（Slots）。每个槽位占用两个字节（用于保存指向记录的地址），Page Directory中的多个Slot组成了一个有序数组（可以使用二分法快速定位），行记录被Page Directory分成了多个块，块与块之间有序，能够加速记录的查找，如下所示：

从图中可以看出，每个行记录的都有一个n_owned的区域，也就是图中粉色的区域。n_owned标识所属的Slot这个块有多少条数据，伪记录Infimum的n_owned值总是1，记录Supremum的n_owned的取值范围为[1,8]，其他用户记录的n_owned的取值范围为[4,8]，并且只有每个块中最大的那条记录的n_owned才会有值，其他的用户记录的n_owned为0。

数据检索过程

在Page中查询数据的时候，先通过B+树中的查询方法定位到数据所在的页，然后将页整体加载到内存中，接着通过二分法在Page Directory中检索数据，来不断缩小范围。

举个例子，假设需要检索7，那么通过二分查找法查找到7位于Slot2和Slot3所指向的记录中间，然后从Slot3指向的记录5开始向后一个个的查找，此时就能找到记录7；如果里面没有7，那么就继续查找，直到Slot2中的记录8结束。

n_owned范围控制在[4,8]内，可以保证每个Slot内的范围数量可以控制在[4,8]个，可以加速目标数据的查找。当有数据插入的时候，Page Directory为了控制每个Slot对应块中记录的个数([4,8])，此时Page Directory中会对Slot的数量进行调整。

Page结构小结

接下来将对Page结构进行一个小结：（1）B+树中叶子节点之间使用双向链表进行连接，可以实现范围查找；（2）页内部的记录之间采用单向链表连接，便于访问下一条记录；（3）为了加快页内部记录的查询，对页内记录加上了一个有序的稀疏索引，即页目录（Page Directory）。

也就是说MySQL中的索引使用到了B+树，链表、二分查找法等，进而实现了快速定位目标数据、快速范围查找数据。

文章总结

本文首先学习了B-树和B+树这两种数据结构，并在此基础上学习了两者的区别和使用选择。之后学习了MySQL中的密集索引和稀疏索引，已经InnoDB和MyISAM中的索引，最后介绍了MySQL中的页结构和数据的检索过程。通过本文的学习，使得我们对MySQL的索引变得更加清晰。

参考大佬： jcole