balanced - tree - btree
07. 平衡树、红黑树与 B/B+ 树
0. 本章先解决什么问题
上一章讲了二叉搜索树,但普通搜索树会退化。
如果树长成链:
1 -> 2 -> 3 -> 4 -> 5
查找就从 O(log n) 退化成 O(n)。
本章要解决:
- 平衡树为什么存在?
- 旋转是什么,它如何恢复结构?
- 红黑树用什么思想保持近似平衡?
- B 树和 B+ 树为什么适合磁盘和数据库索引?
- 有序结构和哈希结构如何选?
这张图怎么读
这张图把 B+ 树和普通二叉树的差异画出来:B+ 树节点更像“页”,一页里放多个 key,树高因此更低;叶子页按顺序连接,所以范围查询不是重新查很多次,而是定位起点后顺着叶子链扫描。
1. 平衡的核心:控制高度
搜索树的查找成本是:
O(树高)
理想情况下,n 个节点高度接近:
log n
如果高度接近 n,就退化。
平衡树的目标:
插入删除后,通过调整结构,让树高保持在可控范围。
2. 旋转:局部改变形状但保持顺序
旋转是平衡树最基础的操作。
右旋示意:
y
/
x
B
右旋后:
x
y
/
B
旋转不会破坏搜索树中序顺序。
它改变的是高度分布,让树更平衡。
核心理解:
旋转是局部重连指针,用来降低某些路径高度。
手推:旋转为什么不会破坏搜索树顺序
旋转看起来像“把节点拧一下”,但它真正依赖的是区间关系。
右旋前:
y
/
x
/
A B
…
在搜索树里,这些部分满足:
A < x < B < y
右旋后:
x
/
A y
/
B
中序遍历仍然是:
A, x, B, y
所以旋转不是随便交换父子节点,而是在保持中序顺序不变的前提下,调整局部高度。排查平衡树 bug 时也要抓这个不变量:旋转后,如果中序序列变了,说明指针重连已经破坏了搜索树语义;如果中序没变但高度/颜色错了,说明平衡元数据维护出了问题。
3. 平衡树的 trade-off
平衡不是免费。
| 收益 | 成本 |
|---|---|
| 查找稳定 O(log n) | 插入删除要维护平衡 |
| 有序遍历 | 节点指针和元数据开销 |
| 范围查询 | 实现复杂 |
| 前驱后继 | 旋转、颜色或高度维护 |
如果只需要精确查找,不需要有序,哈希表可能更合适。
如果需要有序、范围、前驱后继,平衡树更合适。
4. 红黑树的直觉
红黑树是一种近似平衡的二叉搜索树。
它给节点增加颜色:
red / black
通过一组规则限制树的形状,让最长路径不会比最短路径长太多。
你不必一开始死背所有规则,先抓住目标:
用颜色约束 + 旋转 + 重新染色
让插入删除后树高仍然 O(log n)
红黑树不追求绝对完美平衡,而是追求:
维护成本可接受
查找性能稳定
5. 为什么不是所有场景都用红黑树
红黑树适合内存中的有序映射和集合,但它不是万能。
限制:
- 每个节点只存一个 key,指针较多。
- 节点分散,cache 不友好。
- 对磁盘不友好,因为一次查找可能访问很多节点页。
如果数据在磁盘或页缓存里,大量随机节点访问成本很高。
这就引出 B 树。
6. B 树:一个节点存多个 key
B 树是多路搜索树。
一个节点可以有多个 key 和多个孩子:
好处:
树的分叉更多
高度更低
一次磁盘页读取能拿到多个 key
如果一个节点大小设计成接近磁盘页或内存页,一次 IO 能读取很多索引信息。
机制深挖:为什么“页”改变了树的设计
内存里的二叉树通常关心比较次数和指针重连;外部存储或页式缓存里的索引更关心“访问了多少页”。一次页访问可以带回很多连续 key,所以 B/B+ 树把节点设计成页状结构:
| 设计点 | 作用 |
|---|---|
| 一个节点放多个 key | 增大分叉数,降低树高 |
| 节点大小贴近页大小 | 一次页读取获得更多索引信息 |
| 内部节点只做导航 | 让更多 key 装进导航页 |
| 叶子节点顺序连接 | 范围查询能顺序扫描 |
这会改变成本模型:
- 二叉树成本:比较次数 + 指针跳转
- B+ 树成本:页访问次数 + 页内查找 + 顺序扫描
在真实存储系统里,少访问一层页往往比少做几次 key 比较重要得多。
7. B+ 树
B+ 树是数据库和文件系统常见索引结构。
常见特点:
- 内部节点只放 key 和孩子指针。
- 真实数据或数据指针放在叶子节点。
- 叶子节点按顺序连接。
示意:
优点:
| 优点 | 说明 |
|---|---|
| 高度低 | 多路分叉减少层数 |
| 范围查询好 | 叶子节点顺序连接 |
| 磁盘友好 | 节点大小适合页 |
| 查询稳定 | 从根到叶路径长度可控 |
8. B+ 树为什么适合范围查询
范围查询:
查找 key 从 100 到 200
B+ 树流程:
先从根定位到包含 100 的叶子
然后沿叶子链向后扫
直到超过 200
这比哈希表强很多。
哈希表按 hash 分散 key,不保留顺序。范围查询只能全表扫描。
更新成本:分裂、合并和写放大
B+ 树不是只读结构。插入和删除会改变页内容:
| 操作 | 可能发生什么 | 成本含义 |
|---|---|---|
| 插入到未满叶子页 | 页内插入并保持有序 | 局部移动 key |
| 插入到满叶子页 | 叶子页分裂,父节点新增分隔 key | 可能向上传播 |
| 删除后页太空 | 借 key 或合并页 | 可能调整父节点 |
| 大量随机写 | 多个叶子页被修改 | 缓存和刷盘压力 |
这就是为什么索引不是越多越好。每多一个索引,写入时就多一个结构需要维护。读查询可能更快,写入、空间和缓存压力会变大。
反例:索引多,不代表系统一定更快
索引最容易被误解成“给查询加速的免费工具”。但 B+ 树索引是一个需要维护的数据结构,每次写入都可能修改它。
假设一条记录有 5 个索引:
主键索引
时间索引
状态索引
用户索引
复合条件索引
插入一条记录时,并不是只写一次数据页。系统还要让这 5 棵索引树都能找到新记录:
| 写入阶段 | 可能成本 |
|---|---|
| 定位叶子页 | 每个索引都要从根走到叶子 |
| 页内插入 key | 可能移动页内条目 |
| 叶子页满 | 分裂页,修改父节点 |
| 父节点也满 | 分裂向上传播 |
| 持久化 | 多个脏页等待刷盘或写日志 |
所以索引设计要问:
这个索引是否支持真实高频查询?
它能否明显减少扫描范围?
它带来的写放大、空间占用和缓存压力是否值得?
这也是 B+ 树章节必须联系实际的原因:理解结构以后,你就能解释为什么“读慢加索引”不是无脑操作。
9. 树索引和哈希索引的对比
| 能力 | 哈希表 | 平衡树 / B+ 树 |
|---|---|---|
| 精确查询 | 平均快 | 稳定 O(log n) |
| 有序遍历 | 不擅长 | 擅长 |
| 范围查询 | 不擅长 | 擅长 |
| 前驱后继 | 不擅长 | 擅长 |
| 最坏稳定性 | 依实现 | 较稳定 |
| 内存局部性 | 开放寻址较好 | 二叉树一般较差,B+ 树页友好 |
选型关键:
是否需要顺序和范围。
10. 联系实际:为什么数据库常用 B+ 树索引
数据库数据通常在页里管理。
一次磁盘或页缓存访问成本远高于内存比较。
B+ 树适合,因为:
- 分叉大,树高低。
- 一个节点能放很多 key。
- 每层访问一个页,IO 次数少。
- 叶子有序连接,范围扫描方便。
- 插入删除能通过分裂和合并保持结构。
所以数据库索引不是简单二叉搜索树。
它要适配存储设备和页访问成本。
小实验:手算一次范围查询路径
假设一个 B+ 树每个内部页最多放 3 个分隔 key,叶子页之间有顺序链。现在要查:
key between 31 and 75
分析时不要把它想成“查每一个 key”。正确路径是:
- 从根页开始,根据分隔 key 选择子页。
- 一层层向下,直到定位到包含 31 的叶子页。
- 在叶子页内顺序找起点。
- 沿叶子链向后扫描。
- 扫到 key > 75 时停止。
对比哈希索引:
| 查询 | 哈希索引 | B+ 树 |
|---|---|---|
key = 44 | 很适合 | 也可以 |
31 <= key <= 75 | 不保序,通常不适合 | 定位起点后顺序扫描 |
order by key | 不天然支持 | 叶子链天然有序 |
这个例子说明:B+ 树强的不是“单点查找一定比哈希快”,而是它把页访问、稳定树高、顺序扫描放在同一个结构里。
11. 学完本章你能解决什么问题
学完这一章,你应该能解决或开始分析这些问题:
- 普通搜索树为什么会退化?
- 平衡树为什么要控制高度?
- 旋转如何在保持有序的同时调整树形?
- 红黑树为什么追求近似平衡?
- B 树为什么一个节点放多个 key?
- B+ 树为什么适合磁盘索引和范围查询?
- 有序索引和哈希索引如何选择?
平衡树解决的是“有序能力 + 稳定高度”。B+ 树进一步把这个目标适配到磁盘页和范围扫描。