2.2 核心索引算法实现

2.2 核心索引算法实现

本节摘要：索引是加速查找的结构，但它从来不是免费的午餐。B+ 树用树的高度换有界的随机 I/O，代价是页分裂带来的写放大；LSM-Tree 用顺序写换高写入吞吐，代价是读放大；哈希索引用确定性换点查的极致，代价是完全放弃范围查询。本节讲清三者如何定位数据、如何应对写入、在读放大与写放大之间如何取舍，最后给出一张选型决策矩阵。读完你能解释：为什么关系库默认 B+ 树，日志型存储偏爱 LSM，缓存类系统拥抱哈希。

先说结论

阅读完本节，你应当能够：

1. 说清 B+ 树为什么范围查询快，以及页分裂如何带来写放大
2. 解释 LSM-Tree 的分层结构与归并机制，读放大、写放大、空间放大从何而来
3. 区分链地址与开放寻址两种哈希冲突处理方式，理解装载因子阈值的意义
4. 面对一个具体负载，能在 B+ 树、LSM-Tree、哈希索引之间做出有理由的选型
5. 说出布隆过滤器、填充因子、分层归并与分级归并这些工程手段各自的作用

一、问题与直觉

上一节我们把数据摆好了，但这只解决了"存"，没解决"找"。一张几亿行的表，即便布局合理，如果没有索引，点查一条记录仍然只能全表扫，把整张表从磁盘搬进内存再逐行比对。索引要解决的，就是"别把没用的页读进来"——它把"键在哪"这件事，用更小的代价提前编码下来。

但索引本身就是一份数据的副本，它也要占空间、也要被写入、也要被维护。于是出现了一个所有索引都绕不开的账本：读放大与写放大。读放大，指一次逻辑读实际要访问的额外数据量；写放大，指一次逻辑写实际触发的物理写量。这两个数此消彼长，任何索引结构本质上都是在它们之间下注。下注的方式不同，就分化出了 B+ 树、LSM-Tree、哈希索引三条路线。把索引想成一份"为查找而重排的副本"，就更容易理解它为什么一定有代价：副本要占空间，重排要花写入，而让哪种查询省力、让哪种写入省力，就是路线分化的起点。

二、B+ 树：把随机 I/O 控制在树高之内

B+ 树是关系数据库的事实标准。它的设计动机很直接：磁盘随机 I/O 贵，那就把树造得矮而胖，让从根到叶一次寻路只做很少几次随机读。内部节点只存键和指针，不存数据；所有数据都下沉到叶节点，叶节点之间再用链表首尾相连。这样一个节点能装很多键，扇出大，树高增长极慢，几十亿行也只要三四层。

范围查询是 B+ 树的招牌。要找键在某个区间内的所有记录，先沿树导航到起始叶节点，然后顺着叶节点链表一路顺序读下去，不必反复上下树。这正是行式布局加主键聚簇时最舒服的形态——主键范围查询等于顺序扫一段叶子。树高的威力可以用扇出量化：一个 4KB 的节点，键和指针各占若干字节，一个节点能装几百个键，三层树就能覆盖上亿条记录。也就是说，从根到叶只需三次随机 I/O，之后的范围扫描全是顺序读。这就是 B+ 树能同时服务点查和范围查询的底气——它把"寻路"压缩成树高次随机读，把"遍历"交给叶子链表上的顺序读。

但 B+ 树的"平衡"不是免费的。插入一个新键，可能把某个叶节点撑爆，触发页分裂：一页裂成两页，还要把中间键上提到父节点；父节点满了又继续往上裂，最坏一路裂到根，树才长高一层。一次逻辑插入，可能伴随多次物理页写——新页落盘、父节点改写、旧页标记垃圾。这就是 B+ 树的写放大来源。分裂路径上的锁竞争，还容易在高并发写入热点键区间时形成延迟尖刺。

工程上有一堆手段来驯服分裂：填充因子控制页里预留多少空闲，让新插入有地方落脚；延迟分裂把可以再等等的分裂往后拖；无锁的 B-link 树用原子指针替换和版本号校验规避锁竞争。它们共同的思路，是让 B+ 树在"确定的有界随机 I/O"这个优点不被破坏的前提下，把写放大压下来。

三、LSM-Tree：用顺序写换吞吐

B+ 树的痛点是随机写。LSM-Tree 干脆换个思路：既然顺序写比随机写快一个数量级，那就让所有磁盘写都变成顺序追加。这正是上一节 SSTable 与 MemTable 那套机制的完整展开。

写入路径极其简单：写请求先落到内存里的 MemTable，再同步落一条 WAL 保命，之后立刻返回——写入延迟约等于一次内存写加一次顺序日志追加，吞吐极高。MemTable 满了冻结成 Immutable MemTable，后台把它排序后顺序刷成一个 SSTable。磁盘上的 SSTable 只读不可变，永远不需要原地修改，也就不产生随机写。

代价转到了读上。一个键可能散落在 MemTable、若干 L0 文件、以及更深的各层里，点查得逐层找。于是 LSM 用分层和归并来管理：L0 层的文件键范围互相重叠，数量少但要点查多个；L1 层开始键范围不重叠，可以二分跳过。后台的归并任务不断把下层文件合并、去重、清旧版本，让读放大保持在一个可控范围。归并有两种主流策略：分层归并每层只维持一个有序文件集合、归并精准，读放大小；分级归并每层多个文件、归并吞吐高，但读放大略大。选哪种，就是在"写吞吐优先"还是"读延迟敏感"之间表态。具体到参数，层间容量倍数通常是十倍左右：L0 到 L1 的归并频繁但每次数据量小，越往下归并越稀疏但单次越大，摊到每次写入上的写放大趋近对数级。布隆过滤器再给点查兜底——它让大多数"键不存在"的查询在碰磁盘之前就被否定，这是 LSM 能把读放大压到能用的关键补丁。

读放大之外，LSM 还有空间放大：同一个键的多个版本在归并之前同时占据空间。三者构成一个不可能三角——写放大、读放大、空间放大，压一个，另外两个就抬头。工程上靠布隆过滤器压读放大（每个 SSTable 配一个，用不到百分之一的内存提前过滤绝大多数不存在的键），靠更大的层间倍数压写放大，靠更激进的归并压空间放大。这个三角没有全局最优，只有按负载调出来的局部最优。

图：B+ 树与 LSM-Tree 的取舍对比

四、哈希索引：点查的极端

哈希索引走的是另一条极致路线：如果只要精确匹配，何必排序？给定键，用哈希函数算出桶号，直接跳到那个桶，理想情况下 O(1) 完成点查。内存数据库的字典、缓存系统的键值存储，都靠它把延迟压到最低。

哈希冲突是绕不开的现实问题，两个主流解法各有脾气。链地址法让每个桶挂一个链表，冲突键往后挂，实现简单、扩容平滑，但链表遍历破坏缓存局部性，最坏退化成线性。开放寻址法在冲突时按探测序列找下一个空槽，数据连续存储、缓存友好，但删除要留墓碑标记，而且装载因子一旦超过约七成，性能会陡降。内存数据库普遍选开放寻址，再配渐进式扩容：装载因子到阈值，后台把数据往双倍大的新表迁，期间读写由新旧两表一起服务，迁移完成才切走。渐进式扩容把一次性的昂贵搬迁，拆成后台的一连串小步，避免查询卡顿。哈希函数的选择也讲究：要快、要均匀、要稳定。Murmur 和 xxHash 这类非加密哈希正是为此而生，它们不求抗碰撞，只求把键均匀撒进桶里，让每个桶都尽量轻。

哈希索引的致命短板，恰恰是它存在理由的反面：它回答不了任何范围查询、前缀查询、排序。要找某个前缀、要按分数倒序、要求最小值，纯哈希一概无能为力。所以它很少单打独斗，更多是作为加速层嵌进更大的结构里：等值连接的构建阶段、点查为主的键值引擎、向量检索的粗筛层，都能看到它的身影。

五、选型决策矩阵

三条路线的轮廓已经清楚。真实系统里它们很少非此即彼，常常组合出现——InnoDB 主键是聚簇 B+ 树，二级索引是非聚簇 B+ 树；RocksDB 默认 LSM，MemTable 层可选跳表或哈希链表；DynamoDB 用哈希把分区键路由到分片，再在分片内为排序键维护有序结构，实现"哈希加范围"的混合语义。组合是常态，但每个组合单元内部，仍然逃不出下面这张表划出的三个象限。落到单个索引上，选型依然有迹可循：

这张表是罗盘，不是判决书。真实选型还要看运维复杂度、团队熟悉度，以及能否和现有的事务与恢复机制咬合——比如一个已经重度依赖原地更新的系统，硬上 LSM 只会让一致性层反复返工。

⚠️ 常见坑：拿 LSM-Tree 去扛"范围扫描为主"的读负载，等于自己给自己找读放大——每一层文件都要打开合并，延迟毛刺会频繁出现。反过来，拿 B+ 树去扛海量小写入，页分裂会让写放大和延迟抖动一起恶化。索引不是越新越好，是越合身越好。

💡 关键直觉：判断一个索引合不合适，别背复杂度表，就数两笔账——一次典型读要碰多少额外数据，一次典型写要触发多少物理写。读放大和写放大，是索引世界里唯一硬通货。

重点提炼

• 索引是数据的一份副本：它把"键在哪"提前编码，代价是额外的空间和维护开销。
• B+ 树矮而胖，范围查询顺叶链：范围查询是招牌，页分裂是写放大来源。
• LSM-Tree 把磁盘写全部变成顺序追加：写入吞吐极高，代价是读放大和空间放大。
• 归并有分层与分级两种：分层读放大小，分级写吞吐高，选择即表态。
• 哈希索引只服务点查：开放寻址缓存友好但怕高装载，链地址简单但怕冲突退化。
• 读放大、写放大、空间放大构成不可能三角：压一个，另外两个就抬头。
• 选型看负载，不看潮流：点查均衡用 B+ 树，写多读少用 LSM，纯点查用哈希。

到这里，数据怎么摆、怎么找已经讲透。下一章我们把视角从"单个结构"拉到"多个并发操作"——事务如何保证一致性、并发控制如何避免互相踩踏，而这些机制的载体，正是本章的页与索引。