database_tutorial

第2章：存储与索引结构

章节概述

在数据库系统中，存储与索引结构是决定查询性能的核心因素。本章将深入探讨各种索引数据结构的设计原理、实现细节和适用场景。我们将从经典的B+树开始，逐步深入到现代数据库中广泛使用的LSM树、哈希索引、位图索引等高级结构，最后介绍自适应索引这一前沿技术。通过本章学习，您将能够根据具体工作负载特征选择最优的索引策略，并理解各种索引结构背后的权衡。

学习目标

• 深刻理解B+树的设计原理和优化技巧
• 掌握LSM树的写优化机制和compaction策略
• 理解哈希索引的适用场景和限制
• 掌握位图索引和倒排索引在分析型工作负载中的应用
• 了解自适应索引技术的最新进展
• 能够根据工作负载特征选择合适的索引结构

2.1 B+树深度解析

2.1.1 B+树的设计动机

B+树是数据库系统中最广泛使用的索引结构。其设计充分考虑了磁盘I/O的特性：

1. 磁盘访问优化：磁盘的随机访问成本远高于顺序访问，B+树通过增大节点大小（通常为页大小，4KB-16KB）来减少树的高度，从而减少磁盘I/O次数。

2. 缓存友好性：较大的节点可以更好地利用CPU缓存，一次磁盘读取可以获取更多的键值对。

3. 范围查询效率：所有数据都存储在叶子节点，且叶子节点通过指针相连，使得范围查询可以通过顺序扫描完成。

2.1.2 B+树的结构特征

                    [50 | 100]                    <- 根节点
                   /     |      \
              [20|30]  [70|80]  [120|150]        <- 内部节点
             /   |   \    |   \     |    \
          [...]  [...] [...] [...] [...] [...]   <- 叶子节点
            ↔      ↔     ↔     ↔     ↔           <- 叶子链表

关键特性：

1. 节点容量：设节点最大容量为$B$，则：
   • 根节点：至少2个子节点（除非是叶子）
   • 内部节点：$\lceil B/2 \rceil$ 到 $B$ 个子节点
   • 叶子节点：$\lceil B/2 \rceil$ 到 $B$ 个键值对

2. 高度界限：对于$N$个键值对，树高度$h$满足： \(h \leq \log_{\lceil B/2 \rceil} N\)

3. 填充因子：实际系统中，节点平均填充率约为67%（理论最低50%）。

2.1.3 B+树的操作优化

插入优化：

1. 节点分裂策略：
   • 传统分裂：50-50分裂，简单但可能导致空间利用率低
   • 延迟分裂：尝试将键重新分配给兄弟节点，避免不必要的分裂
   • 批量加载：构建时使用自底向上的方法，可达到接近100%的填充率
2. 预分裂技术： 监控节点填充率，在达到阈值（如90%）时主动分裂，避免关键路径上的分裂操作。

删除优化：

1. 懒惰删除：仅标记删除，不立即合并节点，减少结构调整开销
2. 批量删除：累积删除操作，定期批量处理
3. 合并策略：当节点利用率低于阈值（如25%）时才考虑合并

2.1.4 B+树的并发控制

锁耦合（Lock Coupling）：

1. 获取父节点锁
2. 获取子节点锁
3. 如果子节点安全（不会分裂/合并），释放父节点锁
4. 否则保持父节点锁

乐观锁协议：

• 读取时不加锁，使用版本号验证
• 只在修改时加锁
• 适合读多写少的场景

B-link树：

• 节点增加右兄弟指针
• 允许并发的分裂操作
• 提高并发度但增加复杂性

2.1.5 B+树的变种与优化

1. B*树：延迟分裂，要求节点至少2/3满
2. Bε树：在节点中缓存更新，批量下推
3. Fractal Tree：使用消息缓冲区，优化写入性能
4. Adaptive B+树：根据访问模式动态调整节点大小

2.1.6 B+树的性能分析

I/O成本模型：

对于高度为$h$的B+树，各操作的I/O成本：

• 点查询：$h$次I/O（最坏情况）
• 范围查询：$h + \lceil \frac{结果集大小}{每页记录数} \rceil$次I/O
• 插入/删除：$h$次读 + $O(h)$次写（考虑分裂/合并）

缓存效果分析：

假设缓冲池可容纳$M$个页面，访问遵循Zipf分布： \(P(访问第i个页面) \propto \frac{1}{i^s}\)

其中$s$通常在0.6-1.2之间。根节点和上层节点由于访问频率高，几乎总在缓存中，实际I/O次数远小于树高度。

并发性能：

并发度分析：
- 读密集型：几乎线性扩展
- 写密集型：受根节点竞争限制
- 混合负载：取决于写比例和分裂频率

优化策略：
1. 使用B-link树减少锁持有时间
2. 批量操作减少锁竞争
3. 分区B+树提高并发度

2.1.7 B+树的实际部署

内存B+树优化：

当B+树完全在内存中时，优化重点转向CPU缓存和指令级并行：

1. 缓存行对齐：节点大小设为缓存行倍数（64B的倍数）
2. SIMD搜索：使用向量指令并行比较多个键
3. 预取优化：提前预取可能访问的子节点
4. CSB+树：将所有子节点连续存储，提高缓存局部性

持久内存（PM）上的B+树：

Intel Optane等持久内存带来新的设计考虑：

1. 8字节原子写：利用PM的原子写特性简化日志
2. 选择性持久化：只持久化叶子节点，内部节点可重建
3. 混合索引：内部节点在DRAM，叶子节点在PM

分布式B+树：

在分布式环境中，B+树面临新挑战：

1. 分区策略：
   • 范围分区：保持顺序但可能负载不均
   • 哈希分区：负载均衡但失去全局顺序
2. 分布式事务：
   • 使用两阶段提交保证一致性
   • 考虑使用Raft等共识协议
3. 缓存一致性：
   • 使用版本号或租约机制
   • 考虑最终一致性模型

2.1.8 实践中的考虑

Rule of Thumb：

• 节点大小：HDD使用16KB-64KB，SSD使用4KB-16KB，内存使用256B-4KB
• 填充因子：批量加载时90-95%，在线操作时保持67-75%
• 键压缩：当平均键长度>20字节时考虑前缀压缩
• 缓冲池：至少能容纳树的前两层（覆盖99%+的内部节点）
• 并发控制：读写比>100:1时用乐观锁，否则用锁耦合
• 对于递增键（如时间戳），预分配右边界空间避免热点

2.2 LSM树原理

2.2.1 LSM树的核心思想

LSM（Log-Structured Merge）树通过将随机写转换为顺序写来优化写入性能。其核心思想是：

1. 写入缓冲：新数据先写入内存结构（MemTable）
2. 批量持久化：MemTable满后转为不可变的SSTable并顺序写入磁盘
3. 后台合并：定期合并SSTable以控制读放大

2.2.2 LSM树的架构

   写入 → [MemTable] → [Immutable MemTable]
             ↓                ↓
         [WAL日志]        [SSTable L0]
                              ↓
                         [SSTable L1]
                              ↓
                         [SSTable L2]
                              ↓
                            [...]

关键组件：

1. MemTable：内存中的有序数据结构（通常是跳表或B树）
2. WAL（Write-Ahead Log）：保证持久性
3. SSTable：有序的、不可变的磁盘文件
4. Bloom Filter：快速判断键是否存在
5. Block Cache：缓存热点数据块

2.2.3 Compaction策略

Size-Tiered Compaction：

• 相同大小的SSTable合并
• 写放大较小：$O(\log N)$
• 空间放大较大：最坏2倍

Leveled Compaction：

• 分层管理，每层大小呈指数增长
• 写放大较大：$O(L \cdot F)$，其中$L$是层数，$F$是放大因子
• 空间放大较小：约1.1倍

Universal Compaction：

• 基于时间窗口的合并
• 平衡写放大和空间放大
• 适合时序数据

2.2.4 读写性能分析

写入成本： \(Write\_Amplification = \frac{Total\_Bytes\_Written\_to\_Disk}{User\_Bytes\_Written}\)

读取成本：

• 最坏情况：需要查询所有层级
• 优化：Bloom Filter可将不存在键的查询成本降至$O(1)$

空间成本： \(Space\_Amplification = \frac{Total\_Disk\_Space\_Used}{Unique\_Data\_Size}\)

2.2.5 LSM树优化技术

1. 分区（Partitioning）：

将键空间划分为独立的分区，每个分区维护自己的LSM树：

分区策略：
- 范围分区：[0-1000), [1000-2000), ...
- 哈希分区：hash(key) mod N
- 复合分区：先哈希再范围

优势：
- 并行compaction
- 局部compaction减少写放大
- 更好的缓存局部性

2. 并行Compaction：

线程池模型：
- Minor Compaction线程：处理L0→L1
- Major Compaction线程：处理L1→Ln
- 优先级队列：紧急compaction优先

调度策略：
if L0_count > threshold_critical:
  trigger_immediate_compaction()
elif write_stall_risk > 0.8:
  increase_compaction_threads()
else:
  normal_background_compaction()

3. 增量Compaction：

不是合并整个层级，而是选择部分SSTable：

选择算法：
1. 计算每个SSTable的"温度"（访问频率）
2. 优先合并重叠最多的SSTable
3. 限制单次compaction的数据量

benefit(SSTable_set) = overlap_ratio × access_frequency
                       - compaction_cost

4. 混合存储层次：

存储层次设计：
L0: NVMe SSD（写缓冲）
L1-L2: SATA SSD（热数据）
L3-Ln: HDD（冷数据）

数据迁移策略：
- 基于访问频率的热度统计
- 预测模型判断数据冷热
- 异步迁移避免影响前台操作

5. 自适应Compaction：

根据工作负载特征动态调整策略：

监控指标：
- 写入速率（write_rate）
- 读取延迟分布（p50, p99）
- 空间放大系数（space_amp）

调整规则：
if write_rate > threshold AND read_latency < SLA:
  use_tiered_compaction()  # 优化写
elif read_latency > SLA:
  use_leveled_compaction()  # 优化读
elif space_amp > limit:
  increase_compaction_rate()  # 减少空间放大

6. Compaction优化技巧：

• 流水线化：读取、合并、写入三阶段流水线
• 压缩优化：只在最后一层压缩，上层保持未压缩
• 布隆过滤器共享：相邻SSTable共享布隆过滤器
• 异步预读：提前预读下一个要合并的块
• 写优化：使用Direct I/O避免双重缓存

2.2.6 LSM树 vs B+树

详细对比分析：

特性	LSM树	B+树
写入性能	优秀（顺序写，批量刷盘）	一般（随机写，即时更新）
点查询	$O(L \cdot \log N)$，L为层数	$O(\log_B N)$，B为扇出度
范围查询	需合并多个SSTable，成本较高	高效（叶子链表顺序扫描）
空间放大	1.1-2倍（取决于策略）	稳定1.5倍（67%填充率）
写放大	10-30倍（Leveled）	2-3倍（页面更新）
内存需求	较高（MemTable+BloomFilter）	较低（仅缓冲池）
恢复时间	快速（顺序读取WAL）	较慢（需要重放更多日志）
并发性	优秀（追加写无冲突）	中等（节点锁竞争）
实现复杂度	高（compaction调度复杂）	中等（分裂合并逻辑）

工作负载适配性：

LSM树最佳场景：
- 时序数据（IoT、监控、日志）
- 社交网络（写入频繁）
- 消息队列（高吞吐写入）
- 缓存系统（频繁更新）

B+树最佳场景：
- OLTP系统（事务处理）
- 元数据存储（读多写少）
- 二级索引（需要快速查找）
- 小数据集（内存可容纳）

混合架构趋势：

现代系统often采用混合架构，结合两者优势：

1. 主存储用LSM，索引用B+树
   • RocksDB + 二级B+树索引
2. 分层架构
   • 热数据：B+树（快速访问）
   • 温数据：LSM树（平衡读写）
   • 冷数据：列存储（压缩率高）
3. 自适应切换
   • 监控读写比例
   • 动态选择数据结构

Rule of Thumb：

• 写入量 > 读取量 × 10：优选LSM树
• 读延迟要求 < 10ms且稳定：优选B+树
• 数据量 > 内存 × 100：考虑LSM树
• SSD环境：写放大成为主要考虑因素
• 云存储：LSM树的顺序I/O更友好

2.3 哈希索引

2.3.1 哈希索引基础

哈希索引通过哈希函数将键映射到存储位置，提供$O(1)$的点查询性能。

基本结构：

Key → Hash Function → Bucket → Entry List
                         ↓
                    [Overflow Page]

2.3.2 哈希函数选择

理想哈希函数特性：

1. 均匀分布：最小化冲突
2. 计算高效：避免成为瓶颈
3. 确定性：相同输入产生相同输出

常用哈希函数：

• MurmurHash：速度快，分布均匀
• CityHash：Google开发，优化现代CPU
• xxHash：极速，适合实时系统
• CRC32：硬件支持，但分布不如专用哈希函数

2.3.3 冲突解决策略

链地址法（Chaining）：

结构示例：
Bucket[0] → NULL
Bucket[1] → (K1,V1) → (K5,V5) → NULL
Bucket[2] → (K2,V2) → NULL
Bucket[3] → (K3,V3) → (K7,V7) → (K9,V9) → NULL

性能分析：
- 平均查找长度：1 + α/2（成功），α（失败）
- 最坏情况：O(n)所有键哈希到同一桶
- 内存开销：指针占用额外空间

优化技术：

1. 动态数组链：用动态数组替代链表，提高缓存局部性
2. 排序链：保持链表有序，加速查找和范围扫描
3. 跳表链：对长链使用跳表结构

开放地址法（Open Addressing）：

性能对比：

负载因子α = 0.5时的平均探测次数：
- 线性探测：成功1.5次，失败2.5次
- 二次探测：成功1.44次，失败2.19次
- 双重哈希：成功1.39次，失败2.00次

负载因子α = 0.9时：
- 线性探测：成功5.5次，失败50.5次
- 双重哈希：成功2.56次，失败10.00次

线性探测的缓存优势： 虽然聚集现象严重，但线性探测因顺序访问内存，缓存命中率高，实践中性能often优于理论预期。

Robin Hood Hashing： 线性探测的变种，最小化方差：

插入时：
if current.distance < new.distance:
    swap(current, new)
    继续为new寻找位置

效果：
- 减少最大探测距离
- 更均匀的探测距离分布

Hopscotch Hashing： 结合开放地址和链接的优点：

每个桶维护邻域信息（bitmap）
- 邻域大小H（如32）
- 保证元素在H距离内
- 支持并发操作

Cuckoo Hashing详解：

使用两个哈希表T1和T2：
插入key：
1. if T1[h1(key)]空：插入T1
2. elif T2[h2(key)]空：插入T2  
3. else：
   - 踢出T1[h1(key)]的元素
   - 为被踢出元素找新位置
   - 可能触发连锁反应

循环检测：
- 限制最大踢出次数
- 超过阈值则扩容重哈希

变种：

• d-ary Cuckoo：使用d个哈希函数，提高空间利用率
• Cuckoo Filter：支持删除的近似成员测试

2.3.4 动态哈希

可扩展哈希（Extendible Hashing）：

Global Depth = 2
[00] → Bucket A
[01] → Bucket B  
[10] → Bucket C
[11] → Bucket D

• 目录可以指数增长
• 桶独立分裂
• 减少重组开销

线性哈希（Linear Hashing）：

• 顺序分裂桶
• 无需目录结构
• 平滑的增长过程

2.3.5 哈希索引的限制与优化

限制：

1. 不支持范围查询
2. 不支持部分键匹配
3. 哈希冲突影响性能
4. 动态调整大小代价高

优化技术：

1. 自适应哈希：根据负载动态调整桶数量
2. 分区哈希：将哈希表分区以提高并发性
3. 内存优化：使用紧凑的数据结构减少内存占用
4. 硬件加速：利用SIMD指令并行计算哈希

Rule of Thumb：

• 负载因子保持在0.7-0.8之间
• 点查询为主且键分布均匀：优选哈希索引
• 需要排序或范围查询：避免使用哈希索引

2.4 位图索引与倒排索引

2.4.1 位图索引原理

位图索引使用位向量表示数据的存在性，特别适合低基数（distinct values少）的列。

基本结构：

性别列：
男: 1 0 1 1 0 1 0 0 1 1 ...
女: 0 1 0 0 1 0 1 1 0 0 ...

部门列：
销售:   1 0 0 1 0 0 0 1 0 0 ...
研发:   0 1 0 0 1 0 0 0 1 0 ...
市场:   0 0 1 0 0 1 0 0 0 1 ...
运营:   0 0 0 0 0 0 1 0 0 0 ...

查询执行：

• AND查询：位向量按位与
• OR查询：位向量按位或
• NOT查询：位向量按位取反

2.4.2 位图压缩技术

Run-Length Encoding (RLE)：

原始: 0000000011111111100000000
RLE:  0×8, 1×9, 0×8

Word-Aligned Hybrid (WAH)：

• 使用31位存储数据，1位标识类型
• 连续的0或1可以高度压缩
• 支持直接在压缩数据上进行位运算

Roaring Bitmap：

• 将32位空间分为$2^{16}$个桶
• 稀疏桶用数组，密集桶用位图
• 自适应选择最优表示

压缩率分析： 设基数为$c$，记录数为$n$：

• 未压缩空间：$O(c \cdot n)$位
• 最佳压缩（全0或全1）：$O(c)$
• 实际压缩率：取决于数据分布的聚集性

2.4.3 位图索引的应用场景

优势：

1. 空间效率高（低基数列）
2. 支持快速的集合运算
3. 并行化友好
4. 缓存利用率高

限制：

1. 高基数列空间爆炸
2. 更新代价高（需要重建位图）
3. 不适合OLTP工作负载

Rule of Thumb：

• 基数 < 总行数的1%：强烈推荐位图索引
• 基数 < 10000且查询涉及多列过滤：考虑位图索引
• OLTP系统：避免使用位图索引

2.4.4 倒排索引原理

倒排索引是全文搜索的核心数据结构，将词项映射到包含该词的文档列表。

基本结构：

词项词典：
"数据库" → Posting List: [(doc1, 2), (doc3, 5), (doc7, 1)]
"索引"   → Posting List: [(doc1, 3), (doc2, 1), (doc3, 2)]
"查询"   → Posting List: [(doc2, 4), (doc5, 2), (doc7, 3)]

其中：(docID, termFrequency)

2.4.5 倒排索引的组件

词项词典（Term Dictionary）：

• 存储结构：B+树、哈希表或FST（Finite State Transducer）
• 前缀树优化：共享公共前缀，减少存储空间
• 模糊匹配：支持通配符和编辑距离查询

倒排列表（Posting List）：

基础格式：[docID, termFreq, positions]
压缩格式：使用差值编码 + 变长编码

示例：
原始docID: [5, 8, 13, 21, 34]
差值编码: [5, 3, 5, 8, 13]
VByte编码: [0x05, 0x03, 0x05, 0x08, 0x0D]

跳表优化（Skip List）：

Level 2:  5 -----------------> 34
Level 1:  5 -----> 13 -------> 34
Level 0:  5 -> 8 -> 13 -> 21 -> 34

• 加速列表遍历
• 空间换时间的权衡

2.4.6 倒排索引的查询处理

布尔查询：

查询: "数据库" AND "索引"
处理: Intersect(PostingList("数据库"), PostingList("索引"))

短语查询：

查询: "数据库索引"（要求相邻）
处理: 
1. 获取两个词的位置信息
2. 检查位置是否相邻

评分与排序：

TF-IDF公式： \(Score(q, d) = \sum_{t \in q} TF(t, d) \cdot IDF(t)\)

其中：

• $TF(t, d) = \frac{freq(t, d)}{

  d

  }$

• $IDF(t) = \log \frac{N}{df(t)}$

BM25公式（更常用）： \(Score(q, d) = \sum_{t \in q} IDF(t) \cdot \frac{TF(t, d) \cdot (k_1 + 1)}{TF(t, d) + k_1 \cdot (1 - b + b \cdot \frac{|d|}{avgdl})}\)

2.4.7 倒排索引的优化

分片（Sharding）：

• 按文档ID范围分片
• 按时间分片（适合日志数据）
• 按哈希分片（负载均衡）

缓存策略：

1. 词项缓存：缓存高频查询词的倒排列表
2. 查询结果缓存：缓存完整查询结果
3. 交集缓存：缓存常见词项组合的交集结果

增量索引：

主索引（不可变） + 增量索引（可变） + 删除列表
定期合并：主索引' = Merge(主索引, 增量索引) - 删除列表

Rule of Thumb：

• 索引大小约为原始文本的20-30%
• 包含位置信息时增加到50-60%
• 更新频率低的数据适合倒排索引
• 实时性要求高时使用增量索引策略

2.5 自适应索引技术

2.5.1 自适应索引的动机

传统索引需要预先创建并维护，存在以下问题：

1. 预测困难：难以预知未来的查询模式
2. 维护开销：每个索引都有存储和更新成本
3. 静态配置：无法适应工作负载的变化
4. 过度索引：为了覆盖各种查询创建过多索引

自适应索引通过动态调整索引结构来解决这些问题。

2.5.2 数据库裂解（Database Cracking）

核心思想： 将索引创建的成本分摊到查询执行过程中，每次查询都会部分地改善数据组织。

Cracking算法：

查询: SELECT * FROM T WHERE x BETWEEN low AND high

处理过程:
1. 初始状态：数据未排序
   [8, 3, 12, 5, 20, 1, 15, 7]
   
2. 第一次查询 (5 ≤ x ≤ 15)：
   分区结果：[3, 1] | [8, 5, 12, 15, 7] | [20]
   记录边界：<5 | 5-15 | >15
   
3. 第二次查询 (7 ≤ x ≤ 12)：
   进一步细化：[3, 1] | [5] | [8, 12, 7] | [15] | [20]
   记录边界：<5 | 5-7 | 7-12 | 12-15 | >15

性能分析：

• 首次查询：$O(n)$
• 后续查询：逐渐接近$O(\log n)$
• 收敛速度：取决于查询分布

2.5.3 自适应合并（Adaptive Merging）

结合LSM树和Database Cracking的思想：

初始状态：多个有序分区
P1: [1, 5, 9]
P2: [2, 6, 10]  
P3: [3, 7, 11]

查询驱动的合并：
查询 [4, 8] → 部分合并相关范围
结果: P_merged: [5, 6, 7] + 未触及部分保持原样

优势：

• 避免全量合并的开销
• 热点数据优先优化
• 冷数据保持原样

2.5.4 学习型索引（Learned Index）

核心观察： 索引本质上是从键到位置的映射函数，可以用机器学习模型近似。

模型结构：

第一层（根模型）：
f_root(key) → 选择子模型

第二层（专家模型）：  
f_expert_i(key) → 预测位置

误差修正：
实际位置 = 预测位置 ± 误差界限内的局部搜索

CDF建模： 将索引建模为累积分布函数（CDF）： \(pos = CDF(key) \times N\)

优势与挑战：

优势：

• 空间效率：模型参数远少于传统索引
• 缓存友好：模型可完全加载到缓存
• 可并行：预测过程无需锁

挑战：

• 更新处理：模型重训练成本
• 最坏情况保证：需要后备机制
• 数据分布假设：对偏斜数据效果下降

2.5.5 混合自适应策略

工作负载感知索引：

监控指标：

• 查询频率分布
• 选择性估计
• 访问模式（点查询vs范围查询）
• 更新/查询比率

决策逻辑：

if (查询频率 > θ1 AND 选择性 < θ2):
    创建索引
elif (索引使用率 < θ3 FOR 时间窗口 T):
    删除索引
elif (数据分布变化 > θ4):
    重建索引

自动索引推荐系统：

1. What-if分析：
   • 虚拟索引创建
   • 代价估计
   • 收益评估
2. 索引交互分析：
   • 检测冗余索引
   • 识别索引组合收益
   • 评估维护成本
3. 在线调整：
   • 增量式索引构建
   • 后台索引迁移
   • 无中断切换

2.5.6 自适应索引的实践考虑

部署策略：

1. 渐进式部署：
   • 从非关键路径开始
   • 监控性能变化
   • 逐步扩展应用范围
2. 混合模式：
   • 关键查询使用传统索引
   • 探索性查询使用自适应索引
   • 根据反馈动态调整

性能监控：

关键指标：
- 查询响应时间分布
- 索引构建开销
- 存储空间使用
- 缓存命中率
- CPU利用率

Rule of Thumb：

• 工作负载多变：优先考虑自适应索引
• 查询模式稳定：传统索引更可靠
• 探索性分析：Database Cracking很有效
• 机器学习负载：考虑学习型索引
• 生产环境：保守采用，充分测试

本章小结

本章深入探讨了数据库系统中的各种索引结构，每种结构都有其独特的设计理念和适用场景：

核心概念回顾

1. B+树：平衡的多路搜索树，优化磁盘I/O，提供稳定的$O(\log_B N)$性能，是OLTP系统的首选。

2. LSM树：通过将随机写转换为顺序写来优化写入性能，代价是读放大和空间放大，适合写密集型工作负载。

3. 哈希索引：提供$O(1)$的点查询性能，但不支持范围查询和排序操作。

4. 位图索引：对低基数列极其高效，支持快速的集合运算，但更新成本高，主要用于OLAP系统。

5. 倒排索引：全文搜索的核心，通过词项到文档的映射实现高效的文本检索。

6. 自适应索引：根据工作负载动态调整，包括Database Cracking、学习型索引等新技术。

关键公式

• B+树高度：$h \leq \log_{\lceil B/2 \rceil} N$
• LSM写放大：$WA = O(L \cdot F)$（Leveled Compaction）
• TF-IDF评分：$Score(q, d) = \sum_{t \in q} TF(t, d) \cdot IDF(t)$
• 学习型索引：$pos = CDF(key) \times N$

选择索引的决策框架

工作负载特征	推荐索引类型	理由
读多写少，需要范围查询	B+树	稳定的读性能，支持范围查询
写密集型，偶尔读取	LSM树	优秀的写入性能
仅点查询，键分布均匀	哈希索引	O(1)查询时间
低基数列的分析查询	位图索引	空间效率高，集合运算快
全文搜索	倒排索引	专门为文本检索设计
工作负载多变	自适应索引	动态优化

常见陷阱与错误

B+树相关

1. 节点大小选择不当
   • 错误：使用过小的节点（如256B）
   • 后果：树高度增加，I/O次数增多
   • 正确：匹配页大小（4KB-16KB）
2. 忽视批量加载优化
   • 错误：逐条插入构建B+树
   • 后果：大量节点分裂，填充率低
   • 正确：排序后批量加载，填充率接近100%
3. 并发控制过度保守
   • 错误：整棵树加锁
   • 后果：并发性能差
   • 正确：使用锁耦合或乐观并发控制

LSM树相关

1. Compaction策略选择不当
   • 错误：盲目使用Leveled Compaction
   • 后果：写放大严重
   • 正确：根据写入模式选择合适策略
2. 忽视Bloom Filter配置
   • 错误：不使用或配置不当的Bloom Filter
   • 后果：读性能严重下降
   • 正确：根据假阳性率要求合理配置
3. Level大小比例设置不合理
   • 错误：使用过大的放大因子（如100）
   • 后果：compaction开销巨大
   • 正确：通常使用10左右的放大因子

哈希索引相关

1. 用于范围查询
   • 错误：对需要范围扫描的列使用哈希索引
   • 后果：无法利用索引，退化为全表扫描
   • 正确：仅用于等值查询
2. 哈希函数选择不当
   • 错误：使用简单取模作为哈希函数
   • 后果：数据分布不均，冲突严重
   • 正确：使用专业哈希函数如MurmurHash

位图索引相关

1. 高基数列使用位图
   • 错误：对unique列创建位图索引
   • 后果：空间爆炸
   • 正确：仅用于低基数列（<1%总行数）
2. 在OLTP系统使用
   • 错误：在频繁更新的表上使用位图索引
   • 后果：更新性能极差
   • 正确：仅在OLAP或只读场景使用

倒排索引相关

1. 忽视停用词处理
   • 错误：索引所有词包括”的”、”是”等
   • 后果：索引膨胀，查询效率低
   • 正确：维护停用词表，过滤高频无意义词
2. 不当的分词策略
   • 错误：中文使用空格分词
   • 后果：检索效果差
   • 正确：使用专业分词器如jieba

练习题

基础题

练习2.1：B+树节点分裂 给定一个B+树，节点最大容量B=4，当前某叶子节点包含键[10, 20, 30]，现在要插入键25和35，描述节点分裂过程。

提示

考虑插入顺序对分裂的影响，以及中间键的选择。

参考答案

插入25后：[10, 20, 25, 30]（未满，不分裂） 插入35后：[10, 20, 25, 30, 35]（超出容量，需要分裂） 分裂过程： 1. 选择中间键25作为分裂点 2. 左节点：[10, 20, 25] 3. 右节点：[30, 35] 4. 向父节点插入键25和右节点指针 注意：不同的实现可能选择不同的分裂点（如30），这会影响节点的平衡性。

练习2.2：LSM树写放大计算 假设LSM树使用Leveled Compaction，放大因子F=10，共有4层（L0-L3）。如果写入1GB数据，计算总的写放大。

提示

每层的数据都会被重写F次才能到达下一层。

参考答案

写放大计算： - L0→L1: 1GB × 10 = 10GB - L1→L2: 1GB × 10 = 10GB - L2→L3: 1GB × 10 = 10GB - 初始写入: 1GB 总写入量 = 1 + 10 + 10 + 10 = 31GB 写放大 = 31GB / 1GB = 31倍 实际情况中，并非所有数据都会到达最底层，因此实际写放大通常小于理论值。

练习2.3：哈希表负载因子 一个哈希表有1000个桶，当前存储了750个键值对。如果使用线性探测解决冲突，估算平均查找长度。

提示

负载因子α = 0.75，使用线性探测的平均查找长度公式。

参考答案

负载因子 α = 750/1000 = 0.75 线性探测平均查找长度： - 成功查找：≈ 1/2 × (1 + 1/(1-α)) = 1/2 × (1 + 1/0.25) = 2.5 - 失败查找：≈ 1/2 × (1 + 1/(1-α)²) = 1/2 × (1 + 16) = 8.5 这说明当负载因子达到0.75时，性能开始显著下降，特别是对于不存在的键的查找。

练习2.4：位图索引空间计算 一个表有1000万行，某列只有5个不同值。计算使用位图索引的空间需求（未压缩），并与B+树索引比较（假设每个索引项32字节）。

提示

位图索引为每个唯一值创建一个位向量。

参考答案

位图索引空间： - 每个值需要1000万位 = 10^7 / 8 = 1.25MB - 5个值总计：5 × 1.25MB = 6.25MB B+树索引空间： - 1000万个索引项 × 32字节 = 320MB 空间节省：320MB / 6.25MB = 51.2倍 实际使用中，位图索引通常还会进行压缩，空间优势更明显。

挑战题

练习2.5：混合索引设计 设计一个电商网站的商品表索引策略。表结构：

• product_id (主键，自增)
• category (20个类别)
• price (范围0-10000)
• brand (1000个品牌)
• description (商品描述文本)
• status (上架/下架)
• created_at (时间戳)

常见查询：

1. 按类别和价格范围筛选
2. 全文搜索商品描述
3. 按品牌查找
4. 获取最新上架商品

提示

考虑每个查询的特点，选择最适合的索引类型。注意复合索引的列顺序。

参考答案

索引策略： 1. **主键索引**：product_id使用B+树（默认） 2. **类别-价格复合索引**：(category, price)使用B+树 - category在前因为选择性更高 - 支持类别内的价格范围查询 3. **描述全文索引**：description使用倒排索引 - 支持关键词搜索 - 考虑使用专门的搜索引擎如Elasticsearch 4. **品牌索引**：brand使用B+树或哈希索引 - 如果只有等值查询，哈希索引更优 - 如果需要按品牌名排序，使用B+树 5. **状态位图索引**：status使用位图索引 - 只有2个值，位图索引空间效率极高 - 可以快速过滤上架商品 6. **时间索引**：(status, created_at DESC)复合B+树索引 - 支持"获取最新上架商品"查询 - status在前可以直接过滤上架商品 额外考虑： - 对于热门查询组合，可以创建覆盖索引 - 使用查询日志分析，动态调整索引策略 - 考虑分区表，按时间或类别分区

练习2.6：LSM树参数调优 一个时序数据库使用LSM树存储，写入速率100MB/s，数据保留7天。系统有256GB内存，10TB SSD。设计LSM树的参数配置。

提示

考虑MemTable大小、Level数量、Compaction策略、Bloom Filter配置等。

参考答案

参数配置： 1. **MemTable配置**： - 大小：2GB（利用充足内存减少flush频率） - 数量：2个（一个活跃，一个immutable） - Flush间隔：约20秒 2. **Level配置**： - 数据总量：100MB/s × 7天 = 60.48TB - 使用4-5层，放大因子10 - L0: 10GB, L1: 100GB, L2: 1TB, L3: 10TB 3. **Compaction策略**： - 使用Time-Window Compaction - 按天分区，7天后整个分区删除 - 避免跨时间窗口的compaction 4. **Bloom Filter**： - 10 bits per key（约1%假阳性率） - 总内存占用：约1-2GB 5. **Block Cache**： - 分配100GB给Block Cache - 使用LRU或ARC算法 6. **写缓冲**： - WAL使用独立的SSD分区 - 启用group commit，批大小1MB 7. **并发配置**： - 4个compaction线程 - 2个flush线程 优化要点： - 时序数据天然有序，减少compaction开销 - 利用时间分区实现高效的数据过期 - 大MemTable减少写放大 - 充足的Block Cache提升读性能

练习2.7：自适应索引实现 设计一个简单的Database Cracking算法实现，处理范围查询并逐步优化数据组织。

提示

维护一个裂解索引记录已知的分区边界，每次查询更新这个索引。

参考答案

算法设计： ``` 数据结构： - data[]: 原始数据数组 - crackIndex: 有序的(value, position)对列表 查询处理 RangeQuery(low, high): 1. 在crackIndex中二分查找low和high的位置 2. 如果精确匹配，直接返回范围内数据 3. 否则，执行裂解： a. 找到需要裂解的分区 b. 使用三路快排将分区分为：<low | [low,high] | >high c. 更新crackIndex添加新边界 4. 返回查询结果 裂解函数 Crack(start, end, low, high): left = start right = end mid = start while mid <= right: if data[mid] < low: swap(data[left], data[mid]) left++ mid++ elif data[mid] > high: swap(data[mid], data[right]) right-- else: mid++ return (left, mid) 性能分析： - 首次查询：O(n) - 重复查询相同范围：O(1) - 逐步收敛到O(log n) ``` 实现优化： 1. 使用自适应的裂解粒度 2. 维护访问频率，优先裂解热点区域 3. 定期合并过小的分区 4. 使用并行裂解for大数据集

练习2.8：索引选择成本模型 给定查询工作负载，设计一个成本模型来自动选择最优索引组合。考虑索引创建成本、维护成本和查询收益。

提示

定义成本函数，包括存储成本、更新成本和查询成本。使用贪心或动态规划求解。

参考答案

成本模型设计： **1. 定义成本组件**： ``` 总成本 = 查询成本 + 更新成本 + 存储成本 查询成本(Q, I) = Σ freq(q) × cost(q, I) 其中： - freq(q): 查询q的频率 - cost(q, I): 使用索引集I执行查询q的成本 更新成本(U, I) = Σ freq(u) × |I_affected| × update_cost_per_index 其中： - freq(u): 更新u的频率 - |I_affected|: 受影响的索引数量 存储成本(I) = Σ size(i) × storage_cost_per_GB ``` **2. 查询成本估算**： ``` cost(q, I): if 存在覆盖索引: return index_scan_cost elif 存在部分匹配索引: return index_scan_cost + fetch_cost × selectivity else: return full_scan_cost 其中： - index_scan_cost = log(N) × io_cost - fetch_cost = random_io_cost - full_scan_cost = N × sequential_io_cost ``` **3. 索引选择算法**： ``` 贪心算法： 1. 初始化：I = {主键索引} 2. 重复直到收益为负： a. 对每个候选索引i，计算收益： benefit(i) = cost(I) - cost(I ∪ {i}) b. 选择收益最大的索引i* c. if benefit(i*) > threshold: I = I ∪ {i*} else: break 动态规划（适用于小规模）： dp[mask] = 使用索引子集mask的最小成本 对每个索引组合计算成本，选择最优 ``` **4. 实际考虑**： - **索引交互**：检测冗余索引（如(a,b)包含(a)） - **工作负载变化**：使用滑动窗口跟踪查询模式 - **在线调整**：设置阈值，当收益超过阈值时触发索引调整 - **资源约束**：限制索引总数和总大小 **5. 示例决策**： ``` 工作负载： - Q1: SELECT * FROM t WHERE a=? AND b=? (频率:1000/天) - Q2: SELECT * FROM t WHERE b=? (频率:100/天) - U1: UPDATE t SET c=? WHERE id=? (频率:500/天) 候选索引及成本收益： - Index(a,b): - 查询收益：1000 × (全表扫描成本 - 索引扫描成本) - 更新成本：500 × 索引维护成本 - 净收益：正，创建 - Index(b): - 额外收益：100 × 成本改善（已有(a,b)可部分利用） - 额外成本：500 × 索引维护成本 - 净收益：负，不创建 ``` 这个模型可以集成到数据库的自动索引顾问中，持续优化索引配置。