树：从层次结构到 B+ 树索引¶
覆盖：树为何存在、二叉树与遍历、BST、B-Tree/B+ 树与数据库索引；与 数组、哈希表 对照 适用：Day 3 专题深读，或复习 DDIA Ch.3 B-Tree 时对照 方法：5W1H（为什么学、学什么、何时用、在哪用、谁在用、怎么用）
← 返回 总览 | 数组 | 哈希表 | DDIA Ch.3 存储与检索 | 7 天冲刺 Day 3
读前须知：这篇在讲什么？¶
复习 B-Tree 时，很多人卡在：
- 树：和「二叉树刷题」是一回事吗？
- BST：为什么中序遍历是有序的？
- B-Tree / B+ 树：和内存里的红黑树、MySQL 索引是什么关系？
- 选型：什么时候不用哈希、要用树？
下面按 直觉 → 二叉树（面试）→ BST → B+ 树（工程/DDIA）→ 对照表 → 模板 → 刷题 写。
你正在复习 B-Tree：优先看 §0、§四、§五，二叉树题再回看 §二、§三。
§0 先用生活例子建立直觉¶
0.1 树是什么？¶
数组 / 链表：一排或一串，只有「前一个 / 后一个」关系。
树：每个节点可以有多个「孩子」，天然表示 层级：
公司 CEO
/ \
技术 VP 产品 VP
/ \ |
后端组 数据组 产品一组
- 根（root）：最上面，只有一个
- 父 / 子：上下级
- 叶子（leaf）：没有孩子的节点
- 深度 / 高度：从根到某节点的层数
为什么需要树：文件目录、组织架构、DOM、分类菜单——都不是「一条线」能舒服表达的。
0.2 二叉树 vs 二叉搜索树（BST）vs B-Tree（别混）¶
| 名字 | 约束 | 主要用途 |
|---|---|---|
| 二叉树 | 每个节点最多 2 个孩子 | 遍历、递归、DP 载体 |
| BST | 左 < 根 < 右，递归定义 | 有序、查找 O(log n)（平衡时） |
| B-Tree / B+ 树 | 多路平衡、节点多个 key、磁盘页友好 | 数据库索引、范围查询 |
二叉树：只规定「最多两个孩子」
BST： 还规定「左边都比根小，右边都比根大」
B+树： 一棵很「胖」的树，一层对应磁盘一页，叶子串成链表
0.3 和数组、哈希表怎么选？（一句话）¶
| 需求 | 更合适 |
|---|---|
| 按下标访问、连续扫描 | 数组 |
| 按 key 点查、计数、分组（无序） | 哈希表 |
| 层次关系、第 K 小、范围 [a,b]、有序遍历 | 树 |
| 海量追加写、日志型 | LSM（见 DDIA Ch.3） |
树的核心卖点：在 有序 前提下，查找 / 范围 / 顺序遍历 都是 O(log n) 量级（平衡树）。
一、为什么需要树？（Why）¶
1.1 线性结构的局限¶
| 结构 | 查找 | 表达层级 |
|---|---|---|
| 无序数组 | O(n) | ❌ |
| 有序数组 + 二分 | O(log n) 查找，插入 O(n) | ❌ |
| 链表 | O(n) | ❌ |
| 哈希表 | O(1) 平均点查，无序、无范围 | ❌ |
树：插入 + 查找都可做到 O(log n)（平衡时），还能 中序遍历得到有序序列，还能表达父子层级。
1.2 历史脉络（简表）¶
| 阶段 | 内容 |
|---|---|
| 数学 | 树、图论很早就有 |
| 1960s | BST 作为抽象数据结构研究 |
| 1970s | B-Tree（Bayer & McCreight），为 磁盘块 设计 |
| 工程 | B+ 树成为 MySQL InnoDB、PostgreSQL 等索引主流 |
B-Tree 动机：磁盘一次读 一整页（如 16KB），希望一次 I/O 里尽量多 key、少指针跳转；二叉树太「瘦」，层数深，I/O 次数多。
二、二叉树（面试主战场）¶
2.1 四种遍历 — 各干什么¶
对同一棵树：
1
/ \
2 3
/ \
4 5
| 遍历 | 顺序 | 记忆 | 典型用途 |
|---|---|---|---|
| 前序 | 根 → 左 → 右 | 1,2,4,5,3 | 复制树、序列化前缀 |
| 中序 | 左 → 根 → 右 | 4,2,5,1,3 | BST 得有序序列 |
| 后序 | 左 → 右 → 根 | 4,5,2,3,1 | 删树、算子树信息（直径、路径和） |
| 层序 | 按层 BFS | [[1],[2,3],[4,5]] | 最短层数、右视图 |
BST 中序有序的原因：左子树全小于根，右子树全大于根 → 递归下去全局有序。
2.2 递归三要素（每道树题都套）¶
- 终止：
node == null返回什么（0、true、null） - 递归：左、右子树各返回什么
- 合并：当前节点如何用左右结果（max、加、判断）
三种模式（7 天冲刺 同款）：
| 模式 | 信息流向 | 例子 |
|---|---|---|
| 自顶向下 | 根传参到叶 | 最大深度、路径和 |
| 自底向上 | 叶汇总到根 | 直径、最大路径和 |
| 判断型 | 整棵树是否满足条件 | 验证 BST、对称树 |
2.3 手把手：验证 BST（LC 98）¶
不能只看「左孩子 < 根 < 右孩子」，要 整条左子树 < 根 < 整条右子树。
5
/ \
1 6
/ \
4 7 ← 4 在右子树但 < 5，非法
做法：DFS 带区间 (lo, hi)，到节点时检查 lo < val < hi，再传给左右子树。
boolean isValidBST(TreeNode root) {
return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
boolean dfs(TreeNode n, long lo, long hi) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return dfs(n.left, lo, n.val) && dfs(n.right, n.val, hi);
}
2.4 层序遍历（LC 102）— BFS 模板¶
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // 当前层节点数
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
ans.add(level);
}
return ans;
}
关键：for (int i = 0; i < size; i++) 用 当前队列长度 卡一层，不要 while (!q.isEmpty()) 里无界 poll。
三、二叉搜索树（BST）¶
3.1 操作与复杂度（平衡时）¶
| 操作 | 平均 |
|---|---|
| 查找 | O(log n) |
| 插入 | O(log n) |
| 删除 | O(log n) |
| 中序遍历 | O(n) 且 有序 |
退化：按 1,2,3,4… 顺序插入 → 变链表 → O(n)。工程用 AVL、红黑树 保持平衡；Java TreeMap 底层红黑树。
3.2 第 K 小（LC 230）¶
中序遍历第 K 个就是答案；或 BST 上「左子树 size + 1」走左/右。
四、B-Tree 与 B+ 树（你在复习的重点）¶
和 DDIA Ch.3：B+Tree 与 LSM 对照 对照阅读。
4.1 解决什么问题？¶
| 痛点 | B-Tree 思路 |
|---|---|
| 二叉树索引层数太深 | 每个节点存 很多 key（多路），树变矮 |
| 磁盘按 页 读写 | 一个节点 ≈ 一页，一次 I/O 读一整节点 |
范围查询 WHERE id BETWEEN … |
叶子链表 顺序扫（B+ 树） |
不是面试里手写的那种「每个节点只有 2 个孩子」的二叉树，而是 多路平衡树。
4.2 B-Tree vs B+ 树（记差异）¶
| B-Tree | B+ 树（InnoDB 常见） | |
|---|---|---|
| 数据存在哪 | 非叶节点也可能存 value | 只在叶子存行/指针 |
| 叶子 | 无链表 | 叶子串成双向链表 |
| 范围扫描 | 一般 | 极强（沿叶子链扫） |
| 单点查 | 可能在上层结束 | 通常要到叶子 |
[10 | 20 | 30] ← 非叶：只存 key（或 key+指针）
/ | \
[...] [...] [10→row][20→row][30→row] ← 叶子：数据 + 链表 →
4.3 和 LSM、哈希 怎么选（复习 DDIA 时用）¶
| 结构 | 写入 | 点查 | 范围查询 | 典型 |
|---|---|---|---|---|
| 哈希 | 快 | O(1) | ❌ | Redis、哈希索引 |
| LSM | 顺序写快 | 可 | 一般 | RocksDB |
| B+ 树 | 随机页更新 | O(log n) | 强 | MySQL InnoDB |
计费 / OLTP：按订单号查 + 按日期范围报表 → B+ 树索引非常常见。
纯埋点灌库：更偏 LSM / 列存 merge，不是经典 B+ 树 OLTP 模型。
4.4 为什么数据库少用「二叉」红黑树做磁盘索引？¶
- 二叉树 扇出小（每个节点 2 路）→ 同样 key 数量 层数高 → 磁盘 I/O 次数多
- B+ 树 扇出大（一页塞几百 key）→ 层数低 → 3～4 层 就能存亿级索引（量级直觉）
红黑树仍重要：内存里（TreeMap、Java 8 哈希桶树化），不是磁盘主索引形态。
4.5 MVP 直觉：B+ 树查找（伪代码）¶
// 教学用：多路查找，不涉及页分裂/合并
Record search(BPlusNode root, int key) {
BPlusNode node = root;
while (!node.isLeaf) {
int i = 0;
while (i < node.keys.size() && key >= node.keys.get(i)) i++;
node = node.children.get(i); // 落到下一层
}
// 叶子：沿链表或页内二分找 key
return node.findInLeaf(key);
}
分裂 / 合并：插入满页 → 分裂；删除导致页太空 → 合并或借位 —— 实现细节交给数据库，理解 保持平衡 + 页满 即可。
五、刷题 / 工程怎么选？（决策树）¶
拿到「树」相关题或需求
│
├─ 题目给的是 TreeNode，问深度/路径/对称/构造？
│ └─ 【二叉树 + 递归 / BFS】§二
│
├─ 要求有序、第 K 小、验证 BST？
│ └─ 【BST + 中序 / 区间 DFS】§三
│
├─ 讨论 MySQL 索引、范围查询、磁盘？
│ └─ 【B+ 树】§四，对照 DDIA
│
├─ 只要 key 存在不存在、频次、分组？
│ └─ 优先 【哈希表】，不是树
│
└─ 连续下标、子数组子串？
└─ 【数组】技巧，不是树
| 技巧 | 一句话 | 代表题 |
|---|---|---|
| DFS 前/中/后序 | 递归遍历 | 94, 226, 114 |
| BFS 层序 | 队列按层 | 102, 199 |
| 自底向上 DFS | 子树信息汇总 | 543, 124 |
| BST 中序 / 区间 | 有序与验证 | 98, 230 |
| 构造树 | 前+中 / 后+中 + 哈希下标 | 105, 106 |
六、核心模板（Java）¶
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { val = v; }
}
// 1. 前序 DFS
void preorder(TreeNode root, List<Integer> out) {
if (root == null) return;
out.add(root.val);
preorder(root.left, out);
preorder(root.right, out);
}
// 2. 中序 DFS（BST 有序）
void inorder(TreeNode root, List<Integer> out) {
if (root == null) return;
inorder(root.left, out);
out.add(root.val);
inorder(root.right, out);
}
// 3. 最大深度（自顶向下）
int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// 4. 直径（自底向上，后序思想）
int diameter(TreeNode root) {
int[] ans = new int[1];
height(root, ans);
return ans[0];
}
int height(TreeNode n, int[] ans) {
if (n == null) return 0;
int L = height(n.left, ans);
int R = height(n.right, ans);
ans[0] = Math.max(ans[0], L + R);
return Math.max(L, R) + 1;
}
// 5. 最近公共祖先（一般二叉树）
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode L = lowestCommonAncestor(root.left, p, q);
TreeNode R = lowestCommonAncestor(root.right, p, q);
if (L != null && R != null) return root;
return L != null ? L : R;
}
七、必刷题目（15 题）¶
| 优先级 | 题目 | 技巧 |
|---|---|---|
| ⭐⭐⭐ | 102 层序遍历 | BFS |
| ⭐⭐⭐ | 104 最大深度 | DFS |
| ⭐⭐⭐ | 226 翻转二叉树 | DFS |
| ⭐⭐⭐ | 98 验证 BST | 区间 |
| ⭐⭐⭐ | 230 BST 第 K 小 | 中序 |
| ⭐⭐⭐ | 236 最近公共祖先 | DFS |
| ⭐⭐⭐ | 543 直径 | 后序型 |
| ⭐⭐⭐ | 124 最大路径和 | 后序型 |
| ⭐⭐⭐ | 105 前中构造二叉树 | 递归+哈希 |
| ⭐⭐ | 101 对称二叉树 | DFS |
| ⭐⭐ | 114 展开为链表 | 前序 |
| ⭐⭐ | 199 右视图 | BFS/DFS |
| ⭐⭐ | 112 路径总和 | DFS |
| ⭐⭐ | 437 路径总和 III | 前缀和+DFS |
| ⭐⭐ | 297 序列化与反序列化 | BFS/DFS |
八、小结（背这几句）¶
| 主题 | 记住这一句 |
|---|---|
| 树为何存在 | 表达 层级；在有序前提下 O(log n) 查找与范围 |
| 二叉树 | 面试载体；四种遍历 + 递归三模式 |
| BST | 左 < 根 < 右；中序 = 有序；平衡才 O(log n) |
| B+ 树 | 磁盘索引；多路、矮树、叶子链表 扫范围 |
| 和哈希 | 哈希点查快无序；树要 有序 / 范围 / 第 K 小 |
| 和 LSM | LSM 写多读少追加；B+ 树 读多、范围、行级更新 |
复习 B-Tree 时：先画「根 → 非叶 key → 叶子数据+链表」，再对照 DDIA Ch.3 B+Tree 与 框架总览。
刷题口诀：
TreeNode+ 深度/路径/对称 → DFS/BFS- 有序 / 第 K 小 / 验证 → BST + 中序或区间
- 数据库索引 / 范围 → B+ 树，不是二叉
若仍懵：在纸上画一棵 4 节点的 BST，手写中序结果，再画一层「一页 3 个 key」的 B+ 树节点。