存储与检索

一句话

第 2 章谈的是「站在应用视角，数据长什么样」；第 3 章下沉一层，问一个更硬核的问题：数据库到底怎么把数据写到磁盘上、又怎么再找回来？全章的骨架是两组对立——存储引擎有两大家族：日志结构（LSM-tree）与页面结构（B-tree）；工作负载也有两大家族：事务处理（OLTP）与分析处理（OLAP），后者催生了列式存储。看懂引擎里发生了什么，你才选得对、调得动那台数据库。

Glossary · 术语表

坐标

本章仍属 Part I「数据系统的基石」。第 2 章向上看——你用关系 / 文档 / 图怎么给数据建模；第 3 章向下看——这些数据落到磁盘上究竟怎么摆、怎么找，紧接着第 4 章讲「怎么把它编码成字节、又不失兼容」。落到现实，这一章对应的正是你天天要做的决策：该用 MySQL 还是 Cassandra？为什么这条分析查询扫了半天？某张表要不要再加个索引？不看懂引擎，这些都只能靠拍脑袋。

这章要解决什么

你多半不会去手写一个存储引擎，但你必须选一个、还得会调。选错的代价是实打实的：一台为事务调好的数据库拿去跑分析，会慢到没法用；反过来也一样。要选得明白，你得对「盖子底下发生了什么」有个粗略但正确的心智模型。

而这心智模型的起点，是一个朴素到近乎荒谬的事实：最简单的数据库，就是往一个文件末尾不停追加。写是 O(1)——追加一行，快得离谱；可读是 O(n)——要找一条得从头扫到尾，数据一大就崩。于是就有了索引，以及贯穿全章的那条铁律：任何索引都在拿「写变慢」换「读变快」。这章要回答的就是：真实引擎是怎么索引的，各自把这笔账算到了哪一边。

核心内容，讲透

① 索引的本质：一份「以写换读」的派生结构

DDIA 用几行 shell 起手：db_set 把 键,值 追加进文件，db_get 用 grep 从头找最后一条。写极快、读极慢。要救读，就得维护索引（index）——一份从主数据派生出来的额外结构。核心权衡一句话说尽：索引让读更快，却让写更慢，因为每次写都得连带更新每一个相关索引。所以数据库默认不会替你索引一切，索引选哪些列，是你要做的取舍。

② 日志结构家族：哈希索引 → SSTable → LSM-tree

最朴素的索引是内存里的一张哈希表：键 → 该键在日志文件里的字节偏移量。写：追加到日志、更新哈希表；读：查表拿到偏移、直接跳过去读。这就是 Bitcask（Riak 的默认引擎）。快，但两个硬伤：哈希表必须整个塞进内存；键无序，范围查询（「找出 100 到 200 号之间的所有键」）没法做。而且日志只增不减，迟早撑爆磁盘——解法是切成段（segment），后台做压实（compaction）：合并旧段、每个键只留最新值，删除用墓碑标记（tombstone）。

把段文件按键排好序，就升级成 SSTable（Sorted String Table，排序字符串表）。仅仅「有序」这一点就带来三个大好处：其一，合并像归并排序一样流式进行，不必把整段读进内存；其二，索引可以稀疏——每隔几 KB 记一个键就够，读时先定位到大致区间再顺序扫；其三，同区间的记录能成块压缩再落盘，省空间也省带宽。

可写入是乱序来的，磁盘上怎么维持有序？答案是分层：内存里维护一棵有序的平衡树（叫 memtable，红黑树 / 跳表都行），写先进 memtable；等它涨到几 MB，就整棵刷成一个有序的 SSTable 段落盘、此后不再改动。读时先查 memtable，再从最新到最旧翻 SSTable。后台不断把小段压实成大段。为防 memtable 在崩溃时丢失，写 memtable 之前先追加一份 WAL。

这套结构就是 LSM-tree（Log-Structured Merge-Tree，日志结构合并树），源自 Patrick O'Neil 等人 1996 年的论文。LevelDB、RocksDB、Cassandra、HBase、ScyllaDB 都是它，全文搜索引擎 Lucene 的词典也用同一思路。一个关键优化是 Bloom filter（布隆过滤器）：一种极省内存的概率结构，能快速判断「这个键肯定不在某个段里」，从而免掉一次注定扑空的磁盘读——查不存在的键时尤其省。

③ 页面结构家族：B-tree，业界标准

B-tree 是用得最广、最标准的索引——几乎所有关系数据库、许多非关系库都用它。它和 LSM 的思路正相反：不是把数据库切成变长的日志段追加，而是切成固定大小的页（page）（传统 4 KB），一次读写一整页。页与页之间用「磁盘地址」互相指引，像内存指针、只是指向磁盘。一页是根，里面放着若干键和指向子页的指针；顺着指针逐层往下，直到存着真实值的叶子页（leaf page）。

每页能放的子页数叫分支因子（branching factor），通常有几百——所以树很「矮胖」，深度是 O(log n)。DDIA 给的量级很直观：分支因子 500、4 KB 页、4 层就能存 256 TB，任何一条记录最多翻 4 页就能找到。改数据是原地覆写（update in place）：找到对应叶子页，改完把整页写回原位；页满了就分裂（split）成两页、更新父页指针。这一点和 LSM「从不改旧文件」形成鲜明对照。

原地覆写有个可靠性隐患：一次页分裂要改好几页，若中途崩溃就可能只写了一半、把树写坏。B-tree 的对策是也上一份 WAL（这里叫 redo log 重做日志）——每次改页前先把改动追加进日志，崩溃后照日志重放恢复。多线程并发访问同一棵树，还要用轻量锁（latch）保护，防止读到写了一半的页。

④ 其他索引：次级、聚簇、覆盖、多列、纯内存

上面讲的是主键索引，实践里还有一堆变体，随名即释：次级索引（secondary index）——在非主键列上再建目录（如按邮箱查用户），LSM 和 B-tree 都能建。聚簇索引（clustered index）——干脆把整行数据直接塞进索引的叶子页，查到即得、不用二次回表，MySQL 的 InnoDB 主键就是这样。覆盖索引（covering index）——索引里多带几列，让某些查询「只读索引就够、不碰主表」。多列 / 联合索引（multi-column index）——把几列拼成一个键，地理查询则用专门的 R-tree。还有纯内存数据库（Redis、Memcached、VoltDB）：它们快，主要不是因为「省了读磁盘」，而是省掉了「为了能落盘而把内存数据结构编码成字节」的开销。

⑤ 另一个世界：OLTP vs OLAP，与列式存储

前面全是OLTP——每次读写少量记录、按键快速点查，撑着你的下单转账。但公司还有另一类活：OLAP（分析）——一条查询要扫过几百万甚至几十亿行，却只关心其中少数几列（如「按地区、按月，销售额总和」）。用 OLTP 的行式存储硬跑分析，等于为了算一列平均值、把每一行整个从磁盘搬进来再扔掉大半——极其浪费。所以企业普遍另建一个数据仓库（data warehouse），通过 ETL（抽取-转换-加载）把业务库的数据搬过去专门跑分析，schema 常是星型模型（中间一张事实表，四周挂若干维度表）。

数据仓库的杀手锏是列式存储（column-oriented storage）：不再「一行的所有列挨着存」，而是「一列的所有行挨着存」。分析查询只读它要的那几列，磁盘 I/O 立刻降下来。更妙的是同一列的值高度相似（比如「城市」列反复就那几百个值），压缩率极高——DDIA 讲的 位图编码（bitmap encoding）加游程编码，常能把列压到原大小的零头，再配合 CPU 的向量化批处理，分析吞吐能比行式高一到两个数量级。代价是写入变麻烦：插一行要拆开写进每一列，所以列存几乎只用于「批量导入、大量查询」的分析场景，不用于频繁改动的在线业务。

关键权衡与选型

这一章的灵魂是三组取舍。先看引擎两大家族——LSM-tree vs B-tree，这是选数据库时最该心里有数的一张表：

表 1 · LSM-tree（日志结构） vs B-tree（页面结构）

第二组是工作负载——行式 OLTP vs 列式 OLAP，本质是「点查少量记录」还是「扫海量行、只取几列」：

表 2 · 行式 OLTP vs 列式 OLAP

第三组贯穿始终：索引本身的取舍——多一个索引，读快一分、写慢一分、还多占空间。所以别给每列都建索引；给真正常用于查询条件的列建。业界把这类取舍归纳成 RUM 猜想：读放大（Read）、写放大（Write/Update）、空间放大（Memory）三者不可能同时最优，优化一个往往牺牲另外两个——LSM 压低写放大却抬高读放大，B-tree 反之，恰是这条猜想的活样板。

为什么重要 / 落到真实系统

这一章给了你一副透视眼镜：看到 Cassandra / HBase / RocksDB，你知道底下是 LSM，写吞吐高、省空间、但压实会抢带宽；看到 PostgreSQL / MySQL InnoDB，你知道是 B-tree，读稳、事务强、原地覆写；看到 Redshift / BigQuery / Snowflake / ClickHouse，你知道是列式，为「扫海量、算几列」而生，别拿它跑高频点查。面试里问「为什么写密集选 Cassandra、为什么分析另建数仓」，答案全在这三组取舍里。而这些论断不是纸上谈兵——大厂用公开可查的实践替它们背了书：

易错点与争议

• 「LSM 一定比 B-tree 快」——错。LSM 写吞吐高，但后台压实会跟前台读写抢磁盘带宽，造成高分位（p99）延迟毛刺；某些负载下写放大反而更严重。B-tree 的延迟更可预测。选型要看你更怕「平均慢」还是「偶尔卡」。
• 「索引越多越好」——错。每个索引都在拿写速度和空间换读速度。给不常用于查询的列乱建索引，只会拖慢写、白占地。
• 拿 OLTP 库直接跑分析。在业务主库上跑大报表，既拖垮线上事务、又慢——这正是数据仓库和列式存储存在的理由，别混用。
• 误解纯内存数据库「快在省了磁盘读」。真正的大头是省掉「为落盘而编码 / 解码」的开销；有些内存库甚至能管理超过内存大小的数据集。
• 时代局限（2017）。此后 NVMe SSD 把随机写的惩罚大幅拉平、键值分离（如 WiscKey）等新设计削减了 LSM 写放大、「学习型索引」也在探索用模型替代 B-tree；但「日志结构 vs 页面结构、行式 vs 列式」这套分类框架至今稳固。
• SSD 寿命。LSM 的反复压实会放大写、磨损闪存；但 B-tree 每次也要覆写整页——两边都非零成本，要按写入模式权衡。

要点