在数据库的使用中，性能问题十有八九与索引有关：查询莫名变慢、写入突然抖动、磁盘悄悄涨满，背后多半是某种索引结构的特性在起作用。市面上的数据库五花八门，拆到最核心处，索引结构其实只有四条主线——B+ 树、LSM 树、倒排索引，以及 AI 时代走上舞台中央的 HNSW 近邻图。理解它们各自优化了什么、又付出了什么代价，选型与调优就有了共同语言。本文按"为什么需要索引 → 四种结构逐一拆解 → 总对照 → 组合现实"组织全文，最后给出总结与练习。
1、全表扫描的代价
没有索引时，数据库回答任何过滤问题都只有一招：全表扫描。以一张 1000 万行、每行约 1 KB 的表为例，全表约 10 GB；即使按 InnoDB 的 16 KB 页切分，也要顺序读 60 多万个页才能扫完。顺序读在 SSD 上并不算慢，问题在于查询可能只命中其中 3 行——为 3 行数据搬运 10 GB，成本与表大小成正比，表越大越不可接受。
索引的本质是一笔交易：用额外空间与写入开销，换读取时少搬数据。把某一列（或几列）组织成利于查找的结构，定位成本就从"与表成正比"降到"与表规模的对数成正比"。这与字典的部首目录、书本的目录页是同一个思路，区别只在于数据库把工程做到极致，分化出了四条各有所长的路线。
还要先泼一盆冷水：索引不是越多越好。每个索引在写入时都要同步维护，无脑加索引把写入拖垮、把磁盘塞满是常见的线上事故。理解每种结构的维护代价，正是后面几节的主线。
2、B+ 树：有序世界的王者
B+ 树是多数人接触的第一种索引，直觉上它就是一棵"矮胖的多叉排序树"。用一棵三层的示例看它的形状，节点内是键，虚线是叶子间的链表：
这张图有两个关键设计。其一，数据全部在叶子层：内部节点只存路由键与子指针，不存行数据，因此单个节点能塞下几百上千个路由项。其二，叶子之间用链表串起来（图中虚线），这根链是范围查询的秘密武器。
为什么这么矮？树的高度由扇出（每个节点的分叉数）决定。二叉树的扇出是 2，10 亿个键要 30 层，最坏 30 次页访问，且每次都是随机读。B+ 树的一个节点就是一页：16 KB 的页按每个路由项二三十字节算，轻松容纳数百个分叉；按每节点 500 分叉计，两层可导航 25 万键，三层 1.25 亿，四层 625 亿。也就是说，10 亿行的表定位任意一行只需 3～4 次页访问，而树顶几层几乎总在内存缓存里，实际磁盘 IO 往往只剩一两次。
范围查询快就快在叶子链上。WHERE id BETWEEN 35 AND 60 这类查询，先沿树下降定位到 35 所在的叶子，之后完全不再回到树里，直接沿链表向右顺序扫到 60 为止。结果集在叶子层连续存放，全程顺序 IO；等值查询只是范围查询的特例。
正因如此，B+ 树是"读多写少 + 有序数据"场景的默认答案：MySQL 的 InnoDB 里整张表就是一棵主键 B+ 树（聚簇索引），叶子直接携带整行数据，二级索引的叶子存主键值、必要时回表；PostgreSQL 的默认索引类型也属 B 树家族，叶子存指向堆表中行位置的指针。事务型数据库的主键与唯一约束，几乎都由它兜底。
3、LSM 树：写优化的极致
B+ 树为了读快，接受了一个昂贵的代价：写入是随机的。更新页中间的某一行，可能触发页分裂与随机小 IO，写越猛代价越高。LSM（Log-Structured Merge Tree，日志结构合并树）把优化方向整个反过来：为写而生，读时多干活。以 RocksDB 一类引擎为原型，写入路径如下：
解读这条链路：写入先追加一条 WAL（Write-Ahead Log，预写日志）日志保证崩溃可恢复，随后修改内存中的 memtable（通常为跳表）。到这一步写入就已经"完成"，落盘被整体推迟。memtable 写满后转为只读，后台线程把它刷成不可变的 SSTable 文件进入 L0；同层文件攒到阈值，compaction 再把多层文件归并排序成更大的下层文件。整条链路没有任何"原地更新"，磁盘写入全部是顺序大块追加——这是 SSD 与机械盘都最讨喜的写入形态，LSM 的写入吞吐因此能比 B+ 树高出一个量级。
好写的另一面是读麻烦：同一个键的最新值可能在 memtable，也可能埋在任意一层的某个 SSTable 里。点查需要"先查内存、再逐层查盘"，靠布隆过滤器把大多数无关文件提前排除。工程上把 LSM 的代价总结为三个放大：写放大（同一条数据被 compaction 反复重写）、读放大（一次点查裂变成多次查找）、空间放大（旧版本在合并前一直占盘）。compaction 策略的取舍，本质上就是在三个放大之间腾挪。
这套结构统治了写多读少的世界：LevelDB 与 RocksDB 是最著名的开源实现，HBase、Cassandra 与 TiDB 的存储层 TiKV（直接构建于 RocksDB 之上）同属此阵营；Lucene 的"不可变段 + 后台合并"也借鉴了同一思想，所以 Elasticsearch 的写入路径带有 LSM 的影子。
4、倒排索引：为搜索而生
前两种结构回答的都是键与数值的查找，全文检索的问题形状不同：给定一个词，找出包含它的所有文档。按"文档 → 词"存内容叫正排；倒排索引把它翻转成词 → 文档列表。三篇文档建好倒排后大致如下：
| 词项 | 倒排列表 |
|---|---|
| 数据库 | 文档 1、文档 3 |
| 索引 | 文档 1、文档 2 |
| 向量 | 文档 2、文档 3 |
查询"数据库 AND 索引"，就是取两个倒排列表求交集，得到文档 1。倒排列表按文档号有序存放，交集可以用"拉链式"归并线性完成，再配上跳表与位图压缩还能更快。多词查询、短语匹配、按词频打分，都建立在这套集合运算之上。
中文还有一道前置工序：没有天然空格，"索引原理"必须先由分词器切成"索引"与"原理"两个词项才能进入倒排，分词质量直接决定检索效果。这条路线的代表是 Lucene 与其之上的 Elasticsearch、SQLite 的 FTS5 扩展，以及 PostgreSQL 的 GIN 索引——它的内核正是倒排。
5、HNSW：AI 时代的近邻图
语义检索带来了第四种问题。嵌入模型把文本或图片编码成高维向量（例如 1536 维浮点数组），"相似"被定义为距离小，检索目标变成"找出距离最近的 k 个向量"。B+ 树在此完全失效：它依赖大于小于构成的全序关系，而高维空间里不存在这种序——说不出向量 A 整体"大于"向量 B。按维度切分的 KD 树在低维好用，到上百维会退化到接近全量扫描，这就是维度灾难。
朴素解法是暴力扫描：与全部 N 条向量逐一算距离。百万级尚可接受，亿级完全不现实。HNSW（Hierarchical Navigable Small World，分层可导航小世界图）的思路是：把每个向量当作图上的一个点，与其最近的 M 个邻居连边；查询时从入口出发，每一步跳到邻居中离目标最近的那个，直到周围没有更近的点。单层近邻图容易被"卡"在局部最优点，跳不到远处；HNSW 的解法是给图分层，直觉与跳表同构：
图中同一编号的点在多层出现（虚线连接），顶层稀疏、边长，底层稠密、边短。查询从顶层入口贪心跳跃，长边负责快速跨越整个空间，像高速公路；逼近到没有更近的邻居就下降一层，边越来越短，走位越来越精；在最底层做带候选队列的搜索返回 top-k。期望跳数与跳表一样是对数级，这正是原始论文的核心结论。
为什么允许"近似"？因为精确近邻在高维绕不开与全量算距离的 O(N)。HNSW 用召回率换速度：搜索参数（如 ef_search）调大，结果更接近精确解但更慢；调小则更快更糙。生产中召回率 95% 以上、亿级向量毫秒级返回是常态，而语义检索里第 5 名与第 6 名的差别通常无关紧要——用可控的近似换取数量级的速度，是一笔划算的交易。
注意：召回率不是常量。数据分布变了、距离度量换了、数据量涨了，最优参数都会漂移；上线前务必用真实查询集压测，并定期回归。
代价方面：建图慢（插入需要多次近邻搜索）、内存占用大（向量与邻接表都要驻留内存）、删除与更新相对别扭。即便如此，HNSW 仍是当今向量检索的事实标准，pgvector、Qdrant、Milvus、Weaviate、Faiss 与 Elasticsearch 的向量类型都内置了它。
6、四种结构总对照
把四种结构的数据形态与读写特征放到一张表里对比如下：
| 结构 | 数据形态 | 读特征 | 写特征 | 代表引擎 |
|---|---|---|---|---|
| B+ 树 | 有序键值 | 等值与范围查询快 | 就地更新与页分裂 | MySQL 与 PostgreSQL |
| LSM 树 | 有序键值 | 点查需逐层合并 | 顺序追加吞吐极高 | RocksDB 与 HBase |
| 倒排索引 | 词到文档映射 | 多词交并集高效 | 段不可变需合并 | Lucene 与 FTS5 |
| HNSW 图 | 高维向量 | 近似近邻毫秒级 | 建图慢且耗内存 | pgvector 与 Milvus |
没有全能冠军，每一行都是"为某一类查询牺牲其余"的权衡。养成一个习惯：看到新数据库先问它用什么结构做主索引，就能大致推断出它的读写性格。
7、一个库多种索引并存
真实系统从不做单选题，而是让多种索引各管一摊。PostgreSQL 是最典型的样本：默认 B-tree 管等值与范围查询；GIN（Generalized Inverted Index，广义倒排索引）管 jsonb、数组与全文检索；装上 pgvector 扩展后 HNSW 管向量近邻；追加型时序数据还能用 BRIN 只存块范围摘要。同一张表挂多种索引很常见，示例如下：
CREATE INDEX idx_time ON docs USING btree (created_at); -- 时间范围
CREATE INDEX idx_fts ON docs USING gin (to_tsvector('simple', body)); -- 关键词搜索
CREATE INDEX idx_vec ON docs USING hnsw (embedding vector_cosine_ops); -- 语义近邻
三条语句在同一张 docs 表上各建一种索引：按时间过滤走 B-tree，关键词检索走 GIN 倒排，语义相似走 HNSW 图；优化器按查询形状挑路，互不干扰，代价则是写入时三者各自维护。看懂这一层，"选数据库"常常就退化为"这套查询组合需要哪几种索引、谁家的实现更成熟"。更多索引类型可翻阅 PostgreSQL 官方文档。
8、总结
索引是一笔"用空间与写入换读取"的生意，四种结构各押一头：B+ 树用矮胖多叉树把有序查找压到 3～4 次页访问，统治事务型数据库；LSM 树把随机写变成顺序追加，用三个放大换吞吐，统治写多读少场景；倒排索引把"文档找词"翻转成"词找文档"，统治全文检索；HNSW 用分层近邻图在无序的高维空间以对数步数逼近近邻，成为向量检索标配。
对于日常实践，建议：遇到慢查询先用执行计划确认走没走索引、走的是哪一种；写密集场景优先考察 LSM 系引擎；上语义检索前先定召回率与延迟预算，再用真实数据调 HNSW 参数。最后留三个练习：
- 在 MySQL 或 PostgreSQL 造一张 100 万行的表，用 EXPLAIN 对比有无索引的耗时
- 用 RocksDB 写入百万键值，观察 SSTable 层数与磁盘占用的变化
- 在 pgvector 灌入 10 万条随机向量，调整
ef_search与 M，绘制召回率与延迟曲线
把四种结构画在同一张草图上考考自己：谁是树、谁是图、谁靠链表串联——答得出，这篇就没有白读。
