在数据库里，“索引”两个字常常与“性能”同义。而在所有索引类型中，B-Tree（Balanced Tree，平衡树）无疑是最常见、也是最容易被误解的一种。本文将结合 Oracle 的实现，带你把 B-Tree 的逻辑结构、存储细节、与 NULL 的恩怨、以及优化器如何决定是否用它，一次性讲透。
二、B-Tree 的逻辑长什么样？
- 两类块 • 分支块（Branch Blocks）：只存“指路”信息，保存最小前缀键，告诉你向左还是向右。 • 叶块（Leaf Blocks）：真正存“值”，每条记录是 (Key, RowID) 二元组，并且 双向链表 把所有叶块串起来，方便顺序/逆序扫描。
- 一张脑图就够
[Root Branch]
/ \
[Branch A] [Branch B]
/ \ / \
Leaf1 Leaf2 Leaf3 Leaf4
(1-10) (11-19) (20-25) (26-30)
Leaf1 ↔ Leaf2 ↔ Leaf3 ↔ Leaf4 通过指针双向链接，范围扫描时无需再回根节点。
三、物理存储：顺序 ≠ 物理连续
- 块在段里随意“散落” 逻辑上 Leaf1 → Leaf2 → Leaf3 是顺序的，物理上它们可能一个在头、一个在尾。因此 有序索引扫描 只能单块 I/O：读一块 → 通过指针找下一块 → 再读。
- 块内部也不是“排排坐” • 条目真正存在 堆 里，谁先来谁先占坑。 • 但行头数组按 Key 顺序记录了指针，扫描时先看行头，再定位条目，避免把整块条目都读一遍。
四、唯一索引 vs 非唯一索引
| 类型 | 键内容 | 排序规则 | 例子 |
|---|---|---|---|
| 唯一索引 | 仅 Key | Key 升序 | 0, 1, 2 … |
| 非唯一索引 | Key + RowID（附加长度字节） | 先 Key 升序，再 RowID 升序 | 0,AAAP… 0,AAAP… 2,AAAP… |
一句话：非唯一索引靠把 RowID “挤”进键里来保证唯一性。
五、B-Tree 与 NULL：最熟悉的陌生人
规则：B-Tree 不存全 NULL 键。 后果：
- 单列索引
CREATE INDEX idx ON t(col)永远过滤掉col IS NULL的行。 - 优化器面对
SELECT col FROM t WHERE col IS NULL只能全表扫； 面对SELECT col FROM t WHERE col = 10才能愉快地走索引； 面对SELECT col FROM t WHERE col IS NOT NULL也能走 INDEX FULL SCAN，因为非 NULL 行都在叶块里。
六、实战：三条 SQL 看穿优化器心思
- 全表扫 —— 因为 NULL 行可能漏掉
EXPLAIN PLAN FOR
SELECT department_id FROM employees;
-- 执行计划：TABLE ACCESS FULL
- 精准命中 —— 等值查询，非 NULL 行都在索引
EXPLAIN PLAN FOR
SELECT department_id FROM employees WHERE department_id = 10;
-- 执行计划：INDEX RANGE SCAN
- 排除 NULL 后，索引全覆盖
EXPLAIN PLAN FOR
SELECT department_id FROM employees WHERE department_id IS NOT NULL;
-- 执行计划：INDEX FULL SCAN (不需要回表)
七、最佳实践
| 场景 | 建议 |
|---|---|
大量 IS NULL 过滤 | 考虑函数索引 / 位图索引 / 反范式标记列 |
| 唯一约束 | 用唯一索引，节省 RowID 存储，减少长度字节 |
| 范围查询 & 排序 | 让 WHERE 列、ORDER BY 列与索引列顺序匹配，充分利用叶块双向链表 |
| 复合索引 | 把可能为 NULL 的列放后面，避免整行被“踢出”索引 |