解释大名鼎鼎的 B+ Tree

1. 节点 键值 指针 是什么#

好奇 B+ Tree 接近 O(1) 是怎么做到的, 不应该是 像二叉搜索树那样的 就是 lgn 吗, 如果高度很低, 横向数据就很多吧, 不也是需要遍历, 单是横向数据这不就是 O(n) 了吗?

想要了解这些问题, 还是需要了解一下 B+ Tree 的结构

一个节点可以存多个数据, 并不是一个节点只能存一个数据, 非叶子节点, 叶子节点都是这样, 比如下面的描述:

• 一个聚簇索引的叶子节点可以存 200 行数据
• 一个二级索引的叶子节点可以存 200 个主键

也就是说一个节点可以存多个数据, 只是节点种类不同, 索引种类不同(聚簇索引, 二级索引), 存储的数据是不一样的:

• 无论聚簇索引还是二级索引, 非叶子节点存的都是 多个指针 + 多个键值
  • 键值用来与要查询的条件 (比如 id, name) 比较接下来 (下一层) 去哪个指针找下一个节点
  • 指针用来指向子节点 (子页) 的位置
• 叶子节点就有所不同了
  • 聚簇索引的叶子节点存储的是 键值 + 整行数据
  • 二级索引存放键值 + 主键值

注意哪个列的索引, 对应的 B+ Tree 的节点的键值类型, 就是那个列的类型, 比如 name 对应的索引 B+ Tree 每个节点的多个键值的类型肯定是 name, 而聚簇索引是根据 id 建立的 B+ Tree, 所以每个非叶子节点 存的是很多个 id + 指针 这样的数据, 此时 id 是键值:

所以上面我们说: 键值用来与要查询的条件 (比如 id, name) 比较接下来 (下一层) 去哪个指针找下一个节点, 现在可以理解了吧

2. 详细结构介绍#

叶子节点：存储所有键值和数据, 并通过双向链表连接, 便于范围查询

非叶子节点：由"键值"和"指针"组成, 用于导航, 不存储实际数据

• 键值(Key): 用于比较和决策的值
• 指针(Pointer): 指向下一层节点的地址

在一个非叶子节点中, 指针的数量总是比键值的数量多1个, 每个指针指向下一层的一个节点, 非叶子节点在物理结构上是一个连续的数据区域, 其中键值和指针是按特定顺序交替排列的:

[指针P1] [键值K1] [指针P2] [键值K2] [指针P3]

其实指针笔键值多一个很好理解, 比如一个节点有 3 个键值 010, 020, 030, 那数据就有四个范围:

• x < 010
• 010 <= x < 020
• 020 <= x < 030
• 030 <= x

所以需要四个指针来指明 x 在哪个节点上, 通过实际例子解释一下 聚簇索引 B+ Tree 的结构

2.2. PRIMARY KEY 聚簇索引结构#

假设每个页能装 4 行记录（仅用于示意）:

                 (Root, non-leaf page)
                 +------------------+
                 | key=5 | ptr(P2)  |
ptr(P1)----------| key=9 | ptr(P3)  |
                 +------------------+
                    /         \
         +--------------+   +--------------+
         | leaf page P1 |   | leaf page P2 |    ……
         +--------------+   +--------------+

解释

• 非叶子节点 Root 里只保存分隔点 key=5、key=9 以及指向子页的指针

• 叶子节点 P1/P2/P3 按主键顺序链表相连，保存 “键值 + 整行”

查询 SELECT * FROM users WHERE id = 7;

1. 从 Root 读取, 7 > 5 走 ptr(P2)

2. P2 里二分查找, 定位记录 (7,Grace,30)

3. 直接返回整行, 因为行数据就在叶子

聚簇索引和非聚簇索引的结构一样, 只是叶子节点存储的内容不一样, 前者存 键值 + 对应的一整行数据, 后者存 键值 + 主键值

2.2. 二级索引 idx_name 结构#

假设每个页能装 4 行记录（仅用于示意）：

             (Root, non-leaf)
             +--------------------+
             | key=Bob | ptr(S2)  |
ptr(S1)------| key=Helen| ptr(S3) |
             +--------------------+

查询 SELECT age FROM users WHERE name = 'Grace'; 步骤

1. 从 idx_name.Root 读，‘Grace’ > ‘Bob’ 且 < ‘Helen’ 走 S2
2. 在 S2 找到条目 (‘Grace’, 7)
3. 拿到主键 id=7，用它去聚簇索引 Root，再走 P2，然后定位 (7,Grace,30)
4. 取出 age=30

2.3. 决策流程总结#

优先检查能否用索引：

• 查询包含 WHERE id = ? → 使用聚簇索引
• 查询 WHERE name = ? → 使用 idx_name，然后回表

执行器根据统计信息估算成本，再选择走哪个索引（或全表扫）, 一旦选定索引，引擎从 Root 开始，逐层比较键值直到叶子, 如果是二级索引，还需拿到主键，按同样 B+ 树规则走聚簇树

3. 叶子节点是双向连表的优势#

假设我们有一个订单表orders，包含订单ID、客户名、订单日期和金额：

orders(order_id, customer_name, order_date, amount)

其中 order_id 是主键，在 order_date 上创建了索引:

(1, '张三', '2023-01-15', 100)
(2, '李四', '2023-02-20', 200)
(3, '王五', '2023-03-10', 150)
(4, '赵六', '2023-03-15', 300)
(5, '钱七', '2023-04-05', 250)

在B+ Tree索引结构中，order_date 索引的叶子节点可能如下所示:

[2023-01-15, ID=1] <-> [2023-02-20, ID=2] <-> [2023-03-10, ID=3] <-> [2023-03-15, ID=4] <-> [2023-04-05, ID=5]

这些节点通过双向链表连接, 每个节点都有指向前一个和后一个节点的指针,

范围查询 假设我们需要查询3月份的所有订单:

SELECT * FROM orders WHERE order_date BETWEEN '2023-03-01' AND '2023-03-31';

数据库会：

• 通过B+树索引结构找到第一个满足条件的叶子节点（‘2023-03-10’）
• 然后沿着链表顺序遍历，直到找到超出范围的节点
• 无需回到树的上层节点再向下查找

如果没有双向链表, 每找到一个节点都需要从根节点重新遍历, 效率会大大降低

排序查询 执行如下排序查询

SELECT * FROM orders ORDER BY order_date;

由于叶子节点已经按 order_date 排序并通过链表连接, 数据库只需按链表顺序读取即可, 无需额外排序步骤

分页查询 当执行分页查询时：

SELECT * FROM orders ORDER BY order_date LIMIT 2, 2;

数据库可以：

• 找到排序起始位置
• 跳过前2条记录
• 沿着链表读取接下来的2条记录

全表扫描 如果需要全表扫描，可以从第一个叶子节点开始，沿着链表顺序读取所有数据，这种顺序访问比随机访问磁盘更高效

4. 为什么索引查询速度接近 O(1)#

有人分析说 因为 B+ Tree 树的高度很低, 一般都是 3~4, 所以 I/O 次数 只有 3 ~ 4 次, 接近常数 1, 可是我认为, B+ Tree 不像 二叉搜索树那样, 只有每个节点只有两个子节点, 有可能会有多个节点, 比如 100 个, 这没关系, 因为每个节点页都由上层 的节点 通过指针指出, 可是每个节点也就是数据页可能会有多个数据啊, 比如 100 个, 这个时候 定位数据, 复杂度不应该是 O(n) 吗?

4.2. 公式推导#

一次查找包含两个独立成本

记号

• m = 分叉因子（一个非叶子能容纳的最大子页数）
• N = 总记录行数

假设

• 页大小 = 16 KB

• 非叶子节点：每条索引条目 24 B（键 + 子页号）

  • 每页可容纳 ⌊16384 / 24⌋ ≈ 680 个分叉，即 m ≈ 680

• 叶子节点：每条索引项 40 B（键 + 主键）

  • 每页 ≈ 400 条记录

计算树高 h $$ h = \lceil \log_{m}(N) \rceil $$

• N (行数)

• h (向上取整)

• N 从 10⁶ ➜ 10¹⁰ 扩大一万倍，h 只从 3 ➜ 4
• 若页缓存命中，步骤 A 甚至是 0 次磁盘 I/O，仅 CPU 比较

节点内比较成本

• 线性查找：≤ 680 次比较

• 二分查找：⌈log₂ 680⌉ ≈ 10 次比较

在现代 CPU 上比较 10~680 个整数几乎可忽略, 于是总体壁钟时间看起来几乎不随 N 增长，这就是「接近 O(1)」的直观感受

壁钟时间是程序运行的“真实世界时间”, 而这里强调它几乎不受 N 影响, 直观上接近常数时间复杂度,

4.2. 实际数据比较#

我们来比较一下 做一次随机磁盘 IO + 把数据页拷贝进内存 的时间 和 CPU 比较一次的耗时做对比:

• 即使换成 NVMe，随机 I/O 仍比 CPU 比较慢四个数量级
• 因此决定查询延迟的第一因素仍是“要做几次随机 I/O”
• B⁺Tree 通过把分叉数 m 做到几百，使树高 h≤3–4，从而把“随机 I/O 次数”限制到 3–4 次——这远比 “页内要比较多少键” 重要

为什么复杂度推导 没有包括 叶子页找目标记录的开销

在 O(log N) 级别推导中, 页内比较最多几百次, 比一次 I/O 快万倍, 可忽略不计

有人可能会问 你把 在存储介质 一次随机 I/O 耗时 与 CPU 比较一次耗时 进行比较准确吗?

一次磁盘随机 I/O 耗时 不应该加上从内存读取数据的时间吗, 因为数据加载的过程, 是把该节点的整个数据页加载进内存, 然后再比较数据,

下面把 一次磁盘随机 I/O 到真正完成键值比较 所经历的全部路径拆开, 给出各阶段的量级, 看看 磁盘→内存→CPU 各环节到底谁是瓶颈, 为便于对比, 以一次读取 16 KB InnoDB 页为例:

数值按公开硬件数据取近似中位数, 偏差 1–2 倍不影响量级结论, 结论

• 随机 I/O 的主耗时就是 设备端寻址 + 媒体读出（A+B）

• 对机械盘：> 99 % 的时间耗在磁头定位和旋转等待（A）

• 对 SSD：A 仍是大头，只是毫秒级→微秒级

• DMA + 内存拷贝（C+D）加起来只是几个微秒，机械盘情况下占比 < 0.1 %

  • 因此前面的表格 磁盘 IO 时间 5 ms / 100 µs / 20 µs 这种 “磁盘随机 I/O 耗时” 通常已经把拷贝进内存的时间统合在内；再细分也不改变大局——I/O 仍比内存-CPU 操作慢三个以上数量级

• 页内比较（E）只有几十纳秒；即便连带一次 L1→L2 缓存失效也就是百纳秒量级, 和微秒～毫秒的 I/O 相比同样可以忽略

• 如果页已在 Buffer Pool（只需 D+E）：总耗时约 5 µs，比 NVMe 随机 I/O 快 3～4 倍，比机械盘快千倍；此时查找延迟主要是 CPU-DRAM 以及锁、版本检查等开销

所以说 “数据库查找最贵的是随机 I/O” 是对的: 只要页不在内存，I/O 时间会压倒后续所有 CPU 计算

在数据库查询中, 磁盘随机 I/O 操作是最耗时的部分, 而不是单纯的计算次数, B-Tree 的每一层对应一次磁盘 I/O, 而高度低意味着 I/O 次数少, 只要页不在内存, I/O 时间会压倒后续所有 CPU 计算, 因为 CPU 比较数据 & 内存拷贝视为“几乎免费”在数量级上是成立的, B⁺ Tree 之所以追求低树高, 就是为了把这个昂贵的随机 I/O 次数从 O(log N) 压到 3–4 次, 之后页内二分或线性扫描的优化相对只是“锦上添花”

5. 页的概念是什么意思#

5.1. 什么是页（Page）#

在 InnoDB（MySQL 8.x 默认存储引擎）里, 页是磁盘与内存之间读写的最小物理单元

• 任何数据（表、索引、Undo、字典等）都被切成若干页来管理
• 数据库一次随机 I/O 最多只把一个完整页搬到 Buffer Pool，随后对该页里的记录做 CPU 运算

页的大小

5.2. 页里存放什么？#

以一页 “索引页（INDEX PAGE，类型 0x45BF）” 为例

+----------------------+  0     ← file offset
| File Header (38 B)   |
| Page Header (56 B)   |
| Infimum / Supremum   | 伪记录做边界
| User Records ...     | 按主键或二级索引键有序
| Free Space           | 插入时向中间填充
| Page Directory       | 每 128 条插一槽，向下增长
| File Trailer (8 B)   |
+----------------------+ 16384  ← 16 KB

• User Records：真正的行记录或索引条目
• Page Directory：偏移量数组，用来做二分搜索
• Header 包括页号、上一页/下一页指针、校验值、空闲链等元数据

5.3. 页与 B⁺Tree节点的关系#

所以常听到“树高 = 3～4 页深”本质上是“从根页经 3～4 次指针跳到目标叶子页”