[!info] related notes

• 所属 MOC：数据库 MOC
• 前置：数据库 Page 与 Buffer Pool
• 后续：聚簇索引与二级索引、联合索引与覆盖索引
• 优化：索引选择性、基数与代价

B+Tree 数据库索引

[!abstract] 一句话定义 B+Tree 是面向外存 Page 访问设计的多叉平衡搜索树：内部节点主要导航，叶子保存最终索引项并按 Key 有序组织。高扇出让树很矮，因此等值查询只需少量 Page 跳转，范围查询还能连续扫描叶子。

为什么数据库关心 Page I/O

CPU comparison: cheap
random storage Page access: much more expensive

数据库优化目标不是只减少比较次数，而是尽量减少从 Root 到 Leaf 的 Page 数量，并让后续访问更连续。

高扇出为什么重要

一个内部 Page 只保存紧凑的：

separator key + child page pointer

所以能容纳大量 Child：

                 [10 | 40 | 80 | ...]
              /       |       |       \
          child     child   child     child

large fan-out
→ low height
→ few Page reads

二叉树每个节点只有两个 Child，面对磁盘 Page 时会更深、随机跳转更多。

内部节点与叶子节点

内部节点

用于选择下一层 Child，不保存完整业务行，从而提高 Fan-out。

叶子节点

保存最终索引项，可能是：

• Key + 完整行；
• Key + 主键；
• Key + Tuple / Row Locator；
• Key + Included Columns。

具体取决于数据库和索引类型，见 聚簇索引与二级索引。

等值查询

Root Page
→ compare separator keys
→ Internal Page
→ Leaf Page
→ locate key / row reference

Root 和上层 Page 往往长期驻留内存，实际物理 I/O 可能更少，但逻辑访问路径仍存在。

范围查询

叶子按 Key 有序，数据库定位起点后可以向后扫描：

WHERE created_at >= ? AND created_at < ?
ORDER BY created_at

seek first matching leaf entry
→ scan consecutive entries / leaf pages
→ stop at upper bound

这也是 B+Tree 相比 Hash Index 的重要优势。

为什么不是 Hash Index

Hash 适合等值定位，但通常不保留 Key 的全序，因此不自然支持：

• Range；
• Prefix Order；
• ORDER BY；
• Min / Max；
• 有序遍历。

某些数据库会为特定场景提供 Hash Index，但通用默认索引仍多使用 B-tree 家族。

为什么不直接用红黑树 / AVL

红黑树和 AVL 适合内存中细粒度节点访问；每个节点只有少量 Child，树高更大。B+Tree 让一个 Page 承载大量 Key，设计目标直接对齐 Block I/O。

B+Tree 与 B-Tree

术语在教材与数据库实现中可能略有差异。稳定理解是：

• B-tree 家族都是多路平衡树；
• 数据库常让内部节点偏导航、叶子承载最终索引项；
• 叶子有序扫描支持范围查询；
• 具体是否链表连接、哪些值出现在内部节点，应以实现为准。

不要因为命名差异忽略 Page、Fan-out 和范围扫描这三个核心机制。

Insert、Split 与写入成本

目标 Leaf 有空间时直接插入；Page 满时可能：

split page
→ redistribute entries
→ insert separator into parent
→ parent may split recursively

影响：

• 额外 Page Write；
• WAL / Redo；
• Cache 与锁竞争；
• Fragmentation；
• 随机 Key 比顺序 Key 更容易打散局部性。

Fill Factor 等参数可用空间换减少未来 Split，但不是越低越好。

B+Tree 不会让所有查询都快

仍然取决于：

• Query 是否能形成连续 Key Range；
• 选择性；
• 是否需要大量回表；
• 排序和过滤能否利用索引顺序；
• 统计信息；
• 写入和维护成本。

“有索引”不等于优化器一定选择它。

面试回答

数据库通常按 Page 做 I/O。B+Tree 的内部节点只放 Key 和 Child Pointer，一个 Page 能容纳很多分支，所以 Fan-out 高、树高低，从 Root 到 Leaf 只需少量 Page 访问；叶子又按 Key 有序，定位起点后可以连续做范围扫描。相比二叉树它更适合块存储，相比 Hash 又支持 Range 和 Order，因此成为关系型数据库通用索引结构。

掌握标准

• Page I/O 与高 Fan-out；
• 内部节点和叶子的分工；
• 等值查询与范围扫描路径；
• 与 Hash、红黑树的取舍；
• Page Split 和写放大；
• 为什么有 B+Tree 索引仍可能不使用。

Related notes

• 数据库 Page 与 Buffer Pool
• 联合索引与覆盖索引
• 索引选择性、基数与代价