b-tree
No related notes
Outlinks (0)
No outlinks found
Backlinks (0)
No backlinks found
1 · B-tree#
1.1 · S - 场景#
需要频繁随机读取且支持范围查询的场景：
- 传统数据库（MySQL InnoDB、PostgreSQL）
- 文件系统（NTFS、ext4、HFS+）
- 内存数据库（Redis Sorted Sets 基础）
- 分布式系统的索引（Elasticsearch）
1.2 · C - 核心权衡#
| 维度 | LSM-tree | B-tree |
|---|---|---|
| 写入 | 顺序追加（快） | 原地更新（慢） |
| 读取 | 多层查询（多I/O） | 直接定位（少I/O） |
| 空间 | 多版本冗余 | 紧凑高效 |
| 范围查询 | 需要多个SSTable | 直接叶子链表 |
| CPU | Compaction 高负载 | 读写均衡 |
1.3 · Q - 核心问题与解决#
1.3.1 · Q1. 数据随机分散问题#
问题：如果直接把 key-value 放在文件中，随机读需要全表扫描。
解决方案：树形索引结构
- 数据按 key 有序排列
- 通过多层索引指针快速定位
- 树高通常只有 3-4 层（百万级数据）
1.3.2 · Q2. 更新不能原地改写的问题#
问题：如果数据长度变化（如字符串扩展），原地更新会导致后续数据移位。
解决方案：
- 将数据组织成固定大小的页（page/block）
- 更新时只改写涉及的页，不影响其他页
- 利用 CPU 缓存和磁盘分页的天然匹配
1.3.3 · Q3. 插入删除后的树结构失衡问题#
问题：频繁插入删除后，树可能变得不平衡，导致查询性能下降。
解决方案：自平衡机制
- 分裂（Split）：节点过满时分成两个节点
- 合并（Merge）：节点过空时和相邻节点合并
- 旋转（Rotation）：调整树的形状保持平衡
1.4 · A - B-tree 架构#
1.4.1 · 核心特性
Properties of B-tree (order m):
1. 每个节点最多有 m 个孩子（m-1 个 key）
2. 除根节点外，每个节点至少有 ⌈m/2⌉ 个孩子
3. 根节点至少有 2 个孩子（除非树只有根）
4. 所有叶子节点在同一层
5. 节点内 key 有序，key 分隔子树的范围1.4.2 · B-tree 的结构图#
┌─────────┐
│ 30 60 │ (根节点)
└────┬────┴─────┬────┘
/ \
┌─────────┐ ┌─────────┐
│ 10 20 │ │ 40 50 │ (内部节点)
└──┬──┬───┴──┬──┬───┘
/ | \ / | \
┌──┐ ┌─┐ ┌──┐┌──┐ ┌──┐┌────┐
│10│ │15│ │20│ │40│ │50│ │70 80│ (叶子节点)
└──┘ └─┘ └──┘└──┘ └──┘└────┘
(实际存储 data pointers)特点：
- 根到叶子的路径长度相同
- 内部节点和叶子节点都存储 key
- key 用于指导查询路由（路由 key 和数据 key 相同）
1.4.3 · B+tree 的改进（更常用于数据库）#
B+tree 在 B-tree 基础上的改进：
1. 只有叶子存储数据，内部节点只存 key
2. 叶子节点用链表连接，支持高效范围查询
3. 内部节点 key 可以重复出现在叶子B+tree 结构：
┌─────────┐
│ 30 60 │ (索引层：只有 key，无数据)
└────┬────┴─────┬────┘
/ \
┌─────────┐ ┌─────────┐
│ 10 20 │ │ 40 50 │
└──┬──┬───┴───┬──┬───┘
/ | \ / | \
┌──────┬────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 50 │ 70 │ (数据层：存储实际数据)
└──────┴────┴──────┴──────┴──────┘
↓ ↓ ↓ ↓ (叶子链表，支持范围查询)
[data1] [data2] [data3] [data4]1.5 · 关键操作
1.5.1 · 1. 搜索（Search）#
search(key, node):
# 在节点中找到 >= key 的第一个 key
i = binary_search(node.keys, key)
if key 在 node.keys 中:
return node.data[i] # 找到
if node 是叶子:
return NOT_FOUND # 不存在
return search(key, node.children[i]) # 递归搜索时间复杂度：O(log n)
- 树高度：h = log_m(n)，m 通常为 100-1000
- 每层二分查找：O(log m)
- 总复杂度：O(log_m(n) × log m)
1.5.2 · 2. 插入（Insert）#
insert(key, value):
# 1. 找到叶子节点
leaf = find_leaf(key)
# 2. 在叶子插入 key-value
leaf.insert(key, value)
# 3. 如果叶子过满（超过 m-1 个 key）
if leaf.is_full():
# 3a. 分裂：取中间 key 上升
mid_key = leaf.keys[m/2]
left, right = leaf.split()
# 3b. 递归处理父节点
parent.insert(mid_key)
if parent.is_full():
parent.split() # 可能导致级联分裂分裂过程（order=3）：
Before (过满): [10, 20, 30]
│
↓ split
After: [20] (上升到父节点)
/ \
[10] [30] (分成两个节点)时间复杂度：O(log n)
- 查找叶子：O(log n)
- 分裂（最坏级联到根）：O(log n)
1.5.3 · 3. 删除（Delete）#
delete(key):
# 1. 找到包含 key 的节点
node = search_node(key)
if node 是叶子:
node.remove(key)
else:
# 用前驱或后继替换，然后删除
predecessor = get_predecessor(key)
node.replace(key, predecessor)
delete(predecessor)
# 2. 如果节点过空（< ⌈m/2⌉ 个 key）
if node.underflow():
# 尝试从兄弟节点借
if sibling.has_extra():
borrow_from_sibling(node, sibling)
else:
# 否则与兄弟合并
merge(node, sibling)合并过程：
Before (过空): [20] [40]
/ \ / \
[10] [] [30] [35] [50]
│
└─ 与兄弟合并，从父节点借 key
After: [20, 40]
/ | \
[10] [30,35] [50]时间复杂度：O(log n)
- 查找 + 删除 + 合并/借位：O(log n)
1.6 · 性能分析
1.6.1 · 时间复杂度对比
| 操作 | 平衡二叉树 | B-tree (m=100) |
|---|---|---|
| Search | O(log n) | O(log n) 但常数小 |
| Insert | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) |
| Range | O(k + log n) | O(k + log n) |
1.6.2 · 空间和 I/O 特性#
数据量 N = 1 千万（10^7）
二叉搜索树：
树高：h ≈ log₂(10^7) ≈ 24 层
最坏情况需要 24 次磁盘 I/O
B-tree (m=100, 内部节点存 99 个 key)：
树高：h ≈ log₁₀₀(10^7) ≈ 3-4 层
最坏情况只需 3-4 次磁盘 I/O
性能差异：
├─ 二叉树：24 次 I/O × 10ms/IO = 240ms
└─ B-tree：3 次 I/O × 10ms/IO = 30ms
└─ 快 8 倍！1.6.3 · 为什么选择 B-tree？#
-
树高低：3-4 层可处理百万级数据
- 每层一次磁盘 I/O
- 减少 I/O 次数是关键
-
按页对齐：
- 操作系统和磁盘都是按页（4KB-16KB）处理
- B-tree 节点大小恰好匹配页大小
- 无需额外转换或分页
-
支持范围查询：
- 叶子有序连接（B+tree）
- 可高效扫描范围 [a, b]
- LSM 需要查多个 SSTable
-
更新高效：
- 原地改写，无多版本开销
- 无需后台 compaction
1.7 · 工业实现
1.7.1 · MySQL InnoDB B+tree 索引#
结构：
聚集索引：主键 + 完整行数据
辅助索引：索引键 + 主键引用
Clustered Index (按主键):
内部节点：[key1] [key2] [key3]
叶子节点：[pk1, data1] [pk2, data2] ...
Secondary Index (非主键索引):
内部节点：[key1] [key2]
叶子节点：[key1, pk1] [key2, pk2] ...
查询流程：
SELECT * FROM users WHERE name = 'Alice'
├─ 在 name 索引上二分查找
├─ 获得主键 pk = 123
├─ 在聚集索引上查询 pk = 123
└─ 获得完整行数据1.7.2 · SQLite B-tree 实现#
特点：
1. 使用变长 B-tree
2. 页大小可配置（默认 4KB）
3. 支持 VACUUM 重组
4. 数据紧凑存储在叶子1.8 · B-tree vs LSM-tree#
1.8.1 · 权衡决策表
| 特性 | B-tree | LSM-tree |
|---|---|---|
| 写吞吐 | 中等（随机I/O） | 高（顺序I/O） |
| 读延迟 | 低（直接定位） | 中等（多层查） |
| 空间占用 | 紧凑 | 冗余（多版本） |
| 范围查询 | 高效（叶子链表） | 需多SSTable |
| CPU开销 | 低 | 高（compaction） |
| 适用场景 | 通用OLTP | 写密集(日志、TS) |
1.8.2 · 选择建议
选 B-tree 如果：
✓ 读写比例均衡
✓ 需要高效范围查询
✓ 磁盘空间有限
✓ CPU 资源受限
例：传统数据库、文件系统
选 LSM-tree 如果：
✓ 写操作远多于读
✓ 可接受读放大
✓ 有充足 CPU 做 compaction
✓ 可接受高空间占用
例：日志、时序数据库、NoSQL1.9 · 实现要点（伪代码）
class BTree:
def __init__(self, order=3):
self.order = order # m
self.root = BNode(order)
def search(self, key):
return self._search_node(self.root, key)
def _search_node(self, node, key):
# 二分查找找到 >= key 的位置
idx = bisect.bisect_left(node.keys, key)
if idx < len(node.keys) and node.keys[idx] == key:
return node.data[idx] # 找到
if node.is_leaf:
return None # 叶子中未找到
return self._search_node(node.children[idx], key)
def insert(self, key, value):
if self.root.is_full():
# 根满了，需要创建新根
old_root = self.root
self.root = BNode(self.order)
self.root.children.append(old_root)
self._split_child(self.root, 0)
self._insert_non_full(self.root, key, value)
def _insert_non_full(self, node, key, value):
idx = bisect.bisect_left(node.keys, key)
if node.is_leaf:
# 直接插入
node.keys.insert(idx, key)
node.data.insert(idx, value)
else:
# 找到子节点
child = node.children[idx]
if child.is_full():
self._split_child(node, idx)
# 分裂后重新确定方向
if key > node.keys[idx]:
idx += 1
child = node.children[idx]
self._insert_non_full(child, key, value)
def _split_child(self, parent, child_idx):
# 分裂第 child_idx 个子节点
child = parent.children[child_idx]
mid_idx = (self.order - 1) // 2
# 创建新节点
new_child = BNode(self.order)
new_child.keys = child.keys[mid_idx + 1:]
new_child.data = child.data[mid_idx + 1:]
if not child.is_leaf:
new_child.children = child.children[mid_idx + 1:]
# 更新原节点
child.keys = child.keys[:mid_idx]
child.data = child.data[:mid_idx]
# 中间 key 上升到父节点
parent.keys.insert(child_idx, child.keys[mid_idx])
parent.data.insert(child_idx, child.data[mid_idx])
parent.children.insert(child_idx + 1, new_child)1.10 · 总结
B-tree 是生产数据库的标准选择，原因是：
- 低树高：3-4 层处理亿级数据，减少磁盘 I/O
- 高效性：查询、插入、删除都是 O(log n)
- 范围查询：叶子链表支持高效扫描
- 硬件友好：节点大小匹配磁盘页，CPU 缓存友好
- 空间高效：无多版本开销，紧凑存储
而 LSM-tree 则专注于写优化，通过顺序 I/O 换取读放大和空间放大。