本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。

注：在本文中“结点”和“节点”同义，在B树部分，“节点”和“页”同义。

背景知识

很多数据库都是基于B树

传统树的特点回顾

由数据结构与算法的知识可知，BST（二叉搜索树）的左子树的值<根值<右子树的值。

有可能出现极端情况：子节点全在右子树，BST退化为链表。如图所示：

最差情况的时间复杂度为O(N)

为了使树保持平衡，就引入了AVL(平衡二叉树)的概念。具体操作为：在添加或删除结点后进行旋转。如下图所示：

最差情况的时间复杂度为O(Log2N)

为什么在磁盘上使用BST（或其变体）来存储不是一个最佳选择？

维护成本增加：由于扇出（每个节点允许拥有的最大子节点数）较低，必须频繁执行平衡操作、重定位节点、更新指针。

基于维护成本的考虑以及优化

如果想用BST,也不是不可以。需要考虑以下问题并作出优化：

• 新创建的节点不一定在其父节点附近写入，因此，节点子指针可能跨越多个磁盘页。

改进方案：修改树的布局；使用分页二叉树

• 二分树每个节点允许拥有的最大子节点数（概念回顾：扇出）为2，假设有N个结点，则树的高度为Log2N，这也是定位某元素的时间复杂度，同时更是磁盘传输的次数。这样的复杂度在外存中不实用。

什么类型的树适合磁盘实现？

• 高扇出

（本文中第三次重复这个概念了噢，还没记得的小伙伴翻翻前面）

使得数据局部性更好。

• 低高度

减少遍历时的寻道次数。

从树的整体规律可知，总结点相同，扇出高，必然导致高度低；反之亦然。所以这两种条件理论上是可以同时满足的。

B树

简介

其基于平衡搜索树实现，但具有更高的扇出和更低的高度。

以下是B树的表示：
（与其他树不同，这里把它的结点抽象为矩形结构可能更容易让人理解它的特性，尤其是高扇出）

高扇出可以均摊保持树平衡时所做更改的开销；低高度可以减少寻道次数。

何时会触发分裂与合并操作？

当节点已满或几乎为空时。

B+树

数据库系统中真正被广泛用的是B+树。

B树和B+树的区别？

我的理解：

B树是一个大类，B+就再细分一点点。但是很多时候直接用B树指代B+树。

• B树在任意一层上都能存储值。

• 而B+树中规定，仅在叶结点存值，内部节点仅用于存分割键。

  • 值仅在叶节点上，所以crud仅影响到叶结点（例外：分裂和合并期会传播到上层）

B+树的一些特性

• 下图展示了一些不等式关系：

（文字描述会显得很啰嗦，细细看图应该就懂了）

• B树的构造过程是自下而上的
• B树的查找复杂度一般记为Log2N。（N为B树中项的总数）。

参考资料

《Database Internals:A Deep dive into How Distributed Data Systems Work》