07 索引与查找：B 树、哈希、倒排、LSM

开篇提问

先做一个思想实验：

给你一本 1000 页、没有任何目录和索引的书，让你找”第 37 章”在哪一页。你怎么找？

最笨的办法：从第 1 页翻到第 1000 页。这就是全表扫描，O(n)。

聪明一点：书前面有目录 → 直接查到页码 → 翻过去。这就是索引，O(log n) 甚至 O(1)。

现在请回答更深的一层：

索引为什么能加速？它”省”掉的到底是什么？而且——既然索引这么好，为什么不给数据库里每个字段都建上索引？

第二问的答案是理解索引的关键。因为索引不是免费的：它用”写放大”和”空间”换来了”读加速”。不理解这个代价，你就会建出一堆拖垮写入性能的索引，还不知道为什么。

子主题一：索引的本质——用有序性消灭搜索空间

所有索引的核心原理，其实就一句话：

索引通过”维护一个有序的、可快速导航的结构”，让你不必遍历全部数据就能定位目标。

为什么”有序”这么关键？因为有序性让你可以”排除”而不是”遍历”：

无序数组里找 X：只能一个个比 → O(n)
有序数组里找 X：二分查找，每次排除一半 → O(log n)
100 万条数据：O(n) 要 100 万次比较，O(log n) 只要 20 次

从 100 万次到 20 次，这就是索引的力量来源——不是”算得更快”，是”根本不用算”。

所以索引的核心价值是：把”必须检查所有候选”变成”可以排除大部分候选”。 而”排除”的能力，来自于数据被组织成了某种结构（有序、分桶、哈希映射）。

这一条能帮你理解所有索引的差异：不同的索引结构，本质上是”用不同的方式组织数据，从而实现不同方式的排除”。

B 树：按 key 排序 → 可以排除”不在范围内的”
哈希：按哈希值分桶 → 可以精确定位”确定相等的”
倒排：按内容词项组织 → 可以排除”不含这个词”的文档
位图：按位组织 → 可以用位运算快速求交并

子主题二：B 树与 B+ 树——为磁盘而生的索引

哈希索引（O(1) 等值查询）看起来最快，但数据库里最常见的默认索引却是 B+ 树。为什么？

因为数据库的数据在磁盘上，而磁盘的访问模式和内存完全不同：磁盘按”块/页”（通常 4KB~16KB）读写，一次随机 IO 的代价（约 10ms 机械盘）比一次内存访问（约 100ns）慢 10 万倍。

B+ 树就是为这个场景量身定做的：

它是一个”矮胖”的多路搜索树——每个节点能存成百上千个 key，所以树高通常只有 3~4 层。
每个节点大小 = 一个磁盘页（比如 16KB），一次 IO 就能读入整个节点。
3~~4 层意味着：查找任意一条数据，只需要 3~~4 次磁盘 IO。

这就是 B+ 树的核心设计：用”高扇出、低树高”把磁盘 IO 次数压到最小。

为什么不用二叉树？因为二叉树是”高瘦”的——100 万条数据要 20 层，就是 20 次磁盘 IO，慢 5~7 倍。在磁盘场景下，“树高”就是”IO 次数”，所以让树矮比让每层比较快更重要。（这和你在上一本书里看到的”四叉堆比二叉堆缓存友好”是同一个思想：在慢介质上，减少访问次数比减少单次访问成本更重要。）

B+ 树比 B 树强在哪？ 关键差异：B+ 树的所有数据都在叶子节点，非叶子节点只存 key（索引）。两个好处：

非叶子节点能存更多 key → 扇出更高 → 树更矮
叶子节点用链表串起来 → 范围扫描极其高效（找到起点后顺序遍历即可）

这就是为什么 B+ 树同时擅长”点查”和”范围查”，成为关系型数据库的默认选择。

子主题三：哈希索引与 LSM 树——两个极端

哈希索引：O(1) 等值查询之王

结构：哈希表，key → 位置
优势：等值查询 O(1)，比 B+ 树还快
致命弱点：不支持范围查询（哈希把顺序打乱了，你没法查”id 在 100 到 200 之间的”）
适用：K-V 存储（Redis、Memcached）、等值查询为主的表

LSM 树（Log-Structured Merge Tree）：为写优化的结构

这是索引领域一次重要的思路反转。B+ 树的写入有个大问题：每次写入都要在树里找到位置、可能触发节点分裂、产生随机磁盘 IO。写入放大严重。

LSM 树的思路是”反过来想”：

既然随机写慢，那就把随机写变成顺序写。

具体做法：

写入先追加到一个内存结构（MemTable）+ 顺序写 WAL（保证持久性）→ 极快
MemTable 满了，顺序刷到磁盘成为一个不可变的 SSTable 文件
后台定期把多个 SSTable 合并（Compaction），去掉重复和已删除的
查询时：先查 MemTable，再依次查各层 SSTable（用 Bloom Filter 加速”不存在”的判断）

LSM 把”随机写”换成了”顺序写 + 后台合并”。 这是经典的”把成本转移”：把写路径的成本，转移到了后台的 compaction 和读路径（要查多个文件）。

代价是什么？

读放大：一次查询可能要查多个 SSTable
写放大：compaction 会反复重写数据
空间放大：合并期间新旧版本并存

所以 LSM 适合写多读少的场景（时序数据、日志、metrics），B+ 树适合读写均衡或读多写少的场景（OLTP 业务表）。没有哪个”更好”，只有哪个更适配你的读写比例。

子主题四：倒排索引与比特图——搜索领域的专用武器

倒排索引（Inverted Index）：搜索引擎的心脏

正排索引是”文档 ID → 文档内容”，倒排索引反过来：“词 → 包含这个词的所有文档 ID 列表”。

为什么这么设计？因为搜索的需求是”找出包含这些词的文档”，而不是”找出这个文档包含哪些词”。索引的结构要匹配查询的模式——这是索引设计的第一原则。

倒排索引让”包含 A 且包含 B”的查询，变成”两个文档 ID 列表求交集”——非常高效。Elasticsearch、Lucene 都是基于它。

位图索引（Bitmap Index）：低基数场景的利器

对”性别”、“状态”、“地区”这类取值很少的字段，位图索引极其高效：

每个取值对应一个位图（每个文档占 1 位）
“性别=女且地区=北京” = 两个位图做 AND 运算
位运算是 CPU 最擅长的，能极快处理亿级数据

位图用”每个值一个位图”的空间，换来了”任意组合条件查询都很快”的能力。它在 OLAP 和分析型场景（比如用户画像、广告人群圈选）里是无可替代的。

子主题五：索引的代价与选择

现在回答开篇的问题：为什么不给所有字段都建索引？

索引的代价有三层：

代价一：写放大（最主要的代价）。 每次 INSERT/UPDATE/DELETE，都要同步更新所有相关索引。索引越多，写越慢。 一个表有 10 个索引，一次插入就要做 11 次写入（1 次数据 + 10 次索引）。

代价二：空间。 索引本身要占存储，有时甚至超过数据本身。

代价三：优化器的负担。 索引太多，查询优化器要评估更多方案，可能选错执行计划，反而变慢。

所以建索引的判断标准，核心是**“选择性（selectivity）”**：

选择性 = 不同值的数量 / 总行数。选择性越高的字段，建索引越有价值。

主键、唯一 ID：选择性 = 1（每个值都不同）→ 索引价值最大
性别（只有 2 个值）：选择性极低 → 普通 B 树索引几乎无用**（但位图索引有用）**
状态字段（几个固定值）：看分布，如果某个值占 90%，查这个值用索引反而更慢（不如全表扫）

还有几个实用的索引原则：

复合索引的列顺序很重要（遵循”最左前缀”原则）
覆盖索引（索引包含查询需要的所有列）能避免回表，性能提升显著
定期清理无用索引（很多系统里 30% 以上的索引从未被使用过）

子主题六：B+ 树的分裂与合并——填充因子为什么是命门

到目前为止我们一直把 B+ 树当成一幅静态的画。现在往里面插数据，画就开始动了。先问你一个问题：

你往一张有 1 亿行的表里 INSERT 一行 200 字节的数据，磁盘上到底发生了什么？

乐观答案是”写了一个数据页 + 一个索引页”。悲观答案是”触发了一次页分裂，连锁反应一路向上，最后树高 +1，写了五六个页、若干条 redo、还可能搬走了半页数据”。

B+ 树的写入代价不是常数，它是有”尾巴”的——绝大多数写入很便宜，但偶尔有一次极贵。

分裂（Split）：叶子页满了还要插 → 申请一个新页，把原页大约一半的 key 搬过去，然后把中间那个 key 提到父节点里当”分界线”。注意一个细节：叶子分裂时中间 key 是”复制”上去的（因为叶子必须持有全部 key），内部节点分裂时中间 key 是”上移”的（它从孩子身上删掉，只留在父节点）。父节点因此多了一个孩子，父节点也可能满 → 递归向上分裂 → 如果根也满了，根分裂，树高 +1。

生活化地讲：书架塞满了，你得再买一个，把一半书搬过去，还得在目录上添一行”M 以后的书在第二个架子上”。如果目录那页也写满了呢？再拆一层目录。树高 +1 意味着从此以后每一次查询都多一次 IO——一次分裂，永久加税。

合并（Merge）：删除让页的占用率掉到阈值以下，先尝试向左右兄弟”借”（rotation，旋转：把兄弟的一个 key 挪过来，只改父节点的分界 key，代价小，不产生新页，也不减少父节点的孩子数）；借不到才合并——两页并一页，父节点少一个孩子，父节点可能又要合并，级联向上；如果根只剩一个孩子，根被丢弃，树高 -1。

这个”阈值”就是填充因子（fill factor）故事的另一半。 填充因子说的是：建索引或分裂时，页里保留多少空闲空间。

填满（接近 100%）：空间利用率高，但新页一落地就满了，下一条插入立刻又要分裂。
留 30% 空隙：新页有缓冲，能吸收后续一批插入，分裂频率大幅下降，但每个页平均只装 70%。

为什么这个旋钮这么重要？因为分裂频率直接影响三件事：IO 次数（分裂要写新页、重写旧页、改父节点、可能一路改到根）、空间利用率（分裂后两页各半满，随机插入场景下长期平均填充率会掉到 50%~70%）、以及物理碎片——分裂出来的新页在磁盘上往往和原页不相邻，于是 key 相邻的数据在物理上散开了。范围扫描从”顺序 IO”退化成”随机 IO”，这才是碎片真正的杀伤力，不是”浪费了点空间”。

所以：

随机 key 插入最惨：每个 key 随机落在某个页上，所有页都接近满 → 几乎每次插入都有机会分裂 → 空间利用率低、碎片严重。这也是为什么”用 UUID 当主键”在生产上是个著名事故源。
顺序 key 插入最省：永远在最右页追加，满了才分裂一次，且很多实现对”最右页插入”有专门优化（新页继续接收追加，老页保持满）。页的物理顺序 ≈ key 顺序，聚簇度极高，范围扫描全是顺序 IO。

但反过来问一句：顺序插入就完美吗？ 不。所有并发写入都抢同一个最右页，那页的 latch 就成了全局瓶颈——这就是 B+ 树的尾部争用。放到分布式系统里更致命：单调递增的 key 让所有写入落到同一个分片，其他分片闲着（HBase 里著名的 rowkey 热点问题），解法只能是加盐 / 哈希前缀打散。你看，又是一次熟悉的取舍：顺序换 IO，打散换并发，两者不可兼得。

最后一个常见困惑：删了一半数据，表文件大小为什么没变？ 因为删除只是把记录标记为可复用（以及后台 purge 掉被删版本），页里的空间空了但不会还给操作系统，页也不会因为”半空”就自动合并（要跌破合并阈值才动）。想真正收缩，得重建表/索引（OPTIMIZE TABLE 一类操作）。

收束一句：B+ 树的性能问题，八成出在两个词上——“填充因子”和”聚簇度”。前者是”空间利用率 vs 分裂频率”的旋钮，后者是”逻辑顺序 vs 物理顺序”的一致性。后面你会反复看见它们。

子主题七：聚簇索引 vs 非聚簇索引——回表的代价究竟是什么

前面所有讨论都默认了一件事：索引里存的是”位置”，数据存在别处。但 InnoDB 不这么干。

InnoDB 的表本身就是一棵 B+ 树。 主键那棵 B+ 树的叶子节点上挂的不是指针，是完整的行数据。这叫索引组织表（IOT）/ 聚簇索引（clustered index）。而其他索引（二级索引 / 辅助索引）的叶子节点存的不是行的物理地址，而是这一行的主键值。

于是就出现了索引领域最常被提到、最少被算清的一个动作：回表。

SELECT * FROM user WHERE phone = '138...';
-- 索引 idx_phone(phone)

        二级索引树                          聚簇索引树
   phone → 主键 id   ───────────►   id → 完整行数据
        (第 1 趟)                        (第 2 趟 = 回表)

先反问一句：为什么二级索引不直接存”行的物理地址”？那样不是只走一趟吗？

因为行会搬家。一次页分裂，半个页的行被搬到新页，物理地址全变。如果二级索引存物理地址，就得把这张表上所有二级索引里相关的条目全部更新一遍——写放大爆炸。存主键，则是一层间接：只要主键不变，行随便搬。用”多一次查找”换来了”行的物理位置可以自由移动”。 又是一次”用时间换可维护性”的经典交易。

那么回表的代价到底是什么？要算三笔账，尤其是第二笔。

第一笔，IO 账。 多走一棵 B+ 树 = 多 3~4 次页访问（若不在缓冲池里，就是随机 IO）。查 1 行：从 4 次 IO 变成 8 次，看起来只是翻倍。

第二笔，顺序账——这才是真凶。 查 1000 行呢？二级索引里 phone 相同的那 1000 行，它们的主键 id 通常是乱序的（用户注册顺序和手机号毫无关系）。于是回表时要在聚簇索引的页之间疯狂跳跃：1000 次随机 IO。而全表扫描是顺序 IO，在机械盘上顺序比随机快一到两个数量级，SSD 上差距小但依然存在。

结论可能反直觉：回表 1000 行，比直接顺序扫 100 万行还慢。

这个性质有个专门的名字：聚簇因子（clustering factor）——索引的扫描顺序与表中行的物理顺序之间的相关程度。Oracle 会明确统计它并写进执行计划的成本模型，MySQL/InnoDB 不直接暴露这个数字，但它真实存在，并且是优化器决定”要不要走索引”的核心依据之一。

第三笔，行数账。 优化器会估算”走这个索引要回表多少行”。当这个比例超过某个阈值（不同优化器不同，经验上在总行数的 10%~30% 这个量级），优化器会主动放弃索引，选择全表扫描。

注意措辞：这不是”索引失效”，这是”优化器算完账发现顺序扫更便宜”。 很多同学拿着 EXPLAIN 大喊”我建了索引为什么不用”，真实情况是优化器比他更懂这笔账。你要做的不是 FORCE INDEX 硬掰，而是先问：它凭什么算出这么多行？（答案通常是：条件选择性差、统计信息过期、或者确实就该全表扫。）

顺着这条线，把主键选型的问题一次性说透。 因为二级索引的叶子都存着主键值，所以：

主键每长一个字节，这张表上每一个二级索引都跟着胖一圈。

BIGINT（8 字节）当主键 vs CHAR(36) 的 UUID（36 字节，utf8 下可能更多）：二级索引的叶子条目体积差好几倍 → 每个页装的条目数变少 → 扇出下降 → 树变高 → 缓冲池命中率下降 → 连锁反应到每一条查询。
更糟的是 UUID 无序 → 随机插入 → 页分裂 + 碎片（接上子主题六）。两重打击。

所以”自增 BIGINT 主键”不是老派教条，是无数生产事故验证出来的默认值。非要用 UUID，至少用时间有序的 UUID（UUIDv7 / COMB），把随机写变回近似顺序写。

类比收尾：聚簇索引是”正文按页码顺序装订在书里”，二级索引是”书末的关键词表，每条只记页码”。查一个词要翻两次。但如果关键词表旁边直接把那一段原文抄上了（下一条：覆盖索引），你就只翻一次。

子主题八：覆盖索引、回表消除与索引下推

覆盖索引（covering index）：如果一条查询需要的所有列都在这个索引里，那就压根不用回表。EXPLAIN 的 Extra 里出现 Using index 就是这个信号。

为什么提升能大到离谱？因为（接上回的账）回表最贵的不是”多查一次”，而是”多查 N 次随机 IO”。

SELECT COUNT(*) FROM orders WHERE status = 1;   -- 有 idx_status(status)

这条查询只需要在 idx_status 的叶子层顺着链表扫一遍，一行都不回表，全是顺序 IO。而 SELECT * 就要为每一行都跳回聚簇索引——天壤之别。

反问：那我把查询涉及的所有列都塞进索引，不就永远不用回表了？

不行，因为这是有对价的：索引列越多越宽 → 每个页装的条目越少 → 扇出下降 → 树变高（缓存效率下降），而且每次写都要维护这个更胖的索引（写放大上升）。

覆盖索引的本质：把”回表的随机 IO”置换成”索引页的存储空间 + 写入成本”。

所以只对高频、返回行数多、且需要的列很少的查询做这件事。三条实战经验：

免费的午餐：SELECT id FROM t WHERE name = ?（id 是主键）天然覆盖。 因为二级索引的叶子里本来就存着主键值。很多人不知道这一点，还在纠结”要不要给 name 建个 (name, id) 索引”——不需要，那是纯冗余。
冗余列进索引：把 SELECT 里那两三列加到复合索引尾部，是常见且有效的手段，代价是写入变慢。
TEXT/BLOB/很长的 VARCHAR 永远别进索引，扇出会暴跌到没有意义。

索引下推（Index Condition Pushdown，ICP，MySQL 5.6 引入）——如果说覆盖索引是”消灭回表”，ICP 就是”减少回表”。

先看没有 ICP 时有多蠢：存储引擎按索引定位到一条记录后，不管 WHERE 里还剩什么条件，一律先回表取完整行，再交给 server 层去过滤。这意味着大量”注定会被过滤掉的行”白白付了一次随机 IO 的代价。

ICP 的想法很简单：如果某个条件涉及的列虽然在索引里、但因为种种原因不能用来”定位”，那就在存储引擎层、回表之前先判断它，不满足就直接跳过，不回表。

索引 idx(zipcode, lastname, firstname)
WHERE zipcode = '95054'
  AND lastname LIKE '%etrunia%'     -- 前导通配符，无法用来定位，但 lastname 在索引里
  AND address   LIKE '%Main%'       -- address 不在索引里

zipcode 用来在树里定位区间；
lastname LIKE '%etrunia%' 因为以 % 开头，没法在树里做范围定位，但这一列的值就写在索引记录里 → 引擎在索引层先判，不匹配就跳过，省掉一次回表；
address 不在索引里 → 推不下去，只能回表之后再判。

EXPLAIN 里对应的 Extra 是 Using index condition。务必把它和另外两个区分开：

Extra	含义	回表情况
`Using index`	覆盖索引	完全不回表（最好）
`Using index condition`	索引下推	回表前先过滤（次好）
`Using where`	server 层过滤	已回表后才过滤（一般）

把 ICP 抽象一层看，它其实是这条大原则的一个实例：把过滤尽可能往离数据更近的地方推。

这个思想你会在整条技术栈里反复撞见：列式存储的 predicate pushdown、Parquet 用 min-max 在 IO 之前裁剪、把过滤条件下推到存储引擎/外部数据源、Spark/Presto 的 filter pushdown 到 Parquet reader……凡是”能早过滤就别晚过滤”的地方，都有它的影子。 记住这个模式，你会认出很多看起来毫不相干的技术其实是同一招。

收束：覆盖索引消灭回表，索引下推减少回表。两者对付的是同一个真凶——随机 IO。

子主题九：复合索引的列顺序——最左前缀到底在说什么

复合索引 (a, b, c) 在 B+ 树里就是按 (a, b, c) 的字典序排出来的一棵树。跟电话簿按”姓 → 名 → 中间名”排是一回事。

先问：为什么 WHERE b = 2 用不上这个索引？

因为在整棵树里，b = 2 的记录散落在所有 a 的取值下面，它们不连续。而索引能加速的前提恰恰是：

判据：一个条件能不能用上索引 = 满足它的记录在索引里是不是”连续的一段”（或者少数几段）。

逐条验一遍：

a = 1 AND b = 2：a = 1 锁定一段，这一段里 b 是有序的 → b = 2 是其中连续的一小段 → 用得上。
a = 1 AND c = 3：a = 1 锁定一段，段内是按 b 排序而不是 c → c = 3 的记录散落在这段里 → c 只能当”扫描时过滤”，不能当”定位时缩小范围”。
a = 1 AND b > 5 AND c = 3：a、b 定位，c 靠边站。
a > 1 AND b = 5：只有 a 能定位——因为 a > 1 之后，全局看 b 已经不再有序了。

于是最左前缀原则的真身浮出水面：

从最左列开始，连续等值匹配的列共同确定一段连续区间；一旦遇到范围查询 / 不等值 / 被函数包裹 / 干脆中断，那么它右边的所有列都只能当过滤器，不能当定位器。

（顺带一提，那些”只能当过滤器”的列，正是上一条 ICP 的用武之地——两条知识在这里接上了。）

那列到底怎么排？三条规则，按优先级往下走：

规则一：等值列在前，范围列在后。 因为范围列后面的列全废，把它放最后，损失最小。

规则二：能让区间缩得最快的等值列更靠前——通常等价于区分度（选择性）高的列靠前。但有一个重要例外：

如果某列几乎每个查询都带（比如 tenant_id、shop_id），它必须放第一位，哪怕它区分度不高。 因为它决定了”这个索引能不能被大多数查询命中”。

查询模式的稳定性，权重高于单列的区分度。 这是新手最常搞反的地方。

规则三：ORDER BY / GROUP BY 的列，按排序顺序紧跟在等值列后面。 因为索引本身有序 → 顺序读出来的就是有序结果 → 省掉 filesort 和临时表。

索引 (tenant_id, create_time)
WHERE tenant_id = 42 ORDER BY create_time DESC LIMIT 20;
-- 引擎在 tenant_id=42 这一段里倒着扫 20 条就停，O(20) 而不是 O(全部 + 排序)

方向问题：MySQL 8.0 之前不支持降序索引，ORDER BY a ASC, b DESC 这种混合方向用不上索引的有序性；8.0 起支持 DESC 索引项，混合方向才有解。

再反问一层：那我 (a, b) 和 (b, a) 各建一个，不就都覆盖了？

可以，代价是你付了双份写放大（回看子主题五）。而且——

索引设计本质是”用最少的索引覆盖最多的查询模式”，这是一个（近似）集合覆盖问题，不是”每个查询配一个索引”。

正确做法：把你所有高频查询列出来，找它们的公共前缀，然后合并。顺便清理冗余索引：有了 (a, b, c) 之后，(a) 和 (a, b) 都是冗余的（左前缀已被覆盖），但 (b) 不冗余。现实中的库里堆着大量这种冗余索引，纯粹是在给每一次写入交税。

子主题十：LSM 深入——MemTable、SSTable、Compaction 与 Bloom Filter

子主题三给了 LSM 一张速写：把随机写变成顺序写 + 后台合并。现在把这张速写放大成工程图纸。先抛一个问题：

LSM 里最难查的是什么？不是”存在的 key”，而是”不存在的 key”。 记住这个问题，它直接引出 Bloom Filter 的必要性。

写路径：四步，全部顺序

WAL 顺序追加（保证持久性，因为后面那步在内存里）；
写 MemTable（内存中的有序结构）；
MemTable 达到阈值 → 变成 immutable MemTable，后台线程把它顺序刷成磁盘上的 L0 层 SSTable；
开一个新的 MemTable 继续接客。

为什么 MemTable 通常用跳表（skiplist）而不是红黑树？（LevelDB / RocksDB 的选择）

跳表的有序遍历就是链表顺序扫，Seek + Next 天然高效；红黑树做范围扫描要中序遍历，还得维护栈。
跳表插入只改局部若干层指针，锁粒度小，并发控制简单；红黑树要旋转，可能动到根。
实现短、好调。（代价：指针多、缓存局部性差、空间开销略大——但都在内存里，相比磁盘 IO 全是零头。）

反问：MemTable 已经是有序的了，为什么还要多写一份 WAL？

因为内存掉电即失，而 MemTable 的”有序”只是内存里的指针结构，无法从磁盘重建。WAL 就是”顺序写一份流水”来买持久性。注意，LSM 把磁盘上的写全部收敛成了顺序写：WAL 是 append，刷 SSTable 也是 append（顺序生成一个新文件）。这是它最漂亮的地方。

SSTable 的结构：一个”两层索引”的套娃

SSTable（Sorted String Table）= 内部按 key 有序的不可变文件。典型布局：

┌───────────────────────────────────────────┐
│ Data Block 1 │ Data Block 2 │ ... │ Data N │  ← 真正的数据，块内按 key 有序
├───────────────────────────────────────────┤
│ Filter / Meta Blocks（Bloom Filter 数据）  │
├───────────────────────────────────────────┤
│ Meta Index Block                          │
├───────────────────────────────────────────┤
│ Index Block：每个 data block 的最大 key    │  ← 常驻内存，是 data block 的"稀疏索引"
│              + 文件内偏移                  │
├───────────────────────────────────────────┤
│ Footer（固定长度：index/metaindex 位置 + 魔数）│  ← 索引的索引
└───────────────────────────────────────────┘

几个关键点：

Data Block 内用前缀压缩 + 重启点（restart point）：key 是有序的，相邻 key 往往共享很长的前缀，所以只存”共享前缀长度 + 后缀”。但这样第 k 条 key 就没法直接定位，于是每隔若干条 key 存一个完整 key 作为重启点，查的时候从最近的重启点往后扫几条。典型的空间换时间。
Index Block 常驻内存：定位一个 key 时，先在内存里二分 Index Block，确定它落在哪个 Data Block，然后只读那一个 Block，一次 IO。
看清楚这个结构：内存里的 Index Block 是 Data Block 的稀疏索引，Footer 是 Index Block 的索引。“稀疏索引”这个思想在哪儿都长一个样——记住它，下一条子主题里它还会以另一种形态出现。

Compaction 的两条路线：这是 LSM 最核心的取舍

SSTable 不可变，所以”更新”= 写一个新版本，“删除”= 写一条墓碑（tombstone）。于是同一个 key 的多个版本散落在多个文件里，必须靠后台合并来收敛。怎么合？两大流派：

路线 A：Size-Tiered（STCS，Cassandra / HBase 的默认思路）

把大小相近的 SSTable 攒成一组，够了就合并成一个更大的。

✅ 写放大低：一份数据被重写的次数少。
❌ 读放大高：一个 key 的新旧版本可能散落在很多文件里，点查要按”从新到旧”的顺序查一堆文件。
❌ 空间放大高：合并期间新旧版本并存，需要预留大量空闲磁盘；合并瞬间峰值更凶。

路线 B：Leveled（LevelDB / RocksDB）

严格分层：除 L0 外，每层内部 key 范围互不重叠；每层总大小有上限，通常是上一层的固定倍数（LevelDB 里这个倍数是 10，可配置）。合并时从 Ln 挑一个文件，把它与 Ln+1 中 key 范围重叠的文件一起归并重写回 Ln+1。

✅ 读放大低：因为层内不重叠，每层最多只有一个文件可能包含这个 key，还能二分定位。
✅ 空间放大低：版本收敛快。
❌ 写放大高：一个 key 从 L0 一路沉到最底层，每跨一层就要被重写一次，总写放大是各层倍数量级的累加。

一句话取舍：STCS 用”空间 + 读”换”写便宜”；Leveled 用”写放大”换”读快 + 省空间”。

再反问：能两全吗？ RocksDB 的答案是”混合 + 可调”：L0→L1 用类似 tiered 的方式（攒一批再压，摊薄单次成本），上层用 leveled；另外提供 universal（近似 STCS）和 FIFO（时序场景，整个文件过期直接删，几乎零写放大）。“没有免费午餐”在这里的具体形态是：你只能挑一个放大系数来承受。

还有一个工程上常被忽略的坑：compaction 是后台的大块顺序 IO，它会和前台读写抢磁盘带宽。 线上那种”每隔一段时间延迟抖一下”的幽灵，八成是 compaction 风暴。所以生产上必须给 compaction 限流（rate limiter）、必须监控 pending compaction bytes。

Bloom Filter：专治”查一个不存在的 key”

回到开头那个问题。LSM 里最痛的查询是”查一个不存在的 key”：你必须把 MemTable、L0 的每个文件（L0 文件之间 key 范围会重叠，所以每个都得查）、L1..Ln 每层的文件全部查一遍，才能理直气壮地说”确实没有”。这是读放大的最坏情况。

Bloom Filter 就是为这件事而生的：每个 SSTable 生成时顺带生成一个 Bloom Filter（若干哈希函数把 key 映射到位数组的若干位），常驻内存。

它的性质，请背下来：

Bloom Filter 有假阳性（说”可能存在”其实并不存在），但绝无假阴性（说”不存在”就一定不存在）。

而”不存在”恰好是我们最想快速判定的那件事。于是 Get(key) 的流程变成：先挨个问 Bloom Filter，凡是回答”没有”的文件，一次磁盘 IO 都不做，直接跳过；只有回答”可能有”的（含少量假阳性）才真的去读。假阳性率由”每个 key 分到多少位”决定，可调——用一点点内存，买掉了绝大部分无用 IO。

反问：Bloom Filter 对范围查询有帮助吗？

没有。它只回答”这个 key 在不在”，是点查专用加速器。范围查询（scan）仍然必须把各层相关文件全部打开，用堆做 k-way 归并，按 key 顺序推进、按版本号取最新那个。这就是为什么 LSM 的 scan 性能常常不如它的点查那么亮眼——点查有 Bloom Filter 护体，scan 没有。

（顺带：删除只是写墓碑，真正回收空间发生在 compaction。所以”删了大量数据但磁盘没释放”在 LSM 和 B+ 树里同样成立。）

子主题十一：倒排索引深入——词项字典、posting list、压缩与跳表求交

子主题四说倒排索引是”词 → 文档 ID 列表”。真做出来，它分成两块：词项字典（term dictionary）+ 倒排列表（posting list）。

词项字典：索引的索引

它是所有出现过的词项的有序集合，负责把 term 映射到”这个 term 的 posting list 在磁盘上的什么位置”。

为什么要有序？为了支持前缀查询（comput*）和范围查询。
怎么存得下？真实系统的词典动辄上亿词项，直接存字符串会吃掉几个 GB。Lucene 用 FST（有限状态转换器）——本质是一棵带输出值的前缀压缩自动机，把公共前缀和公共后缀都合并掉，能把整部词典塞进内存，还能在 O(词长) 内完成查找和前缀遍历。
每个词项还挂着 df（document frequency，包含该词的文档数）。它既用于算 IDF（相关性打分），也用于查询规划——马上就用到。

posting list：结构由查询模式决定

包含该 term 的所有文档 ID，按 docID 升序排列。除此之外还能挂：

存的额外信息	支撑的查询
词频 tf	BM25 / TF-IDF 相关性打分
位置 positions	短语查询 `"machine learning"`（要求相邻）
偏移 offsets	结果高亮
payload	自定义权重等

结构里存什么，完全由查询模式决定。 又一次印证那条第一原则——索引的结构要匹配查询的模式。你不需要短语查询，就别存 positions，省下来的都是钱。

为什么按 docID 升序排？ 三个理由：

相邻 docID 的差值小 → 好压缩；
有序链表可以线性求交；
结果天然有序，便于去重和取 top-k。

压缩：动机是”让更多 posting 待在内存里”

原始 posting list 是 32 位整数数组。一个热门词（比如 “的”、“the”）的 posting list 可能有上千万个 docID，几十 MB，一次查询读几份这样的东西，IO 直接爆掉。必须压。

第一步：存差值（d-gap）而不是绝对值。 文档集越大、词越热，相邻 docID 越密，差值越小。

第二步：分块 + 帧内同宽（Frame of Reference）。 把 posting list 切成固定大小的块（一个常见的量级是 128 个 docID），块内用统一的 bit 宽度打包存储（宽度由块内最大值决定）。好处是位打包（bit packing）能被 SIMD 批量解码，速度极快。个别超大的差值怎么办？当”异常值”补丁存到块尾——这就是 PForDelta 一族的核心思路。

另一条路线：Elias-Fano 编码。 把单调序列拆成”高位桶 + 低位”两部分，能在压缩态下直接做随机访问和跳过——这对下面的”跳表求交”极其关键，因为你不用先解压整块才能跳过去。

压缩不只是为了省空间，更是为了”让更多 posting list 待在内存和 CPU 缓存里”。用 CPU 时间换 IO，这是所有索引压缩的统一动机。

求交加速：从 O(m+n) 到”几乎只看短的那一列”

朴素做法：两个指针从头扫，相等就输出，不等就移动小的那个。O(m+n)。

问题在哪？假设 A 有一万个 docID，B 有一千万个。A 的每个元素都得让 B 一步步挪过去——绝大部分工作是白费的。

解法一：跳表（skip list / skip pointer）。 在 posting list 上额外存一张跳跃表，每隔固定数量的文档记一个 (docID, 文件偏移)。当 A 的当前位置是 100、B 是 900000 时，别一步步挪了，用跳跃点直接跳到 ≥900000 的位置。Lucene 里是多层跳跃表（先粗跳再细跳），跟跳表本身的思想一模一样。

解法二：leapfrog（蛙跳）求交。 别做”交替推进”，而是固定一个列表当基准，让另一个列表反复跳过它——就像数据库 merge join 里的 leapfrog join。当两个列表长度差 1000 倍时，短的每一个元素都能让长的跳过一大段。

解法三（最省事也最有效）：让最短的 posting list 打先锋。

因为交集的大小上界就是最短列表的长度。用短列表驱动，长列表的跳跃次数最多、跨度最大，总代价最小。

查询 "罕见词 AND 常见词" 时，从罕见词起步能省掉 99% 的工作。这也是搜索引擎”多加几个词反而更快”的原因——每加一个词，最短列表可能又短了一截。df 存在词项字典里就是干这个用的：查询规划时先按 df 升序排，从最稀有的词开始。

解法四：连交都不做完——WAND / MaxScore。 真实搜索要的不是全部结果，是”相关性最高的 top-k”。WAND 这类算法利用”每个词项的最大可能贡献分数”，直接整体跳过那些即使命中所有剩余词也进不了 top-k 的文档段。这已经不是”索引”了，是索引结构 + 算子算法协同设计：索引提供”可跳跃”的能力，算子决定”跳得值不值”。

顺带埋个伏笔：现代引擎（Lucene 等）对 filter 类字段（doc values、数值/地理点）已经开始用 Roaring Bitmap 来存集合，把 posting 求交变成位图 AND——下一条子主题的主角。

子主题十二：位图索引深入——低基数、位运算与 Roaring Bitmap

结构一句话：为每个”取值”建一个长度 = 总行数的 bit 数组，第 i 位为 1 表示第 i 行是这个值。

行号:    0  1  2  3  4  5  6  7
city=北京: 1  0  1  0  1  0  0  1
city=上海: 0  1  0  1  0  1  1  0
gender=女: 1  1  0  0  1  0  1  0

查 "city=北京 AND gender=女" = 两个位图按位 AND = 1 0 0 0 1 0 0 0 → 第 0、4 行

为什么它特别适合低基数字段？算笔账

设总行数 N、基数 C（不同取值个数）。位图索引的总空间 = C × N bit。

性别：C=2，N=1 亿 → 2 亿 bit ≈ 25 MB。便宜得离谱。
用户 ID：C ≈ N = 1 亿 → 1 亿 × 1 亿 bit。直接世界末日。

所以位图索引的适用边界由 C × N 决定，而不是由 N 决定。 基数一高，空间按”基数 × 行数”平方级膨胀。

这就是为什么它统治的领域是：性别、省份、状态、标签、类目、设备型号——以及 OLAP、用户画像、广告人群圈选这些”枚举维度多、行数巨大”的场景。

位运算为什么这么快

一条 AND 指令处理 64 位；SIMD 一条指令能处理 128/256/512 位 → 一次指令判几百行。
多条件组合就是 AND / OR / ANDNOT 的自由组合。而且不管条件多复杂，代价都只是”按位算几遍”——不用像 B 树那样为每个条件单独遍历一棵树，更不用做结果集的归并去重。
这是位图最了不起的性质：组合查询的成本，几乎与”组合的方式”解耦。 十个条件 AND 在一起，也只是按位与十次。
计数就是 popcount（一条硬件指令）。SELECT COUNT(*) WHERE city='北京' AND gender='女' → 两次 AND + 一次 popcount，扫亿级数据可能只要毫秒级。
取行号：找第一个 1 用 ctz（count trailing zeros）；迭代用专门的迭代器（Lucene 的 DocIdSetIterator）。

稀疏怎么办？Roaring Bitmap

现实的坑：绝大多数位图是极度稀疏的。 1 亿行里只有 100 行是”北京市”，这个位图 99.9999% 是 0，存一亿个 bit 纯属浪费。

经典路线：RLE（游程编码）/ BBC / WAH / EWAH——把连续的 0 压成”多少个 0”。按 word 对齐分块，所以压缩态下依然能直接做 AND/OR，只是慢一些。

现代事实标准：Roaring Bitmap。 思路是分而治之 + 按块自动选择表示：

把 32 位整数空间按高 16 位切成 65536 个容器（container），每个容器最多表示 65536 个数；
每个容器根据自己的**基数（cardinality）**自动选结构：
- 稀疏 → ArrayContainer：一个 uint16 的有序数组（有序 → 可二分、可 galloping 求交）；
- 稠密 → BitmapContainer：8 KB 的普通位图（65536 bit），上 SIMD；
- 连续段多 → RunContainer：存 [start, length] 游程列表；
求交时可以两级剪枝：先按高 16 位跳过整个空容器，再在容器内部用最合适的算法（位图 AND / galloping search / 游程合并）求交。

那个切换阈值 4096 是怎么来的？ 因为 4096 个 uint16 = 8192 字节 = 8 KB，正好等于一个 BitmapContainer 的大小。基数 ≤ 4096 用数组更省，> 4096 用位图更省。

这个阈值不是拍脑袋定的，是两种表示的空间占用曲线的交叉点。

再往抽象一层看，“按数据分布自动切换表示”这个套路，是不是和前面见过的东西一脉相承？填充因子是按写入模式调参，PForDelta 是按块内最大值选 bit 宽度，Roaring 是按容器基数选结构。自适应，是索引工程里的常胜将军。

落地情况：Lucene/Elasticsearch、Druid、Pinot、ClickHouse、Spark，以及 Redis 的 bitmap 扩展模块，都在用 Roaring。

位图的致命弱点（必须知道）：写

改一行的某个枚举值 = 修改对应位图的一个 bit。但位图通常是压缩的，而且一个 word 被 64 行共享 → 更新要加锁、可能要解压再重压、可能要重写整块。

所以位图索引在 OLTP 高并发写入场景是灾难。 Oracle 的位图索引建在 OLTP 表上会导致严重的锁竞争，这是业界著名的生产事故来源。

它属于”一次构建、多次只读查询”的世界：数据仓库、离线画像、物化好的人群包。一旦需要高频单点更新，就别碰它。

呼应开头：B+ 树、倒排、位图，都是”用不同的方式排除”。位图的排除方式是按位并行——把 N 行的判断并行成了 N/64 条指令。当你的查询是”多条件组合 + 只要计数/集合”时，位图是降维打击。

子主题十三：列式存储的稀疏索引与 Zonemap——“用元数据避免扫描”

换个战场。子主题十二的场景里我们还在讨论”怎么精确找出符合条件的行”。现在问一个不一样的问题：

如果要扫 100 亿行、结果集本身就有几十亿行呢？

这时候”精确定位每一行”不仅没用，而且是灾难——几亿次回表、几亿次随机 IO，什么结构都扛不住。OLAP 的思路必须换：不追求精确命中每一行，而追求”整块整块地跳过”。

稀疏索引：不是每行都建索引项

稠密索引（B+ 树就是）：每个 key 都有一个索引项，能精确定位到一行。 稀疏索引：每 N 行（一个数据块 / 一个粒度）才建一个索引项，只能定位到”块”。

ClickHouse 的 MergeTree 是教科书例子：数据按 ORDER BY 键排序存放，每 granularity（默认 8192 行）生成一条索引标记（mark），记录这个粒度首行的主键值。

算一下：100 亿行的表，索引只有大约 100 万条标记——小到可以整个常驻内存。

代价呢？索引只能定位到粒度，粒度内部仍然要扫。但没关系：列式存储里，粒度内部只需要读查询涉及的那几列，而且是连续的压缩数据 + 向量化执行（SIMD 一批批处理），扫得飞快。

这就是”用精度换体量”：稀疏索引把索引体积压缩了约 8000 倍，把”精确定位”的责任推给了”块内顺序扫描 + 列存 + SIMD”。

对比一下同样是 100 亿行：B+ 树是稠密索引，索引本身会大到必须分层存盘，每次点查 4~5 次随机 IO。OLTP 要精确取一行，所以付这个代价；OLAP 一次取几亿行，付不起。

Zonemap / min-max 索引：连索引都不用建，只写摘要

做法简单到不像技术：对每个数据块，记录块内每一列的 min 和 max（还可以加 null 计数、distinct 值集合、块级 Bloom Filter）。

查询 WHERE age > 60

块 1: age ∈ [18, 25]   → max ≤ 60，整块跳过 ✓
块 2: age ∈ [61, 99]   → 全块命中，整块读
块 3: age ∈ [30, 70]   → 区间相交，必须读
块 4: age ∈ [0, 17]    → max ≤ 60，整块跳过 ✓

Parquet / ORC 在 row group 和 page 级别都写 statistics（min/max），配合谓词下推做裁剪；ClickHouse 提供 minmax / set / bloom_filter 类型的 skipping index；Oracle/Netezza 等老牌数仓里它叫 zone map 或 small materialized aggregate (SMA)。

这是”元数据”的胜利：你根本没建索引，你只是给每个数据块写了一张”内容摘要”，然后用摘要去排除。

一个 90% 的人忽略的坑：Zonemap 的有效性取决于聚簇

如果 age 是随机分布的，几乎每个块的 min-max 都是 [0, 100]——区间覆盖全域，一个块都跳不掉。Zonemap 完全失效。

反之，如果数据按 age 排序（或至少高度相关），每个块的区间就很窄，能跳过 99% 的块。

结论：这个”索引”其实不在索引里，而在数据的物理组织里。你的 ORDER BY / 分区 / 聚簇方式，才是真正决定跳过率的东西。

这不就是子主题七的”聚簇因子”换了个马甲吗？ 是的。到这里，请把三件事串成一条线：

子主题六的碎片（分裂破坏物理顺序）
子主题七的 clustering factor（索引顺序与物理顺序的相关性 → 决定回表有多贵）
这里的 zonemap 跳过率（物理聚簇程度 → 决定块能不能被跳过）

统一的洞察：索引能否生效，从来不只取决于索引结构本身，还取决于”索引顺序”与”数据的物理顺序”之间的相关性。

把思想抽象出来：“用元数据避免扫描”的四层漏斗

层级	手段	排除粒度	单次判断成本
1	分区裁剪（按日期/租户分区）	TB 级	几乎为零（连文件都不打开）
2	稀疏索引 / Zonemap（块级 min-max、块级 Bloom）	MB~GB 级	几条指令（元数据在内存）
3	倒排 / 位图（行级精确集合）	行级	一次指令判 64 行（但空间按 C×N 增长）
4	B+ 树 / 稀疏索引定位（精确到单行）	单行	3~5 次随机 IO（最贵）
5	物化视图 / 预聚合	连扫都不扫	直接读答案

为什么要分这么多层？因为每一层的”排除成本”和”排除粒度”完全不同。 分区裁剪一次判断扔掉 TB 级数据，但只对分区键有效；位图一次指令判 64 行，便宜但空间按 C×N 涨；B+ 树精确定位到一行，但要付几次随机 IO。

索引设计的艺术，就是按你的查询模式，把这几层叠成一座”漏斗”——让数据在每一层都被廉价地削掉一大截，直到最后一层要面对的量已经小到可以随便处理。

生活化类比收尾：快递分拣中心绝不会为了找一件货把整个仓库翻一遍。它先看省（分区裁剪），再看区（zonemap），再看货架排号（稀疏索引），最后才走到那个格子（精确定位）。每一层都是一个”粗粒度的、极便宜的判断”，目的只有一个：让下一层需要看的量变小。所有索引，概莫能外。

子主题十四：实操——怎么读执行计划，怎么发现”索引没被用上”

前面十三节全是原理。这一节给一套可以直接拿去用的排查流程。

第一步：读懂 EXPLAIN（以 MySQL 为例）

EXPLAIN SELECT * FROM orders WHERE user_id = 42 AND status = 1 ORDER BY create_time DESC LIMIT 20;

重点看这几个字段：

type——访问方式，从好到坏：

system > const > eq_ref > ref > range > index > ALL
                                          ↑       ↑
                                    全索引扫描  全表扫描

看到 ALL 就是全表扫描，立刻警惕；index 比 ALL 好一点（扫的是索引，通常更小、且是顺序的），但依然是”扫全部”，看到也要掂量。

key / key_len——key 是优化器最终选中的索引。key_len 是排查复合索引问题的第一手证据：它告诉你这个复合索引实际用了几列。

比如 (a, b, c) 三列都是 BIGINT（8 字节，可为 NULL 再加 1）：

key_len = 9 → 只用了 a
key_len = 18 → 用了 a, b
key_len = 27 → 三列全用上了

rows / filtered——优化器估算的扫描行数，以及过滤后剩余的百分比。rows × filtered ≈ 预计回表多少行（回看子主题七：这个数字直接决定优化器要不要放弃索引）。

Extra——信息密度最高的一列：

Extra	含义	判断
`Using index`	覆盖索引	✅ 完全不回表，最好
`Using index condition`	索引下推	✅ 回表前先过滤，次好
`Using where`	server 层过滤	⚠️ 已经回表了才过滤
`Using filesort`	排序没用上索引顺序	❌ 慢查询常客，考虑把排序列加进复合索引
`Using temporary`	用了临时表（常见于 GROUP BY / DISTINCT）	❌ 同上

EXPLAIN ANALYZE（MySQL 8.0.18+ / PostgreSQL）会给出真实的行数与耗时。把它和 rows 放一起对比——

估算值与实际值的差距，本身就是最重要的诊断信息。 差一个数量级以上，说明统计信息失真，先 ANALYZE TABLE 再谈别的。

第二步：四类让索引失效的经典写法

① 函数 / 表达式包裹列

WHERE DATE(created_at) = '2024-01-01'     -- ❌
WHERE created_at >= '2024-01-01'
  AND created_at <  '2024-01-02'          -- ✅
WHERE amount * 2 > 100                    -- ❌
WHERE amount > 50                         -- ✅

为什么失效？因为 B+ 树里存的是 created_at 的值，不是 DATE(created_at) 的值。索引的有序性和你的判断标准不是同一个有序性，树就没法导航了。

注意一个关键的不对称：给”列”加函数会失效，给”常量”加函数不会。

WHERE created_at < NOW()          -- ✅ 函数在常量侧，没问题
WHERE created_at + 0 > 123        -- ❌ 运算在列侧，失效

实在要按表达式查，就建表达式索引 / 函数索引（MySQL 8.0 支持函数索引，PostgreSQL 支持表达式索引）——本质上是”把函数的计算结果也物化成一棵有序树”，用空间和写放大把这个有序性买回来。

② 隐式类型转换

-- phone 是 VARCHAR(20)
WHERE phone = 13800138000    -- ❌ 索引失效
WHERE phone = '13800138000'  -- ✅

为什么？MySQL 的规则是**“字符串与数字比较时，把字符串转成数字”**。于是上面那句等价于 WHERE CAST(phone AS UNSIGNED) = 13800138000——列被套了函数，跟①是同一个病根。

反向则不成立：

-- id 是 INT
WHERE id = '123'    -- ✅ 索引照常可用（转换发生在常量侧）

这个不对称，是很多人踩了坑却百思不得其解的地方。 同类问题还有：两表 JOIN 时关联列的字符集或排序规则（collation）不一致 → 也会触发转换 → 索引失效。

③ 前导模糊查询

WHERE name LIKE 'abc%'    -- ✅ 能定位到连续一段
WHERE name LIKE '%abc'    -- ❌ 全表扫
WHERE name LIKE '%abc%'   -- ❌ 全表扫

原因就着最左前缀来想：B+ 树按”从左到右”的字符序排。你知道开头，就能定位到连续的一段；你不知道开头，就无处下嘴。

真正的解法不是改 SQL，是换索引结构：用全文索引 / 倒排索引（把文本拆成词项，建 term → doc 映射）。要支持任意位置匹配，就用 n-gram 分词（MySQL 的 ngram parser、ES 的 ngram tokenizer）把字符串切成重叠的短片段再建倒排。

又一次：不是所有”查不到”都要改 SQL。有时候你真正的问题是选错了数据结构。

④ OR 条件

WHERE a = 1 OR b = 2    -- 若 b 上没有索引 → 整条 SQL 退化成全表扫

为什么？因为”满足 b = 2 的行”必须全表扫才能找齐，优化器不可能”只走一半”。

改法两种：

给 b 也建索引，让优化器用 index_merge（Extra 里出现 Using union(...) / Using intersect(...)）。但 index_merge 的实际表现常被低估，很多时候不如手写；
拆成两条用 UNION ALL，各自走各自的索引，通常最快、最可控。

注意一个例外：同一列上的 OR 不算。WHERE a = 1 OR a = 3 会被转成 a IN (1, 3)，正常走索引。

第三步：两种”看起来失效其实很理性”的情况，别误诊

情况 A：优化器主动放弃索引。 估算回表行数太多（回到子主题七那笔账：大量随机 IO 比一次顺序全表扫还贵）→ 选全表扫。这时候该做的是：让它变成覆盖索引、加 LIMIT、或者改写条件降低命中行数。在按 FORCE INDEX 之前先问一句：优化器凭什么算错了？

情况 B：统计信息失真。 数据分布严重倾斜（某个状态占了 90%）、没有直方图、表刚做完大批量导入还没 ANALYZE → 优化器估错 → 选错计划。MySQL 8 支持直方图统计（ANALYZE TABLE t UPDATE HISTOGRAM ON col WITH N BUCKETS），专门治这种倾斜。

一套可以直接背的排查套路

1. 慢查询进来 → EXPLAIN 看 type 和 key
     key = NULL / type = ALL  →  先怀疑"索引不存在或不匹配"
2. key 有值但还是慢 → 看三处
     key_len     → 复合索引用全了吗？（最左前缀）
     rows×filtered → 回表量有多大？（这是优化器放弃索引的依据）
     Extra       → 有没有 filesort / temporary？是 Using index 还是 Using where？
3. EXPLAIN ANALYZE 对比估算与实际 → 差距大 → ANALYZE TABLE / 建直方图
4. 还不行 → optimizer_trace（MySQL）看优化器的决策依据；
            或 SHOW STATUS LIKE 'Handler%' 前后取差值，直接数出
            "实际扫描了多少行、读了多少个索引项"

最后这一步尤其值得强调：Handler_read_* 这些计数器是”实际发生的事”，而 EXPLAIN 是”优化器的预测”。当预测和事实打架时，永远相信事实。

演进脉络

早期：顺序文件 + 全表扫描。
1970 年：Bayer 和 McCreight 提出 B 树，为磁盘 IO 优化的多路搜索树成为主流。
1970s-80s：B+ 树成为关系型数据库事实标准（叶子链表支持范围扫描）。
1990s：LSM 树被提出，为写密集型场景提供顺序写方案。
2000s：BigTable 论文的 SSTable + LSM 架构，催生 HBase、Cassandra、LevelDB、RocksDB。
2010s：列式存储 + 向量化执行（ClickHouse、Doris），索引和分析进一步融合。
2018 至今：学习型索引（Learned Index）——用机器学习模型替代传统索引结构，如果数据分布有规律，模型能比 B 树更快更小。这是”用数据分布的知识换搜索时间”的最新形态。

主线：索引的演进，是不断在”读性能、写性能、空间”这个不可能三角里找平衡点——B+ 树求均衡，LSM 求写快，列式求分析快，学习型索引求用数据规律换一切。

本章思考题

【思考题】

索引为什么能加速？它”省”掉的是什么？为什么”有序性”是索引的核心？
为什么数据库的默认索引是 B+ 树而不是哈希或二叉树？请从磁盘 IO 的角度解释。
LSM 树把随机写变成顺序写，它把成本转移到了哪里？什么场景适合 LSM、什么场景适合 B+ 树？
为什么不能给所有字段都建索引？“选择性”怎么影响索引的价值？
B+ 树的节点分裂和合并具体是怎么发生的？为什么”填充因子”这个参数会显著影响写入性能？
什么是聚簇索引？“回表”的代价到底由哪几部分构成？为什么回表几千行可能比全表扫描一百万行还慢？
覆盖索引为什么能大幅提升性能？它付出的是什么代价？索引下推（ICP）解决的是什么问题？
用最左前缀原则判断：有索引 (a, b, c) 时，a=1 AND c=3、a=1 AND b>5 AND c=3、a>1 AND b=5 各自能用上几列？设计复合索引时，列顺序该怎么排？
LSM 的 MemTable 为什么通常用跳表？SSTable 内部大致是什么结构？Size-Tiered 和 Leveled 两种 Compaction 策略各自的取舍是什么？Bloom Filter 加速的是哪类查询、为什么它帮不上范围查询？
倒排索引里 posting list 为什么要按 docID 升序存？为什么要做 d-gap + 分块压缩？求交时为什么”让最短的 posting list 打先锋”？
位图索引为什么只适合低基数字段？请用”基数 × 行数”的账说明。Roaring Bitmap 是怎么解决稀疏问题的？它为什么不适合高并发写入场景？
列式存储里的稀疏索引和 Zonemap（min-max 索引）是怎么”跳过数据块”的？为什么说它的有效性取决于数据的物理聚簇程度？“用元数据避免扫描”这个思想还能推广到哪些场景？
看到一个慢查询，你用 EXPLAIN 会重点看哪些字段？请举出四类会让索引失效的写法，并说明各自的原因和改法。
综合题：为什么”索引能不能生效”这件事，不只取决于索引结构本身，还取决于数据的物理组织方式？请至少用三个前面学过的概念来论证。

【参考答案】

索引通过维护”有序、可快速导航的结构”，让你不必遍历全部数据。省掉的是”必须检查所有候选”——把 O(n) 的遍历变成 O(log n) 或 O(1) 的排除。有序性关键，因为有序才能”排除”：二分查找每次排除一半，100 万条从 100 万次比较降到 20 次。所有索引本质都是”用不同方式组织数据，从而实现不同方式的排除”。
磁盘场景的关键约束是”随机 IO 极慢（约比内存慢 10 万倍），且按页读写”。二叉树太”高瘦”（100 万条要 20 层 = 20 次 IO）；哈希不支持范围查询。B+ 树”矮胖”：每个节点一个磁盘页、扇出成百上千，100 万条只要 3~~4 层 = 3~~4 次 IO，且叶子节点链表化让范围扫描极高效。在慢介质上，“减少访问次数（树高）“比”减少单次成本”更重要。
LSM 把随机写换成”顺序写 + 后台合并”，成本转移到了：读放大（查询要查多个 SSTable）、写放大（compaction 反复重写）、空间放大（合并期间新旧并存）。所以 LSM 适合写多读少（时序、日志、metrics），B+ 树适合读写均衡或读多写少（OLTP 业务表）。没有绝对优劣，取决于读写比例。
索引代价：写放大（每次写要同步更新所有索引，10 个索引 = 11 次写）、空间占用、优化器负担（可能选错计划）。选择性 = 不同值数/总行数，越高索引越有价值：主键选择性=1 价值最大；性别（2 值）普通 B 树索引几乎无用（但位图索引有用）；若某值占 90%，查它用索引反而比全表扫慢。所以建索引要看选择性，不是越多越好。
分裂：叶子页满还要插入 → 申请新页、搬走约一半 key、把中间 key 提到父节点（叶子分裂是”复制”上去，因为叶子必须持有全部 key；内部节点分裂是”上移”）→ 父节点可能也满，递归向上，根分裂则树高 +1（此后每次查询永久多一次 IO）。删除使占用率跌破阈值时，先向兄弟”借”（rotation，只改父节点分界 key，代价小）；借不到才合并，父节点少一个孩子，可能级联向上，根只剩一个孩子则树高 -1。填充因子 = 建索引/分裂时页保留多少空闲。填满则空间利用率高但下一次插入立刻又要分裂；留 30% 空隙则能吸收一批后续插入，分裂频率大幅下降。它同时影响三件事：IO 次数、空间利用率、物理碎片（碎片让范围扫描从顺序 IO 退化成随机 IO，这才是真正的杀伤力）。随机 key 插入最惨（页页接近满 + 碎片重），顺序 key 最省（只在最右页追加，物理顺序≈key 顺序），但顺序插入会带来尾部争用和分布式场景下的分片热点，所以要用加盐/哈希前缀打散——又是一次”顺序换 IO、打散换并发”的取舍。
聚簇索引（InnoDB）：表数据本身就存在主键 B+ 树的叶子上；二级索引的叶子存的是主键值而非物理地址（存物理地址会导致行因页分裂搬家时要更新所有索引，写放大爆炸；用主键是一层间接，用多一次查找换”行可自由移动”）。回表的代价三笔账：① IO 账——多走一棵树 = 多 3~4 次页访问；② 顺序账（真凶）——二级索引里同 key 的那些行，主键通常是乱的，回表是在聚簇索引的页之间跳跃，N 行就是 N 次随机 IO，而全表扫描是顺序 IO，机械盘上顺序比随机快一到两个数量级，所以”回表几千行比顺序扫一百万行慢”是可能的；这个”索引扫描顺序与行物理顺序的相关性”就是聚簇因子（clustering factor）；③ 行数账——rows×filtered 超过某个比例（经验上总行数的 10%~30% 量级）时优化器会主动放弃索引选全表扫，这不是”失效”而是”算完账发现顺序扫更便宜”。
覆盖索引：查询需要的所有列都在索引里 → 不回表（EXPLAIN Extra = Using index）。提升巨大的原因正是消灭了”N 次随机 IO”，而不只是”少查一次”（如 SELECT COUNT(*) WHERE status=1 只在索引叶子层顺序扫）。代价：索引越宽 → 每个页装得越少 → 扇出下降 → 树变高、缓存命中率下降，且每次写都要维护更胖的索引（写放大上升）。本质是用”索引页空间 + 写入成本”置换”回表的随机 IO”，所以只对高频、返回行数多、需要列很少的查询做。ICP（索引下推）：把”索引里有、但不能用来定位”的那部分 WHERE 条件下推到存储引擎，在回表之前先判断，不满足就跳过（Extra = Using index condition）。它解决的是”大量注定被过滤的行白付了回表代价”的问题，是”把过滤尽量往离数据近的地方推”这一大原则的实例（同族还有 predicate pushdown、Parquet min-max 裁剪）。一句话：覆盖索引消灭回表，ICP 减少回表，对付的都是随机 IO。
判据：“满足条件的记录在索引里是不是连续的一段”。① a=1 AND c=3：a 锁定一段，段内按 b 排序而非 c，c=3 散落在段里 → 只有 a 定位，c 只能当过滤器（可用 ICP）。② a=1 AND b>5 AND c=3：a、b 定位，c 靠边站（key_len 只算到 b）。③ a>1 AND b=5：只有 a 定位，因为 a>1 之后 b 全局不再有序。规律：从最左列起，连续等值匹配的列共同确定连续区间；一旦遇到范围/不等值/函数/中断，右边所有列都只能当过滤器。排序列顺序按优先级：① 等值列在前、范围列在后（范围列后面全废，放最后损失最小）；② 能让区间缩得最快的等值列更靠前（通常即区分度高的），但”几乎每个查询都带的列”（tenant_id、shop_id）必须放第一，哪怕区分度不高——查询模式的稳定性权重高于单列区分度；③ ORDER BY / GROUP BY 的列按排序顺序紧跟等值列后面，复用索引有序性省掉 filesort 和临时表（混合 ASC/DESC 在 MySQL 8.0 之前用不上）。另外，索引设计是”用最少的索引覆盖最多的查询模式”的集合覆盖问题，找高频查询的公共前缀来合并；有了 (a,b,c) 后 (a)、(a,b) 都是冗余索引。
MemTable 用跳表：有序遍历天然是链表顺序扫（范围查询友好，红黑树要中序遍历），插入只改局部指针、锁粒度小、并发控制简单，实现短；代价是指针开销和缓存局部性差，但都在内存里，相对磁盘 IO 是零头。SSTable 布局：若干 Data Block（块内按 key 有序，前缀压缩 + 每隔若干条存一个”重启点”完整 key）+ Filter/Meta Blocks（Bloom Filter 数据）+ Meta Index Block + Index Block（每个 data block 的最大 key + 文件内偏移，常驻内存，是 data block 的稀疏索引）+ Footer（记录 index/metaindex 位置 + 魔数，是”索引的索引”）。Compaction 取舍：Size-Tiered 把大小相近的 SSTable 合并成更大的，写放大低，但读放大高（一个 key 的新旧版本散落多文件）、空间放大高（需预留大量空闲磁盘）；Leveled 分层、除 L0 外层内 key 范围互不重叠、每层大小为上一层固定倍数，读放大和空间放大低，但写放大高（key 每沉一层就被重写一次）。一句话：STCS 用空间和读换写便宜，Leveled 用写放大换读快和省空间；RocksDB 用混合策略（L0→L1 类 tiered，上层 leveled）+ 限流来折中。Bloom Filter：每个 SSTable 一个，常驻内存，有假阳性但绝无假阴性，所以最擅长加速”查一个不存在的 key”（LSM 读放大的最坏情况）——凡回答”没有”的文件一次 IO 都不做。它帮不上范围查询，因为只回答”这个 key 在不在”；scan 仍需 k-way 归并所有相关文件。
按 docID 升序存的三个理由：相邻差值小 → 好压缩；有序链表可线性求交；结果天然有序，便于去重和取 top-k。压缩：① 存 d-gap 而非绝对值（词越热、文档集越大，差值越小）；② 分块 + 帧内同宽（Frame of Reference，块内统一 bit 宽度打包，可被 SIMD 批量解码；超大差值当异常值补丁存块尾，即 PForDelta）；另一路线是 Elias-Fano，能在压缩态下直接随机访问和跳过。压缩的真正动机不只是省空间，更是让更多 posting list 待在内存/缓存里——用 CPU 时间换 IO。求交加速：跳表/跳跃指针（每隔固定文档数记一个 docID+偏移，直接跳过去，Lucene 是多层跳跃）、leapfrog 蛙跳（固定一个基准，另一个反复跳过它）、以及”最短 posting list 打先锋”——因为交集大小的上界就是最短列表的长度，用短列表驱动能让长列表跳跃最多、跨度最大；查询”罕见词 AND 常见词”从罕见词起步能省掉绝大部分工作，df 存在词项字典里就是为此服务的（这也是”多加几个词反而更快”的原因）。再进一步，若要 top-k 而非全部结果，可用 WAND/MaxScore 按”剩余词最大可能得分”整体跳过不可能进榜的文档，连交都不做完——体现”索引提供可跳能力、算子决定跳得值不值”的协同设计。
空间账：总空间 = 基数 C × 行数 N bit。性别 C=2、N=1 亿 ≈ 25MB，极划算；用户 ID 的 C≈N=1 亿 → C×N 天文数字，直接崩。所以位图索引的适用边界由 C×N 决定而非只由 N 决定，它统治的是性别/省份/状态/标签/类目这类低基数维度，以及 OLAP、用户画像、广告人群圈选。Roaring Bitmap：把 32 位空间按高 16 位切成 65536 个容器，每个容器按基数自动选结构——稀疏用 ArrayContainer（有序 uint16 数组，可二分/galloping 求交），稠密用 BitmapContainer（8KB 位图，可上 SIMD），连续段多用 RunContainer（游程）；切换阈值 4096 正好是 4096×2B = 8KB = BitmapContainer 大小，即两种表示的空间占用交叉点，不是拍脑袋定的。求交时可两级剪枝（先按高 16 位跳过空容器，再在容器内选最合适的算法）。不适合高并发写入：改一行的一个枚举值要改压缩位图的一个 bit，而一个 word 被 64 行共享 → 要加锁、可能解压重压、可能重写整块，锁竞争严重（Oracle 在 OLTP 表上建位图索引是著名的生产事故来源）。它属于”一次构建、多次只读查询”的世界。
稀疏索引：每 N 行（如 ClickHouse 每 granularity 默认 8192 行）建一条索引标记，只定位到块；100 亿行的表索引仅约 100 万条标记，可整个常驻内存，代价是块内仍要扫——但列存只读取所需列 + 压缩数据 + 向量化执行，扫得飞快；本质是”用精度换体量”，与 B+ 树的稠密索引形成对照（OLTP 精确取一行付得起 45 次 IO，OLAP 一次取几亿行付不起）。Zonemap：每个数据块记录每列的 min/max（还可加 null 计数、distinct 集合、块级 Bloom），谓词与区间不相交则整块跳过，一个字节都不读（Parquet/ORC 的 row group 与 page statistics，ClickHouse 的 minmax/set/bloom_filter skipping index）。关键坑：若该列随机分布，几乎每个块的 min-max 都覆盖全域 → 一块都跳不掉 → 完全失效；所以有效性取决于数据的物理聚簇程度，即”这个索引其实不在索引里，而在数据的物理组织里（ORDER BY/分区/聚簇方式）“。推广：“用元数据避免扫描”是一个多层漏斗——① 分区裁剪（TB 级，成本近乎零，只对分区键有效）；② 稀疏索引/Zonemap/块级 Bloom（MBGB 级，元数据常驻内存）；③ 倒排/位图（行级精确集合，一次指令判 64 行，但空间按 C×N 增长）；④ B+ 树/稀疏索引定位（精确到行，3~5 次随机 IO，最贵）；⑤ 物化视图/预聚合（连扫都不扫）。分层的理由是每层的”排除成本”和”排除粒度”不同；索引设计的艺术就是按查询模式把这些层叠成漏斗，让数据在每一层都被廉价地削掉一大截。
EXPLAIN 重点看：type（system/const/eq_ref/ref/range/index/ALL，见 ALL 或 index 就警惕）、key（最终选中的索引）、key_len（复合索引实际用了几列，是排查最左前缀问题的第一手证据）、rows×filtered（≈预计回表行数，正是优化器放弃索引的依据）、Extra（Using index 覆盖=最好；Using index condition=ICP 次好；Using where=回表后才过滤；Using filesort/Using temporary=常是慢查询元凶）。再用 EXPLAIN ANALYZE 对比估算与实际，差距一个数量级以上说明统计信息失真，先 ANALYZE TABLE。四类失效写法：① 函数/表达式包裹列（DATE(created_at)=…、amount*2>100），因为索引的有序性与判断标准不是同一个有序性；改法是运算挪到常量侧（created_at >= d AND < d+1），注意不对称——给列加函数失效、给常量加函数不失效；实在需要就建函数/表达式索引。② 隐式类型转换（VARCHAR 列与数字比较 → MySQL 把字符串转数字 → 列被套函数 → 失效；反之 INT 列与字符串比较转换在常量侧，索引照常可用）；JOIN 列字符集/collation 不一致同理。③ 前导模糊查询（LIKE ‘%abc’），因为 B+ 树按从左到右的字符序排，不知开头就无处下嘴；真正的解法是换结构——全文索引/倒排，或 n-gram 分词支持任意位置匹配。④ OR 条件（a=1 OR b=2 且 b 无索引 → 因为”满足 b=2 的行”必须全表扫才能找齐，整条退化）；改法是拆成 UNION ALL 各自走索引，或给 b 建索引走 index_merge（但 index_merge 常被低估）；同列的 OR（a=1 OR a=3）会转成 IN，正常走索引。另有两类”看起来失效其实理性”：优化器因回表行数太多主动放弃索引（该做的是变覆盖索引/加 LIMIT/缩小结果集，而非 FORCE INDEX）；统计信息失真或分布倾斜（建直方图）。兜底手段：optimizer_trace 看决策依据，或 SHOW STATUS LIKE 'Handler%' 前后取差值直接数出实际扫描行数与索引项读取数——当预测与事实打架时永远相信事实。
核心论点：索引提供的只是”某种顺序下的可导航性”，而真正决定代价的是”沿着这个顺序访问时，物理上是不是连续的”。三个概念：① 聚簇因子（clustering factor）——二级索引扫描顺序与表中行物理顺序的相关程度。它直接决定回表是不是随机 IO；相关性差时，走几千行索引回表比顺序全表扫一百万行还慢，优化器因此理性地放弃索引。② B+ 树的碎片与填充因子——随机插入导致的页分裂把 key 相邻的记录在物理上拆散，同一个索引、同一条 SQL，在”刚重建过”和”跑了一年”的表上性能可以差一个数量级；顺序插入虽好却带来尾部争用与分片热点。③ Zonemap/稀疏索引的跳过率——块级 min-max 能否跳过数据块，完全取决于该列是否聚簇：随机分布时每个块的区间都覆盖全域，跳过率为零，“索引”名存实亡。此外还有：LSM 里 SSTable 的 key 范围重叠程度（L0 重叠多 → 读放大高）、列存的 ORDER BY 键选择、以及分区裁剪只在按分区键组织时才成立。统一结论：索引不是一个可以脱离数据布局单独评估的组件，它是一个”结构 + 物理组织 + 维护状态”的组合体。 所以索引优化的一半工作不在 CREATE INDEX 语句里，而在主键选型、插入顺序、分区与排序键、以及定期重建与统计信息维护里。

徐术挺-漫思录

探索

07-索引与查找