B 树

在计算机科学中，B 树（B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

https://oi-wiki.org/ds/b-tree/

在 B 树中，有两种节点：

• 内部节点（internal node）：存储了数据以及指向其子节点的指针。
• 叶子节点（leaf node）：与内部节点不同的是，叶子节点只存储数据，并没有子节点。

B 树性质

首先介绍一下一棵 $m$ 阶的 B 树的特性。$m$ 表示这个树的每一个节点最多可以拥有的子节点个数。一棵 $m$ 阶的 B 树满足的性质如下：

1. 每个节点最多有 $m$ 个子节点。
2. 每一个非叶子节点（除根节点）最少有 $\lceil \frac{m}{2}\rceil$ 个子节点。
3. 如果根节点不是叶子节点，那么它至少有两个子节点。
4. 有 $k$ 个子节点的非叶子节点拥有 $k-1$ 个键，且升序排列，满足 $k[i]<k[i+1]$。
5. 每个节点至多包含 $2k-1$ 个键。
6. 所有的叶子节点都在同一层。

B 树优势

二叉查找树的问题在于，由于每个节点只能容纳一个数据，导致树的高度很高，逻辑上挨着的节点数据可能离得很远。

考虑在磁盘中存储数据的情况，与内存相比，读写磁盘有以下不同点：

• 读写磁盘的速度相比内存读写慢很多。
• 每次读写磁盘的单位要比读写内存的最小单位大很多。
• 由于读写磁盘的这个特点，因此对应的数据结构应该尽量的满足「局部性原理」：「当一个数据被用到时，其附近的数据也通常会马上被使用」，为了满足局部性原理， 所以应该将逻辑上相邻的数据在物理上也尽量存储在一起。这样才能减少读写磁盘的数量。

所以，对比起一个节点只能存储一个数据的 BST 类数据结构来，要求这种数据结构在形状上更「胖」、更加「扁平」，即：每个节点能容纳更多的数据， 这样就能降低树的高度，同时让逻辑上相邻的数据都能尽量存储在物理上也相邻的硬盘空间上，减少磁盘读写。