1. 为什么 MySQL 采用 B+ 树作为索引⚓
1.1 怎样的索引的数据结构是好的⚓
MySQL 的数据是持久化的，意味着数据（索引 + 记录）是保存到磁盘上的，因为这样即使设备断电了，数据也不会丢失。
磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block）。Linux 中的块大小为 4KB，也就是一次磁盘 I/O 操作会直接读写 8 个扇区。
由于数据库的索引是保存到磁盘上的，因此当我们通过索引查找某行数据的时候，就需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存，也就是说查询过程中会发生多次磁盘 I/O，而磁盘 I/O 次数越多，所消耗的时间也就越大。
所以，要设计一个适合 MySQL 索引的数据结构，至少满足以下要求：
- 能在尽可能少的磁盘的 I/O 操作中完成查询工作；
- 要能高效地查询某一个记录，也要能高效地执行范围查找；
1.2 二分查找⚓
索引数据最好能按顺序排列，这样可以使用「二分查找法」高效定位数据。
二分查找法每次都把查询的范围减半，这样时间复杂度就降到了 O(logn)，但是每次查找都需要不断计算中间位置。
1.3 二分查找树⚓
用数组来实现线性排序的数据虽然简单好用，但是插入新元素的时候性能太低。因为插入一个元素，需要将这个元素之后的所有元素后移一位。
二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点。这样我们在查询数据时，不需要计算中间节点的位置了，只需将查找的数据与节点的数据进行比较。
另外，二叉查找树解决了插入新节点的问题，，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。
当每次插入的元素都是二叉查找树中最大/最小的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)。并且不能范围查询，所以也不合适。
1.4 自平衡二叉树⚓
了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉查找树（AVL 树）。
主要是在二叉查找树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn)。
除了平衡二叉查找树，还有很多自平衡的二叉树，比如红黑树。
不管平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。
1.5 B 树⚓
为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。
B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶（超过这些要求的话，就会分裂节点），所以 B 树就是一个多叉树。
因为 B 树的高度比平衡二叉树要低，所以B 树在数据查询中比平衡二叉树效率要高。
但是 B 树的每个节点都包含数据（索引 + 记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。
而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。
另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。
1.6 B+ 树⚓
B+ 树与 B 树差异的点，主要是以下这几点：
- 叶子节点（最底部的节点）才会存放实际数据（索引 + 记录），非叶子节点只会存放索引；
- 所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
- 非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
- 非叶子节点中有多少个子节点，就有多少个索引；
1.6.1 B+ 和 B 树的性能对比⚓
1.6.1.1 1、单点查询⚓
B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。
但是 B 树的查询波动会比较大，因为每个节点即存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。
B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O 次数会更少。
1.6.1.2 2、插入和删除效率⚓
B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快
B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂，可能涉及复杂的树的变形。
B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。
1.6.1.3 3、范围查询⚓
B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。
因为 B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助。可以先查找到第一个记录所在的叶子节点，然后利用链表向右遍历，直到找到末尾的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。
而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。
因此，存在大量范围检索的场景，适合使用 B+树，比如关系型数据库。而对于大量的单个索引查询的场景，可以考虑 B 树，比如 nosql 的 MongoDB。
1.7 MySQL 中的 B+ 树⚓
参考《从数据页的角度看 B+ 树》。