B+树索引

读写效率

索引的目的是什么，当然是更快地检索到想要找的数据。但是检索的速度还跟数据的存储介质有关，众所周知，内存要比硬盘读写更快，但是其实也分情况。
一般来说，如果是随机读写，会有10万到100万倍左右的差距。但如果是顺序访问大批量数据的话，磁盘的性能和内存就是一个数量级的。这里面的原理不在这篇文章的讨论范围内，默认这一事实即可。
对于数据库来说，它存储的数据必然是非常庞大的，数据无法全部存储在内存中，需要借助磁盘完成存储和检索。
假设有一个有序数组存储在硬盘中，如果它足够大，那么它会存储在多个块中。当我们要对这个数组使用二分查找时，需要先找到中间元素所在的块，将这个块从磁盘中读到内存里，然后在内存中进行二分查找。如果下一步要读的元素在其他块中，则需要再将相应块从磁盘中读入内存。直到查询结束，这个过程可能会多次访问磁盘。我们可以看到，这样的检索性能非常低。由于磁盘相对于内存而言访问速度实在太慢，因此，对于磁盘上数据的高效检索，我们有一个极其重要的原则：对磁盘的访问次数要尽可能的少！
为了减少磁盘的访问次数，将索引和数据分离就是一种常见的设计思路。

线性索引方案

上篇文章讲到，在单个索引页内查找一条记录，只需要根据页目录进行二分查找就可以了。由于一个索引页肯定无法储存我们所有的记录，因此我们需要在多个索引页中查找我们需要的记录，这就需要我们先定位到记录所在的索引页，然后在根据页目录查找相应的记录。

最简单的索引方案和页目录的做法类似，我们可以为所有的索引页做一个目录，每页对应一个目录项，每个目录项的内容包括两项内容：

页的用户记录中最小的主键值，我们用key来表示。
页号，我们用page_no表示。这样所有的目录项组成了一个有序数组，它占用的空间很小，可以放入内存中，这种方案叫做线性索引。
页分裂
大部分的检索算法都需要保证要检索的东西是有序的。因此，我们必须通过一些诸如记录移动的操作来始终保证：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。

在数据频繁变化的场景中，有序数组并不是一个最好的选择，二叉检索树或者哈希表往往更有普适性。但是，哈希表由于缺乏范围检索的能力，在一些场合也不适用。因此，二叉检索树这种树形结构是许多常见检索系统的实施方案。
InnoDB使用B+树作为索引的数据结构，至于为什么稍后再讲，先来看看InnoDB中索引是怎样工作的。
首先可以看到，目录项和普通的用户记录差不多，只不过它存储的是主键和页号而已，所以可以直接复用之前存储用户记录的索引页来存储目录项，为了和用户记录做一下区分，在记录头信息中将record_type标记为1，它的各个取值代表的意思如下：

0：普通的用户记录
1：目录项记录
2：最小记录
3：最大记录

将存储目录项的索引页以及存储实际用户数据的索引页套入到B+树的数据结构中后，索引就长这样：

聚簇索引

InnoDB默认会为每个表创建这样一个索引，叫做聚簇索引。
它有如下特点：

使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
- 页内的记录是按照主键的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B+树的叶子节点存储的是完整的用户记录。

二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用。因此如果我们想以别的列（1列或者多列是一样的）作为检索条件时，就可以以这个列替换主键在聚簇索引中的作用，再创建一个B+树索引，这样的索引叫做二级索引。它与聚簇索引的主要区别在于叶子节点中存储的不再是完整的用户记录，而是指定列和主键这两个列的值。

回表

当我们需要根据指定列查询完整的用户记录时，我们需要根据二级索引查找到记录的主键值，然后再根据主键值使用聚簇索引查询完整的用户记录，这一过程叫做回表。
回表是有代价的，举个例子：

1	SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

使用二级索引（name）进行范围查询，然后根据主键进行回表。使用二级索引时，数据都会在相近的几个数据页中，我们可以通过顺序I/O很快的把这些连着的记录从磁盘中读出来。但是根据主键回表时，数据可能分布在不同的数据页中，这样就会随机I/O。
因此应该尽量避免使用*号作为查询列表，最好把我们需要查询的列依次标明，在创建联合索引的时候尽量保证索引列的集合就是要检索的列的超集，也就是覆盖索引。
回表的记录越多，使用二级索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用二级索引。需要回表的记录越少，查询优化器就越倾向使用二级索引而不是全表扫描。因此如果某些情况确实无法执行覆盖索引，如果可以使用LIMIT子句，那么优化器就会倾向于使用二级索引+回表的方式执行查询。

为什么是B+树？

上面提到，尽管二叉检索树可以解决数据动态修改的问题，但在索引数据很大的情况下，依然会有数据无法完全加载到内存中。一个很自然的思路，就是将索引数据也存在磁盘中。那如果是树形索引，我们应该将哪些节点存入磁盘，又要如何从磁盘中读出这些数据进行检索呢？
B+树给出了将树形索引的所有节点都存在磁盘上的高效检索方案。使得索引技术摆脱了内存空间的限制，得到了广泛的应用。
操作系统对磁盘数据的访问是以块为单位的。因此，如果我们想将树型索引的一个节点从磁盘中读出，即使该节点的数据量很小，但磁盘依然会将整个块的数据全部读出来，而不是只读这一小部分数据，这会让有效读取效率很低。
B+ 树的一个关键设计，就是让一个节点的大小等于一个块的大小。节点内存储的数据，不是一个记录，而是一个可以装m个记录的有序数组。这样一来，我们就可以将磁盘一次读取的数据全部利用起来，使得读取效率最大化。
B+ 树还有另一个设计，就是将所有的节点分为内部节点和叶子节点。尽管内部节点和叶子节点的数据结构是一样的，但存储的内容是不同的。内部节点仅存储 key 和维持树形结构的指针，并不存储 key 对应的数据（无论是具体数据还是文件位置信息）。这样内部节点就能存储更多的索引数据，我们也就可以使用最少的内部节点，将所有数据组织起来了。而叶子节点仅存储 key 和对应数据，不存储维持树形结构的指针。通过这样的设计，B+ 树就能做到节点的空间利用率最大化。

此外，B+ 树还将同一层的所有节点串成了有序的双向链表，这样一来，B+ 树就同时具备了良好的范围查询能力和灵活调整的能力了。
因此，B+ 树是一棵完全平衡的 m 阶多叉树。所谓的 m 阶，指的是每个节点最多有 m 个子节点，并且每个节点里都存了一个紧凑的可包含 m 个元素的数组。B+ 树的一个节点就能存储一个包含 m 个元素的数组，这样的话，一个只有 2 到 4 层的 B+ 树，就能索引数量级非常大的数据了，因此 B+ 树的层数往往很矮。比如说，一个 4K 的节点的内部可以存储 400 个元素，那么一个 4 层的 B+ 树最多能存储 400^4，也就是 256 亿个元素。

检索过程

因为B+树一个节点的大小等于一个块的大小，因此当我们检索一个记录时，通过一次硬盘访问，就可以将根节点的所有数据读出，然后在根节点的有序数组中二分查找下一个需要读取的块的地址，因此在B+树的每一层我们只需要读取一次硬盘，如果B+树有4层，那么我们最多读取4次硬盘，就可以到达叶子节点。
我们还可以将内部节点存入内存，来进一步减少对硬盘的读取。比如说一个4层的B+树，每个节点大小为4K，那么第一层根节点就是 4K，第二层最多有 400 个节点，一共就是 1.6M；第三层最多有 400^2，也就是 160000 个节点，一共就是 640M。对于现在常见的计算机来说，前三层的内部节点其实都可以存储在内存中，只有第四层的叶子节点才需要存储在磁盘中。

B+树动态调整

因为B+树是完全平衡的多叉树，因此在新增节点和删除节点时，是需要进行动态调整的。

插入数据

由于具体的数据都是存储在叶子节点上的，因此，数据的插入也是从叶子节点开始的。以一个节点有 3 个元素的 B+ 树为例，如果我们要插入一个 ID=6 的节点，首先要查询到对应的叶子节点。如果叶子节点的数组未满，那么直接将该元素插入数组即可。具体过程如下图所示：

如果我们插入的是 ID=10 的节点呢？按之前的逻辑，我们应该插入到 ID 9 后面，但是 ID 9 所在的这个节点已经存满了 3 个节点，无法继续存入了。因此，我们需要将该叶子节点分裂（也就是页分裂）。分裂的逻辑就是生成一个新节点，并将数据在两个节点中平分。

叶子节点分裂完成以后，上一层的内部节点也需要修改。但如果上一层的父节点也是满的，那么上一层的父节点也需要分裂。

内部节点调整好了，下一步我们就要调整根节点了。由于根节点未满，因此我们不需要分裂，直接修改即可。

删除数据也类似，如果节点数组较满，直接删除；如果删除后数组有一半以上的空间为空，那为了提高节点的空间利用率，该节点需要将左右两边兄弟节点的元素转移过来。可以成功转移的条件是，元素转移后该节点及其兄弟节点的空间必须都能维持在半满以上。如果无法满足这个条件，就说明兄弟节点其实也足够空闲，那我们直接将该节点的元素并入兄弟节点，然后删除该节点即可。

其他搜索树呢？

以B树为例，B树与B+树的主要区别在于，B 树可以在非叶结点中存储数据，但是 B+ 树的所有数据其实都存储在叶子节点中。这样的结果是储存相同的数据的情况下，B树的层高可能会低于B+树，以至于在查询单条记录时，B树的平均随机 IO 次数会比 B+ 树少，因为不用每次都到树的最底层查找数据。但是在做范围查询时，因为满足条件的数据可能分散在B树的各个节点上，不是连续的，导致B树的平均随机 IO 次数会比 B+ 树多。
也就是说单条查询的话，B 树应该时更好的选择，但是范围查询的话，B+ 树是更好的选择。InnoDB设计时要应对的场景，当然要包括范围查询，而且认为范围查询很常见，所以选择B+ 树就很自然了。
但是像MongoDB的WiredTiger引擎设计的时候认为单条数据的查询更为常见，所以自然就会选择B 树作为存储的数据结构了。

总结

B+树索引的检索过程其实也是二分查找，因此如果B+树索引完全加载在内存中的话，它的检索效率其实并不会比有序数组或者二叉检索树更高，也还是二分查找的 log(n) 的效率。并且，它还比数组和二叉检索树更加复杂，还会带来额外的开销。但是，B+ 树最大的优点在于，它提供了将索引数据存在磁盘中，以及高效检索的方案。这让检索技术摆脱了内存的限制，得到了更广泛地使用。
单个索引页内的页目录其实就是一个有序数组，正因为在多个索引页间检索使用的是B+树，因此页目录可以维持在一个较小的范围内，这使得在索引数据很大的情况下，B+树依然可以将索引数据和用户数据（或者说内部节点和叶子节点）分别存储在内存和硬盘中。