B树

B 树是为磁盘或其他直接存取的辅助存取设备而设计的一种多叉平衡搜索树，类似于红黑树，但 B 树在降低磁盘 I/O 操作方面要更好一些。许多数据库系统使用 B 树或 B 树的变种来存储信息。

我们知道，磁盘 I/O 是很慢的，因为要涉及到磁头寻道、定址和数据读取时间。寻道是一种机械运动，速度自然慢；定址的平均时间是磁盘旋转周期的一半，目前主流磁盘旋转速度是 5400RPM，快一点的也是 7200RPM。尽管如此，旋转一圈也需要 8.33ms，比内存存取时间的 50ns 要高出 5 个数量级。所以综合来说，磁盘 I/O 与主存 I/O 的差距在 6~8 个数量级之间。

因此我们需要尽可能的减少磁盘 I/O 的次数。这时候 B 树就出现了。一颗 B 树 T 是具有以下性质的有根树：

1. 每个节点 x 具有下面属性：
   • x.n: 当前存储在节点 x 中关键字的个数；
   • x.n 个关键字本身 x.key₁、x.key₂ ... x.key_x.n，以非降序存放，使得 x.key₁ <= x.key₂ <= ... <= x.key_x.n。
   • x.leaf: 一个 bool 值，如果 x 是叶子节点，则为 true，否则为 false;
2. 每个内部节点 x 还包含 x.n+1 个指向其孩子的指针；
3. 关键字 x.key_i 对存储在各子树中的关键字范围加以分割；
4. 每个叶子节点具有相同的深度，即树的高度 h。
5. 每个节点所包含的关键字个数有上界和下界，其中下界大于等于 2。

因为 B 树具有以上这些性质，所有尽管 B 树的基本操作和红黑树一样也是对数量级的，但 B 树中对数的底可能很大，这就使得 B 树的高度很低。如果我们令 B 树的根节点存储在主存上，那么对于一个高度为 3，每个节点有 1000 个关键字的 B 树，最多只需要在磁盘上查找 2 次。而这棵树可以存储的信息达到 1000³,即十亿个!正因为此，B 树特别适合用来做磁盘 I/O。