DS. B-Tree

B树是一种高效的多路平衡搜索树。你可以在文件系统/数据库这类有关磁盘存储（Mass storage system）中经常看到B树极其变种的身影。我们知道，树这种结构往往代表着优秀的查询时间复杂度，比如红黑树这类二叉树的查询时间复杂度为 ，即假如我们有10亿数据，我们最多需要30次 I/O 操作。相比顺序结构简直好到那里去了。

既然二叉树搜索已经足够快了，我们为什么还要学习B树？因为磁盘 I/O 太太太慢了。访问一次磁盘 I/O 会浪费数百万个时钟周期，相比之下，访问内存通常需要 200-300 个时钟周期。这就相当于在厨房做饭，去菜市场买菜和在冰箱里面拿的区别。

同样的10亿数据，怎么能让查询更快呢？既然我们的树不能往高了长，那就压低树高，让他变宽不就行了吗？Rudolf Bayer 和 Edward M. McCreight 在上世纪70年代也是这样想的。所以相比二叉树，B树的每个节点可以包含 m 个子节点（我们称之为m阶B树）。

在文件系统和数据库中，B树及其变种的阶数通常在 64-1600 之间。假如我们的B树阶数为200阶，那么其搜索10亿数据所需要的I/O操作就是：4次。足足减少了 86% 的I/O操作。（所以红黑树并不应用在磁盘中，你可以在内存/缓存结构中看到红黑树的身影）

数据结构并不是最难的，算法才是。下面是一个最简单的B树，一个父节点，三个子节点。除了中间的子节点外，其他的节点均拥有2个键，父节点有三个指向子节点的指针。所以这个树是3阶B树。

从之前的学习中，我们只看到B树降低了查询次数，我们还会得到什么呢？天下没有掉馅饼的好事情，B树也不例外。我们减少了 I/O 操作，但是我们查询子节点时需要比较的操作肯定变多了。二叉树你只需要一次比较，但是m阶B树，你需要 次的比较操作。

但是一旦我们从磁盘中取到节点，我们比较的操作实际上是在内存中进行的。前面我们提到了磁盘操作相比内存操作要慢多少了，上千次内存操作也比不上一次磁盘操作所消耗的时间长，所以比较操作的时间几乎可以不计了。我们赢了两次。

B树有许多规则，通过这些规则，我们就能保证B树处于一个平衡状态，以便发挥其特性。B树的规则有：

需要再次补充说明的是，每个节点除了键还会存储指向子节点的指针。从上面的图不难发现，指针的个数往往是键个数+1。

B树的新键插入也很有意思，具体的规则是：

假如我们现在有下面的3阶B树（每个节点最多2个键）。我们通过 mermaid 图来了解整个过程。

第一步插入键值8，我们通过定位将其插入到叶子节点 [5, 7]。这时变为 [5, 7, 8]，键数为3，溢出。

溢出后分裂叶子节点，中间键 7 提升到父节点中，源节点分裂为 [5] 和 [8]。

我们再插入键值25。同样的也会溢出。

分裂叶子节点，我们讲中间键提升到父节点中。这时，父节点也会溢出。这时，我们就增加一层树高，把父节点的中间键提升到新的根节点中。

至此，B+树的插入完成了。

B+树和B树的区别在于，B+树只使用叶子节点来存储数据，内部节点仅仅作为索引使用。所以B+树所有查询的路径长度是严格一致的。这样做的好处是，由于指针只有 8 字节，你可以一次性从磁盘中读取很多指针信息。这样，你就可以在内存中找你想要的信息，适合范围查询。