Theory · Data Structure · Balanced Tree
给 BST 按住高度：严格平衡（AVL）· 松弛规则（红黑）· 磁盘友好（B+）—— 内存与磁盘两套平衡哲学
平衡因子 |BF|≤1，四种旋转修复——查询最快、写最贵
五条性质把高度按在 2log n 内，旋转 ≤3 次——工程默认
一节点一磁盘页、扇出 1170、3 层 2000 万行——数据库索引之王
The Degeneration Problem
随机插入时期望 h≈O(log n)，但有序输入直接退化成链表：1,2,3,…,n 依次插入，h=n，查找变 O(n)。生产环境不会给你随机数据。
① 强制高度差：每步维护 |BF|≤1（AVL）——平衡严格、查询快；② 松弛染色规则：不盯高度，用红黑五性质把高度夹在 2log n 内（红黑）——维护便宜、写快。
磁盘上一次 IO = 10ms 级、一次内存比较 = 纳秒级——树高即 IO 次数。于是放弃二叉、放大扇出到千级：B/B+ 树 3 层装下 2000 万行。
所有平衡树的本质都是同一句话：用插入/删除时的局部调整，换查询时全局的高度上界。
| 结构 | 高度上界 | 调整代价 |
|---|---|---|
| 裸 BST | O(n)（有序输入） | — |
| AVL | 1.44 log n | 插入 ≤2 旋，删除 O(log n) 旋 |
| 红黑树 | 2 log(n+1) | 插入 ≤2 旋，删除 ≤3 旋 |
| B+ 树（阶≈千） | 3~4 层（千万行） | 节点分裂/合并，逐层上传 |
AVL · Four Rotations
AVL · Height Bound & Trade-off
每个节点 |BF| ≤ 1。插入沿路径更新高度，第一个失衡点做一次（双）旋转后整棵树恢复——因为旋转把子树高度还原到插入前的值。
最"瘦"的 AVL 树是斐波那契形状：N(h) = N(h−1) + N(h−2) + 1 节点，解得 h ≤ 1.44 log₂n。比 log n 多 44% 常数，换来了"查询路径最短"。
删除可能让多个祖先依次失衡，要一路回溯到根，最坏 O(log n) 次旋转——这是 AVL 输给红黑树的核心点。
查询远多于写、且对查询延迟敏感（如内存索引、语言教学实现）。工程库极少内建 AVL——红黑的"维护便宜"通常更值钱。
| 指标 | AVL | 红黑树 |
|---|---|---|
| 平衡严格度 | |BF|≤1（严格） | 高 ≤ 2log(n+1)（松弛） |
| 查询 | 略快（更矮） | 稍慢 |
| 插入旋转 | ≤ 2 次 | ≤ 2 次 |
| 删除旋转 | O(log n) 次 | ≤ 3 次 |
| 维护开销 | 存高度/平衡因子 | 1 bit 颜色 |
| 库内地位 | 教学/专用品 | 工业默认 |
Red-Black Tree · Five Invariants
Black Height · Why 2 log n
① 性质⑤：任一节点到叶的路径黑数相同，记黑高 bh；
② 最短路径 = 全黑 = bh 长；最长路径红黑相间 = 2bh 长 → 最长 ≤ 2×最短；
③ 黑高 bh 的子树至少含 2^bh − 1 个节点（归纳：每层黑数翻倍）→ n ≥ 2^bh − 1 → bh ≤ log₂(n+1) → 高 ≤ 2log₂(n+1)。
红黑树不追求最矮（AVL 的 1.44），只追求常数因子内的有界——2 倍以内的路径差，配合"调整便宜"，总体赢。
插入新节点染红（不破坏黑高，只可能违反④红红）；红红冲突看叔叔：叔红 → 变色上推；叔黑 → 旋转+变色，一次终结。插入最多 2 次旋转。
删黑节点会破坏黑高，需要"双黑"修补，情况多但旋转 ≤ 3 次——这是红黑对 AVL 的决定性优势。
// 插入修复核心（伪代码直觉） for cur != root && cur.parent.red { if uncle.red { // 叔红：变色，冲突上推两层 parent.black = uncle.black = true grandparent.red = true cur = grandparent } else { // 叔黑：旋转 + 变色，终结 rotate & recolor break } } root.black = true
Red-Black In The Wild
Java TreeMap / TreeSet、HashMap 的树化桶（链长 ≥8 转 红黑，哈希 deck）；C++ std::map / set / multimap——有序容器几乎都是红黑。
CFS 调度器（按 vruntime 排序取最左节点）、epoll（红黑树管理监听 fd）、虚拟内存区域 vma 管理、ext4 的 extent 缓存——内核的"有序集合"默认答案。
nginx 定时器（红黑树取最近到期）、Java ConcurrentHashMap 1.8 树化桶。共同点：有序 + 高频插入删除 + 最坏情形有界。
标准库没有平衡树（map 走哈希、有序需求交给排序 slice 或第三方）——面试可答"Go 的哲学是组合最小原语"，并引到 跳表 与 堆 这两个"特化替代"。
| 场景 | 为什么是红黑树 |
|---|---|
| TreeMap / std::map | 有序遍历 + O(log n) 稳定 |
| HashMap 树化 | 哈希最坏 O(n) → O(log n) 兜底 |
| CFS 调度 | 每次取 vruntime 最小 = 最左节点 O(log n) |
| epoll fd 管理 | 注册/删除高频 + 按 fd 有序 |
| 内核 vma | 按地址区间有序查找 |
B+ Tree · Disk-Friendly
Why B+ Tree Wins On Disk
| 维度 | B+ 树 | B 树 | 红黑树 |
|---|---|---|---|
| 数据位置 | 全在叶子，非叶纯导航 | 所有节点都存数据 | 每节点一份数据 |
| 扇出 | ≈1170（16KB 页 ÷ 14B 项） | 较小（内点要放行数据） | 2 |
| 千万行树高 | 3 层（3 次 IO） | 更高 | ≈23 层 = 23 次 IO |
| 范围查询 | 叶子链表顺序扫 | 中序回溯父节点 | 中序遍历（跳跃指针） |
| 查询稳定性 | 每次到叶，耗时一致 | 可能在非叶命中 | 一致 |
等值查询 O(1) 很香，但不支持范围、排序、最左前缀——WHERE age > 18 在哈希里只能全表扫。InnoDB 有自适应哈希（热点页缓存），但主索引永远是 B+树。
Selection Cheat Sheet
| 结构 | 查找 | 插入/删除 | 范围查询 | 介质与场景 |
|---|---|---|---|---|
| 有序数组 + 二分 | O(log n) | O(n) | ✓ 二分端点 | 静态数据；只读近乎完美 |
| AVL | O(log n) 最快常数 | O(log n) 旋转多 | ✓ 中序 | 内存 · 读多写少 |
| 红黑树 | O(log n) | ≤3 旋转，最便宜 | ✓ 中序 | 内存 · 通用库/内核默认 |
| 跳表 | O(log n) 期望 | O(log n)，实现极简 | ✓ 底层链表 | 内存 · Redis zset（跳表 deck） |
| 堆 | 仅最值 O(1) | O(log n) | ✗ | 内存 · 只要最值（堆 deck） |
| B+ 树 | O(log n) = 3 次 IO | 分裂/合并 | ✓✓ 链表顺序扫 | 磁盘 · 数据库索引 |
| LSM 树 | O(log n)~多路 | 顺序写 O(1) 摊 | ✓ 需归并 | 磁盘 · 写多读少（RocksDB） |
Interview QA · Part 1
BF = 左高 − 右高，|BF| ≤ 1。失衡路径前两步定型：LL 右旋、RR 左旋、LR 先左旋儿子再右旋、RL 相反。旋转把子树高度还原到插入前，修复即止。
最少节点的 h 层 AVL 树满足 N(h) = N(h−1) + N(h−2) + 1（两子树一高一矮）——斐波那契增长，解出 h ≤ 1.44 log₂n。最坏形状即"斐波那契树"。
红黑根黑nil黑、无红红、黑高一致。最关键是 ④+⑤ 的组合：⑤钉死黑高一致，④限制红不连续——合起来推出"最长 ≤ 2×最短"。
最短路径全黑 = bh；最长红黑相间 ≤ 2bh；黑高 bh 的子树至少 2^bh−1 个节点 → bh ≤ log₂(n+1) → 高 ≤ 2log₂(n+1)。三步口述即可。
AVL 更矮、查询略快，但删除要回溯 O(log n) 次旋转；红黑高度放宽到 2log n，但插入 ≤2、删除 ≤3 次旋转，修改便宜。读极多选 AVL，通用/写多选红黑。
新节点染红（不破坏黑高）；若父也红：叔红 → 变色把冲突上推两层（无旋转）；叔黑 → 一次旋转+变色终结。上推要么到根（0 旋转），要么中途遇黑叔（≤2 旋转）。
树化是哈希退化的兜底，负载不可预测、可能反复增删——要的是"任何序列下修改便宜 + 最坏有界"，正是红黑的强项；AVL 的删除回溯在退化场景反而危险。
CFS 调度器按 vruntime 排序（取最左 = 下一个运行进程）；epoll 用红黑树管理注册 fd（增删高频）；进程地址空间 vma 按地址有序。共同点：有序 + 高频增删 + 内核不能容忍最坏退化。
Interview QA · Part 2
B 树数据分布在所有节点，可能在非叶提前命中；B+ 树数据全在叶子且叶子链表相连——非叶纯导航扇出更大、范围查询顺序扫、每次查询稳定到叶。
二叉扇出 2，2000 万行高 ≈23 层 = 23 次磁盘 IO（每次 ~10ms 级）；B+ 树 16KB 页做节点、扇出 ≈1170，3 层搞定。数据在磁盘上，"矮胖"就是生命。
哈希等值 O(1) 但不支持范围扫描、排序、最左前缀匹配——BETWEEN / ORDER BY / LIKE 'x%' 全废。InnoDB 自适应哈希只是热点页的旁路缓存。
范围查询定位到起点叶后，沿链表顺序读下一批叶页——磁盘预读友好，几乎无随机 IO；删改时链表维护 O(1)。这是"范围查询之王"的机制来源。
插入时叶页满 → 从中间分裂、分裂键上提到父，父满继续上传（可能长高一层——唯一长高方式）；删除后页利用率低于阈值则与兄弟合并/重分布，父层收缩。
期望 O(log n) 与红黑同档，但插入删除只改指针、无旋转无染色，实现行数少一个量级；底层链表做范围查询同样顺。Redis zset 的选择（跳表 deck）。
LSM 把随机写变顺序写（memtable + 分层 SSTable + 后台 compaction），写吞吐远超 B+；代价是读要查多层、compaction 有写放大。RocksDB/LevelDB 用 LSM，MySQL 用 B+——读写比定生死。
Related & References
MySQL B+ 树索引 →（页/扇出/聚簇落地细节）
Redis 数据结构 →（zset 为何选跳表）
二分查找 →（有序结构的通用检索）
复杂度分析 →（log 下界的来源）
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch13 · Red-Black Trees | 五性质、黑高引理（高 ≤ 2log(n+1)）、插入删除修复 |
| Adelson-Velsky & Landis (1962) | AVL 原始论文；高度界 1.44 log n 的斐波那契论证 |
| Linux kernel lib/rbtree.c · kernel/sched/fair.c | 内核红黑树实现与 CFS 调度器应用 |
| MySQL 8.0 Manual · InnoDB Index Structures | 16KB 页、B+ 树组织；对照本仓库 index-btree deck |
| Bayer & McCreight (1972) · B-trees | B 树原始论文（B+ 为其数据库化变体） |