精读 DDIA（四）：数据库为什么需要这么多种索引

0. 开篇

读这一章之前，我先数了数自己平时打交道的存储：公司里是 Hive 加 Spark，底下的文件是 Parquet；自己 VPS 上跑着 Postgres 和 ClickHouse；中间还夹着一条 Kafka。同样是「存数据、查数据」，为什么我身边要同时存在这么多长得完全不一样的引擎？这一章给了我一个统一的解释框架：查询长什么样，决定了数据该怎么摆。

Feynman 有句话说得准：

“A computer does not primarily compute… they primarily are filing systems.”

最简单的数据库可以只是一个文件：

db_set () { echo "$1,$2" >> database; }
db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

写入很快，因为只是把一行追加到文件末尾。读取很慢，因为要从头到尾扫描整个文件——1 亿条数据，平均要扫 5000 万行。

为了让读变快，需要索引。但索引不是免费的：它占额外存储，写入时要同步维护，还增加系统复杂度。所以数据库不会自动给所有列建索引，建哪个索引，取决于查询是什么样子的。

这也是本文想回答的问题：为什么数据库需要 B-tree、LSM-tree、列存、倒排索引、向量索引这么多种结构？答案一句话就能说完——不同的查询需要不同的找数据方式，找数据的方式不同，底层结构也就不同。剩下的篇幅，是把这句话拆开看。

1. 每种结构都是被一个具体问题逼出来的

存储结构不是凭空出现的，按时间捋一遍就能看出来：1970 年 Bayer 和 McCreight 发表 B-tree 论文，解决的是磁盘上的点查和范围扫描，九年后它已经被称为 “ubiquitous”；1996 年 LSM-tree 论文出现，那时互联网日志、搜索引擎索引这类写密集负载刚刚冒头，B-tree 的随机写成了瓶颈；2005 年 C-Store 论文带火列存，针对的是分析查询「只用三列却要读一百列」的浪费；2016 年 HNSW 论文解决高维向量的近似最近邻，几年后被 RAG 推着走进了工业界。

这条线说明一件事：新结构不是为了取代旧结构，而是为了处理新的查询场景。B-tree 没有消失——今天 PostgreSQL 的默认索引仍然是这个 1970 年的发明；LSM-tree 没有统一所有数据库；列存也没有替代行存；向量索引更不是传统索引的终点，RAG 系统在它之外照样要依赖结构化过滤。

DDIA 第 4 章的价值，是把这些结构背后的权衡逐个拆开。

2. 先分清两个层次：索引和数据结构

很容易把「索引」和「数据结构」混为一谈，但它们不在同一层。数据结构回答「数据怎么组织」，是计算机科学的基础概念，比如数组、哈希表、B-tree；索引回答「目标数据在哪里」，是数据库里的工程概念，比如主键索引、联合索引、倒排索引。两者的关系是：索引通常由某种数据结构实现。B-tree 是数据结构，B-tree 索引是用 B-tree 实现的索引。

同一种索引在不同系统里可以用不同的数据结构实现——同样叫「主键索引」，PostgreSQL 用 B-tree，RocksDB 用 LSM-tree。用途相同，实现不同。

分清这一点之后，后面的 B-tree、LSM-tree、列存、倒排、向量就不是孤立的知识点了，它们都在回答同一个问题：怎么针对某种类型的查询，设计一种更便宜的找数据方式。

3. B-tree：面向稳定点查和范围扫描

1970 年前后的数据库面对几个约束：数据主要在磁盘上，内存远小于磁盘，查询既要按 key 找一条记录，也要扫一个范围。哈希表点查快但不支持范围；排序数组支持范围但插入要挪动后面所有元素。B-tree 想同时满足三件事：点查快、范围快、插入代价可控。

它的做法是把索引组织成一棵很矮的多叉树，每个节点对应一个磁盘页（page，通常 4 到 16 KiB）：根页告诉你 key 应该去哪个子页找，一层层走下去，直到存着 key 和记录位置的叶子页。

3.1 为什么查找快

关键在分支因子（branching factor）：一个页通常能放几百个子页指针。假设是 500 个：

• 走 1 层，搜索范围从 1 亿缩到 20 万
• 走 2 层，缩到 400
• 走 3 层，已经到叶子页了

所以 1 亿条记录，B-tree 只要 3-4 次磁盘读取就能找到任何一条。每往下走一层，搜索范围缩小到原来的几百分之一，这是它快的根本原因。范围扫描也顺：叶子页之间有指针连成链，找到起点后顺着读下去就行。

3.2 写入路径

写入先根据 key 找到目标叶子页，写一条 WAL（预写日志，保证崩溃后能恢复），然后在原位置覆盖修改；页满了就分裂成两个页，父页满了继续向上分裂。

B-tree 维护的是一套可以原地更新的页结构，这带来两个特征：读取路径稳定，每次查找都是从根到叶子的固定步数；写入时可能要修改磁盘上分散的页，产生随机 I/O。

3.3 适合什么，卡在哪里

SELECT * FROM orders WHERE order_id = 10001;

SELECT * FROM orders
WHERE created_at >= '2026-01-01'
  AND created_at < '2026-02-01';

这两类查询的共同点是条件能沿着有序的 key 一步步缩小范围，正是 B-tree 的主场。PostgreSQL、MySQL InnoDB、SQLite 的默认索引都是 B-tree 或其变种。

它卡在两种场景上。一是写入量非常大时，分散的页修改让随机写成本上升；二是分析型查询——表有 100 列、查询只用 3 列，B-tree 所在的行存布局要把 97 列无关数据一起从磁盘读上来。前者引出 LSM-tree，后者引出列存。

4. LSM-tree：面向写密集场景

LSM-tree（Log-Structured Merge-tree）的目标只有一个：让所有写入都变成顺序写。顺序写在机械硬盘上比随机写快几百倍，在 SSD 上也快好几倍——把写入全变成顺序的，写吞吐就能抬一个数量级。

4.1 写入路径

写入不直接落盘。一次写做两件事：把记录追加到 WAL 文件末尾（顺序写），再插入内存里一个有序结构 memtable（红黑树或跳表，纯内存操作）。用户感知的写入延迟就是这两步之和，没有寻页，不改任何已有数据。

memtable 攒到几 MB 到几十 MB 后，整个一次性顺序刷到磁盘，形成一个 SSTable（Sorted String Table）文件——写完就不再修改。修改一个 key 是写入新版本，旧版本还在；删除是写入一条 tombstone 标记。后台的 compaction 任务不断把多个 SSTable 合并，顺便清掉旧版本和被删除的数据。

4.2 读取为什么不算慢

数据散在 memtable 和一堆 SSTable 里，读取看起来要查很多地方，但有两个机制兜底。第一，每个 SSTable 内部是排好序的，还带稀疏索引，单文件内查找是 O(log n)。第二，每个 SSTable 配一个 Bloom filter——每个 key 只占大约 10 个 bit 的小位图，能快速回答「这个 key 一定不在这个文件里吗」。误判率能压到 1% 以下，也就是说查 100 个 SSTable，平均只需要真正读 1 个左右。整体读取仍在毫秒级，比 B-tree 慢，但不会慢一个数量级。

4.3 代价

LSM-tree 的账单记在别处：一次读可能要碰多个文件；同一条记录会在一轮轮 compaction 里被反复重写（写放大）；旧版本和 tombstone 在合并前一直占着空间；compaction 本身是 IO 密集任务，跑起来会跟前台读写抢资源。

写这节的时候我才意识到，离我最近的 LSM-tree 一直藏在眼皮底下：RocksDB 是它的代表实现（Facebook 2012 年从 LevelDB fork 出来的），而 Flink 最常用的状态后端就是 RocksDB——我们天天在用，只是从来没往「存储引擎」这个方向想过。ClickHouse 的 MergeTree 虽然不是严格的 LSM-tree，但「不可变文件 + 后台不断合并」的思路是同源的，怪不得叫这个名字。

5. B-tree 与 LSM-tree 对照

两者解决的是同一类问题：在磁盘上维护一个按 key 可查的数据集合。差别全在写入路径上——B-tree 维护一套可原地更新的页结构，LSM-tree 维护一组不断合并的不可变文件。

拿具体场景过一遍：订单系统读写都重、点查频繁、延迟要稳，选 B-tree；用户行为日志写远多于读、数据只增不改，选 LSM-tree；按时间范围查询的时序数据，关键不在引擎叫什么名字，而在数据能否按查询条件形成有序排列。

6. 列存：面向大规模扫描

分析查询长这样：

SELECT category, SUM(qty) FROM fact_sales
WHERE year = 2024 GROUP BY category;

表有 100 列、10 亿行，查询只用 3 列。行存必须把每行 100 列都读上来再丢掉 97 列。列存的思路是把同一列的数据连续放在一起，查询只读需要的列。好处不止省 I/O：同一列里类型相同、值分布相似，压缩率高得多；引擎可以一次处理一批列值做向量化执行；每个数据块还能带上 min / max 元数据，让查询直接跳过无关的块。

一个常见误解是列存等于「一个字段一个文件」。实际上 Parquet 通常还是单个文件，内部先横切成多个 row group，每个 row group 里再按列组织：

一个 Parquet 文件
├── Row Group 1
│   ├── Column chunk: user_id
│   ├── Column chunk: category
│   └── Column chunk: amount
├── Row Group 2
│   └── ...
└── Metadata（每列的 min / max / null count / offset）

查询引擎根据 metadata 定位需要的列块，只读那些字节范围。

这里有个容易吃亏的点：Parquet / ORC 本身不会自动排序，排不排序由写入任务决定。不排序时每个 row group 的 min / max 可能覆盖整列的取值范围，什么都跳不过；按过滤列排好序，min / max 变窄，大部分数据块直接跳过。同一个道理在 ClickHouse 里更明显——建表时的 ORDER BY 不是普通索引，它决定数据在磁盘上的物理排列顺序。我自己在 VPS 上建 ClickHouse 表的时候，最花心思的也是这个：ORDER BY 选什么列，直接决定后面查询能不能裁剪掉大部分数据。

工程对应：文件格式有 Parquet、ORC、Lance；数仓产品有 ClickHouse、Snowflake、BigQuery；查询引擎有 DuckDB、Trino、Spark SQL。

7. 物化视图和数据立方体

除了索引，还有一条加速路线：提前把结果算好。

普通视图只是保存一段 SQL，每次查询展开重跑；物化视图把查询结果真正存下来，查询直接读结果。代价是占额外存储、底表变化要刷新、刷新有延迟、维护逻辑更复杂——用空间和更新成本，换读取速度。

这个概念对做数仓的人一点都不陌生：ADS 层那些按天聚合的汇总表，本质上就是手动维护的物化视图，调度任务负责「刷新」。区别只是有的系统把这件事自动化了——ClickHouse 的 MATERIALIZED VIEW 在写入时顺带维护，Materialize 干脆做成增量计算。

数据立方体（data cube）是更激进的预聚合：日期、地区、类目三个维度，把所有维度组合的聚合结果全部提前算好。问题是维度一多组合数量爆炸。而且在现代列存系统里，明细扫描本身已经很快，cube 从默认选择退成了特定场景（查询模式稳定、维度可控）下的加速结构。

8. 多维、倒排、向量索引

前面的结构处理的都是结构化数据，但现实里的查询还有别的形状：地图上圈一个范围、按关键词搜文档、找语义相似的内容。每种形状对应一类新结构。

8.1 多维索引

前面讲的索引都是按一个维度排序的：B-tree 把数据按 key 从小到大排好，所以「找一个范围」才快。但地理查询天然是两个维度的——比如找出某个矩形范围内的所有餐厅：

SELECT * FROM restaurants
WHERE lat BETWEEN 30.20 AND 30.30    -- 纬度
  AND lng BETWEEN 120.10 AND 120.20; -- 经度

直觉上，给 lat、lng 两列建一个联合索引（把两列拼在一起排序的 B-tree）应该能解决。但它不行，原因在于联合索引只是先按 lat 排、lat 相同再按 lng 排，本质还是一条按 lat 排好的长队。

用电话簿打个比方：电话簿先按姓排，姓相同再按名排。要找「姓在 A–M 之间」很快，因为这是连续的一段。但要找「姓在 A–M 之间且名在 A–M 之间」，你只能先翻到姓 A–M 那一大段，再在里面一个个挑名字符合的——符合的人散落在这一大段的各个角落，并不连续。

(lat, lng) 索引就是这样：它能快速圈出 lat 在 30.20–30.30 的所有点，但这些点的 lng 什么值都有，还得逐个过滤。维度一多，一维排序就照顾不过来了。解决办法有两类。

第一类：R-tree——直接用矩形把点分组。

R-tree 不再把点排成一条队，而是把位置相近的点圈进一个矩形框（也叫 bounding box，外接矩形），再把相近的矩形框圈进更大的框，一层层套起来形成一棵树。查询时，只要你的查询范围和某个框不相交，框里所有点就整体跳过，连看都不用看。这样二维范围查询也能像 B-tree 那样层层缩小搜索范围。PostgreSQL 的地理空间扩展 PostGIS 就用这种结构。

第二类：空间填充曲线——把二维「压扁」成一维。

如果还是想用现成的一维 B-tree，就得想办法把二维坐标变成一个一维的数，而且要尽量做到二维上挨得近的点，算出来的一维数也挨得近。空间填充曲线就是干这个的：想象一条蜿蜒的线，按某种固定顺序穿过地图上每一个格子，一个点落在这条线的第几步，就是它的一维编号；挨得近的点编号通常也挨得近，于是又能用普通的有序索引来查。常见的画法有 Z-order 曲线和 Hilbert 曲线。Delta Lake 的 ZORDER BY 就是用这个思想，把相关的数据在文件里聚到一起，让过滤查询能跳过大量无关文件。

8.2 倒排索引

普通索引是文档 ID 指向文档内容，倒排索引反过来：词指向包含这个词的文档列表。

apple → [doc1, doc3, doc8]
red   → [doc1, doc8]

查询 red AND apple 等于两个 posting list 取交集。

这种结构适合的数据形状是「维度极多、但每条数据只在少量维度上有值」——整个词表几万个词，每篇文档只包含其中一小撮。抽象层面它和列存的 bitmap encoding 很接近，都是「某个值指向一组行号」；但全文搜索还叠加了分词、词频、BM25 相关性排序这些语义，不能完全画等号。

8.3 向量索引

倒排索引依赖关键词重合。但用户搜「取消订阅」，文档标题是「关闭账户」——没有共享词，语义却接近。向量索引用 embedding 模型把文本转成高维浮点向量，在向量空间里查最近邻。常见的三种做法：Flat 暴力扫描所有向量，精确但慢；IVF 先聚类，查询时只搜最相关的几个簇；HNSW 用分层图结构把查询压到近似 O(log n)。后两者用一点精度换数量级的速度——结果可能不是最精确的最近邻，但足够近。

向量索引不是传统索引的替代品，而是又一种新的找数据方式。在 RAG 系统里它通常和结构化过滤、关键词召回、rerank 配合使用，谁也离不开谁。

9. 选型权衡

每种结构都在读性能、写性能、空间占用三个目标之间做权衡，这就是 DDIA 引用的 RUM conjecture（Read-Update-Memory）：每一种「读得更快」，都要在别处付费——B-tree 付的是随机写和页维护，LSM-tree 付的是读放大和空间放大，列存付的是单行更新的复杂度，物化视图付的是刷新成本，向量索引付的是精度和内存。没有免费的结构。

所以选型不能只问「哪个更快」，要问「它让哪类查询更快、把成本转移到了哪里」。而回答这个问题的前提，是先看清自己的查询长什么样：

10. 收尾

回到开篇那个问题：为什么我身边要同时存在 Hive、ClickHouse、Postgres、Kafka 这么多引擎？读完这章的答案是：因为我的查询本来就长得不一样——跑批聚合、点查配置、追加日志，每一种都值得一套为它优化的摆放方式。

这些结构没有谁彻底取代谁，它们只是把成本放在了不同的地方：有的牺牲写入换读取稳定，有的牺牲读取稳定换写入吞吐，有的牺牲空间换查询速度，有的牺牲精度换近似搜索。工程选型的第一步不是比较产品名，而是看清楚自己要回答的查询是什么样子。