索引是对数据库性能影响最大的那一个杠杆,"这条查询为什么慢?"几乎总能归到索引上。思路很简单——维护一个辅助结构,让你不用扫全表就能找到行——但工程上很有深度:两种主流结构(B-Tree 和 LSM-Tree)在读写速度上做出相反的取舍;而你如何组织索引(聚簇、二级、复合、覆盖)决定了一条查询是飞起来还是爬。这是我们 DDIA 存储与检索笔记 的实战配套篇。

⚡ 速览要点
  • 索引用写速度和空间换读速度——它把 O(n) 的全表扫描变成 O(log n) 的查找,但每次写都得同时更新索引。
  • B-Tree 读优化、有序、平衡、原地更新——关系型数据库的默认(PostgreSQL、MySQL/InnoDB)。
  • LSM-Tree 写优化——写先缓冲在内存,刷成不可变的有序文件,后台做 compaction(Cassandra、RocksDB)。
  • 聚簇索引 vs 二级索引——聚簇索引就是按主键排序的表本身;二级索引是另一个指回行的结构。
  • 复合索引遵循最左前缀规则——(a, b, c) 上的索引能帮到查 a、a+b、a+b+c——但帮不到只查 b。
  • 覆盖索引能只靠索引就回答查询,完全跳过回表。
  • 别建过多索引——每个索引都拖慢写、占空间;没用的索引是纯开销。
tldr

索引靠避免全表扫描让读变快,代价是写更慢、占更多存储。B-Tree(有序、原地、读优化)支撑大多数关系型数据库;LSM-Tree(内存缓冲 + 不可变 SSTable + compaction,写优化)支撑很多 NoSQL 存储。除了结构,设计也很关键:聚簇 vs 二级、复合索引(最左前缀规则)、覆盖索引(只靠索引回答)。索引那些你查询会过滤/排序的列——别多建。

为什么要建索引

没有索引时,找匹配 WHERE email = 'x' 的行意味着全表扫描——读每一行,O(n)。一千行没事;一亿行就是灾难。索引是一个有序(或以其他方式组织)的辅助结构,让数据库能在 O(log n) 内跳到匹配的行。代价是实打实的,要说清楚:索引消耗存储,而且每次 INSERT/UPDATE/DELETE 都必须更新表上的每一个索引。所以建索引是一个有意的取舍——用更慢的写和更多空间,换更快的读。

B-Tree 索引

B-Tree(具体是 B+tree)是关系型数据库的主力。它是一棵由定长页(page)(通常 4–16 KB)组成的平衡树,键有序存放;内部页把你路由到持有实际键/指针的叶子页。因为平衡,查找、插入、范围扫描都是 O(log n),而有序的叶子让范围查询和有序读取很高效。

B+tree:平衡、有序、范围友好 
                 [ 30 | 70 ]            ◀ 根(路由键)
                /     |      \
        [10|20]   [40|50|60]   [80|90]   ◀ 内部
        /  |  \    ...           ...
   叶子:有序的键 → 行指针,串成链表支持范围扫描

  查 50:根(→中) → 内部(→50) → 叶子   = O(log n),只读几页

B-Tree 原地更新:改一个值会重写持有它的那一页。这让读快且可预测,但写会带来随机 I/O(找到并修改正确的页),并需要预写日志(WAL)保证崩溃安全。B-Tree 是 PostgreSQL、MySQL/InnoDB、SQL Server、Oracle 的默认。

LSM-Tree 索引

Log-Structured Merge-tree 为写优化。它不原地改页,而是把写缓冲在一个内存有序结构(memtable)里;memtable 满了就刷到磁盘成为一个不可变的有序文件(SSTable)。因此写是快速的顺序追加——没有随机 I/O。久而久之 SSTable 越积越多,所以后台进程做 compaction——合并有序文件并丢弃被覆盖/删除的键。

LSM-Tree:缓冲 → 刷盘 → compaction 
写 → memtable(内存,有序)
            │ 满? 刷盘(顺序写)
            ▼
       SSTable_1  SSTable_2  SSTable_3 ...   (不可变,有序)
            └──────── compaction ────────┘ → 合并后的 SSTable
                                            (丢弃被覆盖/删除的键)

  读:先查 memtable,再从最新到最旧查 SSTable
      (Bloom filter 跳过不可能含该键的 SSTable)

缺点:一次读可能要查 memtable 和好几个 SSTable,所以 LSM 的读可能更慢(用 Bloom filter 快速排除不含某键的 SSTable 来缓解——和我们 短链 里用的是同一招)。LSM-Tree 支撑 Cassandra、RocksDB、LevelDB,以及很多 NoSQL 系统背后的存储引擎。

B-Tree 对比 LSM-Tree

方面B-TreeLSM-Tree
优化方向读写
写原地(随机 I/O)追加 + 刷盘(顺序)
读快、可预测可能要查多个 SSTable
放大写放大(重写页)读放大 & compaction 放大
用于PostgreSQL、MySQL、OracleCassandra、RocksDB、LevelDB

聚簇索引 vs 二级索引

聚簇索引(clustered index)决定表中行在磁盘上的物理顺序——表就是那个索引,按聚簇键(通常是主键)排序。每表只有一个,按该键查找会立刻返回整行。二级(非聚簇)索引是一个独立结构,其叶子指回行(按主键或行位置);用它需要再跳一次去取整行。含义:按聚簇键查找是最便宜的读,而二级索引查找要多一步。

复合索引与最左前缀规则

索引可以跨多列——一个在 (country, city, name) 上的复合索引。关键在于它是按这些列依次排序的,所以它只帮得到用了这些列最左前缀的查询:

最左前缀规则 — 索引 (country, city, name) 
WHERE country=?                         ✓ 用上索引
WHERE country=? AND city=?              ✓ 用上索引
WHERE country=? AND city=? AND name=?   ✓ 完整用上索引
WHERE city=?                            ✗ 跳过了最左列 → 用不上
WHERE name=?                            ✗ 用不上

  列的顺序很重要:把最常过滤/最有区分度的列放前面,
  并与你的查询模式对齐。

这是现实中最常见的索引错误之一:复合索引列序搞反,或查询过滤的是非前导列,于是悄悄退化成扫描。

覆盖索引

如果一个索引包含了查询所需的所有列(过滤列和被选列都在内),数据库就能只靠索引回答查询——不用回表。这就是覆盖索引(covering index),对热点查询是大赢:SELECT name WHERE country=? 由 (country, name) 上的索引服务,根本不碰表行。代价是索引更宽(更多存储、更慢的写),所以把覆盖索引留给你流量最高的查询。

什么时候不该建索引

索引不是免费的,过度建索引是真实的反模式:

看执行计划

判断索引是否被用上,靠查询计划器:跑 EXPLAIN(或 EXPLAIN ANALYZE),看是 index scan 还是 顺序/全表扫描。大表上意外的全表扫描就是"缺索引或索引用不上"的经典信号——常因复合索引非最左列、在列上套了函数,或类型不匹配导致索引失效。

总结

索引是一笔取舍:读拿到 O(log n),代价是写速度和空间。了解你的存储引擎(B-Tree = 读优化、原地;LSM = 写优化、追加+compaction),并围绕你真实的查询模式设计索引——聚簇键给最便宜的读、复合索引守最左前缀规则、覆盖索引给热点路径——同时克制住"什么都建索引"的冲动。

🎯 面试速答

索引的代价是什么?存储加写变慢——每次写都更新每个索引。它换来 O(log n) 读而非 O(n) 扫描。
B-Tree 对比 LSM-Tree?B-Tree = 有序、原地、读优化(关系库);LSM = memtable + 不可变 SSTable + compaction,写优化(Cassandra、RocksDB)。
聚簇 vs 二级索引?聚簇定义表的物理顺序(表即索引);二级是独立结构、指回行(多一跳)。
最左前缀规则?(a,b,c) 上的复合索引服务查 a、a+b、a+b+c——不服务单查 b 或 c。列序必须匹配查询模式。
覆盖索引是什么?包含查询所需全部列的索引,只靠索引就能回答、不用读表。

← 上一篇
Elasticsearch