MySQL相关：索引数据模型推演及 B+Tree 的详细介绍( 三 ) _索引数据

www.cs.usfca.edu/~galles/vis…
比如 Max Degree（路数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有 4 个指针，子节点会变成 4 路，所以这个时候必须进行分裂。把中间的数据 2 提上去，把 1 和 3 变成 2 的子节点。
如果删除节点，会有相反的合并的操作。注意这里是分裂和合并，跟 AVL 树的左旋和右旋是不一样的。我们继续插入 4 和 5，B Tree 又会出现分裂和合并的操作。

文章插图

从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。节点的分裂和合并，其实就是 InnoDB 页的分裂和合并。

B+树（加强版多路平衡查找树）B Tree 的效率已经很高了，为什么 MySQL 还要对 B Tree 进行改良，最终使用了 B+Tree 呢？总体上来说，这个 B 树的改良版本解决的问题比 B Tree 更全面。我们来看一下 InnoDB 里面的 B+树的存储结构：

文章插图

MySQL 中的 B+Tree 有几个特点：

它的关键字的数量是跟路数相等的； B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。举个例子：假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。非叶子节点可以存储多少个指针？假设索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。非叶子节点（一页）可以存储 16384 / 14 = 1170 个这样的单元（键值+指针），代表有 1170 个指针。树深度为 2 的时候，有 1170^2 个叶子节点，可以存储的数据为 1170 * 1170 * 16 = 21902400 。在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询数据最多需要访问 3 次磁盘。所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。它是根据左闭右开的区间 [ )来检索数据。

我们来看一下 B+Tree 的数据搜寻过程：
1）比如我们要查找 28，在根节点就找到了键值，但是因为它不是页子节点，所以会继续往下搜寻，28 是[28,66)的左闭右开的区间的临界值，所以会走中间的子节点，然后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后在叶子节点上找到了需要的数据。
2）第二个，如果是范围查询，比如要查询从 22 到 60 的数据，当找到 22 之后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）。
总结一下，InnoDB 中的 B+Tree 的特点：

它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据） B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）

为什么不用红黑树？红黑树也是 BST 树，但是不是严格平衡的。
必须满足 5 个约束：