B 树和 B+ 树有什么区别？( 四 ) _B

文章插图

因此需要拆分节点数据，我们从中间把红色的节点拆开，15 作为冗余的索引写入父节点，就形成下图的情况：

文章插图

接着插入 26，写入到对应位置即可。

文章插图

接下来，插入 8 到对应位置即可。

文章插图

然后我们插入 30，此时右边节点发生过载：

文章插图

解决完一次过载问题之后，因为 26 会浮上去，根节点又发生了过载：

文章插图

再次解决过载，拆分红色部分，得到最后结果：

文章插图

在上述过程中，B+ 树始终可以保持平衡状态，而且所有叶子节点都在同一层级。更复杂的数学证明，我就不在这里讲解了。
插入和删除效率
B+ 树有大量的冗余节点，比如删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点。这样删除非常快。B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂。比如删除根节点中的数据，可能涉及复杂的树的变形。
B+ 树的插入也是一样，有冗余节点，插入可能存在节点的拆分（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要更多复杂的算法，类似红黑树的旋转操作等。
因此，B+ 树的插入和删除效率更高。
搜索：链表的作用
B 树和 B+ 树搜索原理基本一致。先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。
你可能会注意到，B+ 树所有叶子节点间还有一个链表进行连接。这种设计对范围查找非常有帮助，比如说我们想知道 1 月 20 日和 1 月 22 日之间的订单，这个时候可以先查找到 1 月 20 日所在的叶子节点，然后利用链表向右遍历，直到找到 1 月22 日的节点。这样我们就进一步节省搜索需要的时间。
总结
这一讲我们学习了在数据库中如何利用文件系统造索引。无论是行存储还是列存储，构造索引的过程都是类似的。索引有很多做法，除了 B+ 树，还有 HashTable、倒排表等。如果是存储海量数据的数据库，我们的思考点需要放在 I/O 的效率上。如果把今天的知识放到分布式数据库上，那除了需要节省磁盘读写还需要节省网络 I/O 。
好了，现在回到文章的开头：MySQL 中的 B 树和 B+ 树有什么区别？
【解析】B+ 树继承于 B 树，都限定了节点中数据数目和子节点的数目。B 树所有节点都可以映射数据，B+ 树只有叶子节点可以映射数据。
单独看这部分设计，看不出 B+ 树的优势。为了只有叶子节点可以映射数据，B+ 树创造了很多冗余的索引（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，而且可以自动平衡，因此 B+ 树的所有叶子节点总是在一个层级上。所以 B+ 树可以用一条链表串联所有的叶子节点，也就是索引数据，这让 B+ 树的范围查找和聚合运算更快。