algorithmsdatabaseinternals

B 树与 B+ 树：数据库索引为什么这么快

从二叉搜索树讲起，看节点为什么要匹配磁盘页、B 树如何把树高压到极低，以及 RDB 为什么最终选了 B+ 树。叶节点链表让范围查询从反复上下遍历变成顺序读取，末尾还讲了节点分裂算法。

kenji.blogkenjinote5 分钟阅读

中文
中文日本語
复制

深入探讨如何最小化磁盘 I/O 的树形结构。

为什么数据库能从几千万甚至上亿条记录中瞬间找到目标数据？背后是一个叫“索引”的机制，而支撑索引的核心数据结构，就是 B-Tree 和 B+Tree。本文从简单的二叉搜索树出发，深入探讨关系型数据库（RDB）为什么最终选择了 B+Tree，以及它的演进过程与内部结构。

1. 二叉搜索树（BST）的局限

作为加速数据检索的数据结构，最先想到的可能是“二叉搜索树（BST）”。二叉搜索树中每个节点最多有两个子节点，左子节点小于父节点，右子节点大于父节点。理想状态下，搜索的时间复杂度为 O(log⁡N)，非常快。

 graph TD
 A["50"] -- "left" --> B["25"]
 A -- "right" --> C["75"]
 B -- "left" --> D["10"]
 B -- "right" --> E["30"]

然而，直接把二叉搜索树用作数据库索引，有一个致命问题。

树的平衡崩塌

如果持续按有序状态插入数据，二叉搜索树就会变成一条笔直的链表，搜索效率退化到 O(N)。为了防止这种情况，出现了 AVL 树、红黑树等“平衡二叉搜索树”，它们会自动调整平衡，把树高维持在 log⁡N。

磁盘 I/O 之墙

最大的挑战在于磁盘 I/O（Input/Output）。对于内存操作，平衡二叉搜索树已经足够快，但数据库索引通常存放在磁盘（HDD 或 SSD）上。 与 CPU 计算或内存访问相比，从磁盘读取数据慢得不是一个量级。而且磁盘并不是逐字节读取，而是以“块（block）”或“页（page）”为单位（例如 4KB、8KB）读写。二叉搜索树中一个节点承载的数据量很小，树的“高度（深度）”往往很深。树深意味着从根节点到目标叶子节点要经过许多节点，如果每个节点都需要读取不同的磁盘页，就会产生海量的磁盘 I/O，性能急剧下降。

2. B-Tree：把高度和 I/O 压到最低

减少磁盘 I/O 次数的思路很明确：让树的高度尽可能低（浅）。要做到这一点，单个节点就不能只有两个子节点，而要有几十甚至几百个。

这就是 B-Tree 的基本思想。B-Tree 属于「多路树」，特点如下：

  • 一个节点里存多个键（数据）。
  • 把节点大小对齐到磁盘页大小（比如 4KB 或 8KB），一次磁盘 I/O 就能把大量键读进内存。
  • 始终保持完美平衡（所有叶子节点深度相同）。
 graph TD
 Root["[ 40 , 80 ]"]
 Root -- "< 40" --> Child1["[ 10 , 20 , 30 ]"]
 Root -- "40 - 79" --> Child2["[ 50 , 60 , 70 ]"]
 Root -- ">= 80" --> Child3["[ 90 , 100 ]"]

B-Tree 的查找过程

  1. 从磁盘读入根节点。
  2. 在节点内扫描（或二分查找）键数组，找到指向包含目标值的子节点的指针。
  3. 从磁盘读入该指针指向的子节点，重复上述步骤。
  4. 找到目标键后，取出关联的数据（或指向磁盘上真实数据的指针）。

举个例子，假设一棵 B-Tree 的单个节点能容纳 100 个键。 高度为 3（根、中间、叶子）的 B-Tree 就能存下 100×100×100=1,000,000（100 万）条记录。也就是说，在 100 万条记录里找一条目标记录，最多 3 次磁盘 I/O。二叉搜索树的高度约为 20，要产生 20 次 I/O，相比之下这是巨大的改进。

3. B+Tree：RDB 的终极形态

B-Tree 已经是非常优秀的数据结构，但 MySQL（InnoDB）、PostgreSQL 这类现代关系型数据库，索引用的都是 B-Tree 的衍生结构 B+Tree。为什么不用 B-Tree 而用 B+Tree？原因就在于「范围查询」和「顺序访问」的效率高得压倒一切。

B-Tree 与 B+Tree 的区别

B+Tree 在 B-Tree 基础上做了几处关键改动：

  1. 所有数据只存在叶子节点。B-Tree 中，根节点和中间节点也会存真实数据（或指向真实数据的指针）。
  2. B+Tree 的根节点和中间节点只保存「路标（索引键）」，不保存任何真实数据。真实数据全部放在最底层的叶子节点。
  3. 叶子节点之间用双向链表相连。相邻叶子节点互相持有指针，数据可以横向一次遍历到底。
 graph TD
 Root["[ 50 ]"]
 Root --> Node1["[ 25 ]"]
 Root --> Node2["[ 75 ]"]

 Node1 --> Leaf1["[ 10, 20 ]"]
 Node1 --> Leaf2["[ 30, 40 ]"]

 Node2 --> Leaf3["[ 60, 70 ]"]
 Node2 --> Leaf4["[ 80, 90 ]"]

 Leaf1 -- "Next" --> Leaf2
 Leaf2 -- "Next" --> Leaf3
 Leaf3 -- "Next" --> Leaf4

为什么 B+Tree 最适合 RDB

1. 单节点可容纳的键数量（扇出）大幅提升

根节点和中间节点不存实际数据，因此单个节点能放下的“键和指针”数量可以大幅增加。举例来说，假设页大小同为 4KB，B-Tree 因为还要存数据，一个节点可能只能放 50 个键，而 B+Tree 只存键，能放 500 个。树高因此更低，磁盘 I/O 也随之减少。

2. 范围查询速度呈爆炸式提升

数据库里经常要执行 SELECT * FROM users WHERE age BETWEEN 20 AND 30; 这样的范围查询。 用 B-Tree 做这件事，得在树里上上下下反复来回，才能找齐符合条件的数据，产生大量无谓的 I/O。 而 B+Tree 的做法是：

  1. 先从根往下走一遍，找到 age = 20 所在的起始叶子节点。
  2. 之后只需顺着叶子节点之间横向相连的“链表”顺序读下去，直到条件（age &lt;= 30）结束。 磁盘的顺序访问（连续读取）极快，这一特性在磁盘 I/O 上带来的优势是压倒性的。

4. 节点分裂与插入/删除算法

每次增删数据，索引都必须保持平衡。B+Tree 有一套自动维持平衡的算法。

插入与分裂

插入新键时，先按与查找相同的路径找到目标叶子节点，把键加进去。 如果该节点已经满了（达到上限），就会发生节点分裂。

  1. 把满节点的键一分为二，得到两个新节点（或原节点加一个新节点）。
  2. 分裂处居中的键被上提（移动到父节点）。
  3. 如果父节点也满了，父节点同样分裂，分裂会连锁地向上传播。
  4. 分裂最终传到根节点时，会创建一个新的根节点，此时树高增加一层。

通过这种自下而上的构建方式，B+Tree 始终保持“完美平衡”，即到叶子节点的距离（深度）完全一致。

5. 结语

数据库之所以能实现快速查找，靠的正是 B+Tree——它在设计上深刻把握了磁盘 I/O 这一物理瓶颈，并将其降到最低。

  • 把树的“高度”压到极致，用更少的读取次数抵达数据。
  • 将数据集中在叶子节点，提高索引节点的密度。
  • 用链表连接叶子节点，使范围查询能够顺序访问磁盘。

它优化的不只是“算法时间复杂度”，还有“硬件特性（磁盘页访问）”——这正是 B+Tree 几十年来稳坐数据库王座的最大原因。

来源: kenji.blog← 返回首页