06.05 索引结构：从历史游标到消息点查
返回第六卷 · SQL 游标前置：06.02 · 哈希前置：02.04 · 有序树前置：02.06 · 数据库页前置：06.04
06.05 索引结构：从历史游标到消息点查
DeepTutor 八节初稿经技术与教学审阅后的静态课程。会话
c-a、c-b、消息m-a、每叶两键及根分隔键都是纸上模型。没有运行 SQL、数据库、Go、基准或站点；没有推断 OpenIM 的物理存储布局。真实页访问、索引选择和性能需要 06.06 的执行计划与受控数据验证。
一、先问业务要找什么，再问索引怎样排
06.01 把消息定义为有身份的记录，06.02 用 SQL 提出“查 c-a 更旧的三条消息”，06.04 再说明记录要经过数据库页与缓冲池。现在问题变成：数据库凭什么迅速定位目标范围？ 暂定已通过会话成员权限校验；索引只能帮助找到候选，不能替代这一步。
固定两个需求。历史接口持有上页给出的游标 7，要查 conversation_id='c-a' AND seq<7 ORDER BY seq DESC LIMIT 3；另一接口用稳定 message_id='m-a' 精确找一条消息。假设 c-a 有 seq=1..8，c-b 有 seq=1..3，且本题中一个会话内 seq 唯一。历史答案必须是 6、5、4；m-a 的点查只有一个键，题目尚未给它对应哪一行，不能凭 ID 猜正文或 seq。
表保存记录，索引另外维护“可比较的键 → 对应记录或定位信息”。没有合适索引时，查询可以扫描记录并过滤；有索引时，也不等于一定更快：要读取索引结构、可能再取数据页，还可能因数据量小或选择率差而由规划器选择扫描。先把三种对象拆开：业务 seq 是会话内次序；索引键决定搜索顺序；数据库页是存储/缓存单位。它们不会自动共享同一个编号。
| 需求 | 先要保留的语义 | 候选访问结构 |
|---|---|---|
c-a 中 seq<7，倒序取 3 条 | 同一会话、严格小于游标、稳定顺序 | 以 (conversation_id,seq) 为键的有序索引 |
message_id=m-a | 精确匹配并保留唯一性规则 | 按 message_id 的唯一 B-tree/主键等值索引；是否使用哈希另评估 |
第一遍先掌握“有序键为什么让范围聚在一起”；第二遍再讨论覆盖、写入成本与 LSM。02.03 的二分查找和 02.06 的多路树是机制前置，但下面从头重画一棵小树。
二、从二分到 B+ 树：索引页负责导航，叶页负责连续扫描
已排序数组可以二分查找，但若索引大到分布在很多页里，逐项比较不是主要成本；要尽量让一次取页获得许多可比较的键。多路平衡树的内部页存分隔键与子页方向，较高扇出可减少导航层数；叶页按键序保存索引项，范围查询先定位边界，再沿键序走过后续项。这里把它称为 B+ 树入门模型；具体引擎是否给叶页双向兄弟指针、如何压缩键以及如何处理并发，都要看具体实现。
本题只画 (c-a,seq) 的八项，每个玩具叶页恰放两个索引键：
教学根页：分隔 (c-a,3) | (c-a,5) | (c-a,7)
↓ ↓ ↓ ↓
叶 L0：1,2 叶 L1：3,4 叶 L2：5,6 叶 L3：7,8根页的 3/5/7 是“右侧子树从这里开始”的导航边界，不表示只有根里才有 3、5、7，也不是三条额外消息。L0–L3 才是本题的索引叶页；它们与 06.04 的 P0..P15 数据页是两套独立模型。真实 B-tree 页能装多少项，取决于页大小、键宽、指针/元数据、压缩和填充；不能把“每叶两键”拿来估算生产容量。PostgreSQL 的 B-tree 具备有序比较能力，范围条件可以成为索引条件；这里的四叶一根没有模拟它的实际页格式。PostgreSQL B-tree 文档
若再加入 c-b，完整复合键会先按 conversation_id 比，再在同一会话内按 seq 比。可以把 c-b 想成接在 c-a 段之后的另一段；上面四叶仅画 c-a 子问题，加入新键后页划分和根可能改变。不能一边说根只覆盖八键，一边把 c-b 也算入这四叶。
三、手算一次历史游标：6、5、4 来自两张教学叶页
输入是严格不含游标的 seq<7。从根的分隔边界定位到 7 左侧，在 L2 找到最大合格键 6；按降序先读 6、5，再移到前一叶 L1 读 4，凑满三条便停。L3 的 7、8 不合格，L0 的 1、2 不需读。这是两张教学叶页 L2 和 L1：
| 步骤 | 位置 | 已返回 | 为什么继续或停止 |
|---|---|---|---|
| 1 | 根页定位 <7 的边界 | 空 | 定位过程不是消息结果 |
| 2 | L2，逆序读 6、5 | 6,5 | 还缺 1 条 |
| 3 | L1，读 4 | 6,5,4 | 达到 LIMIT 3 |
这个图为推理方便画了“往左一页”。真实实现可以通过向后扫描的索引游标、父路径或其他机制做到反向遍历，不要求每个 B+ 树都有显式左向叶指针。要把 seq 换成消息正文，还可能按索引项定位数据页并做可见性检查；根/内部页可能已经缓存；成员校验可能单独触页。因此“两张叶页”只是纸上索引叶页计数，既不是整条 SQL 的总页数，也不是两次物理磁盘 I/O。06.04 的 buffer miss 与设备读取区别在此仍成立。
改一个假设看结果：若条件为 seq<=7，返回 7,6,5，从 L3 跨到 L2；若 LIMIT 4 且仍是 <7，返回 6,5,4,3，仍可由 L2、L1 给出。边界符号和条数都会影响叶页访问，不能只记“范围查询用树”。
四、复合键的字典序：为什么列顺序服务业务条件
(conversation_id,seq) 按字典序排列，先比较会话，再比较序号。例如 (c-a,8) 在 (c-b,1) 之前，尽管 8 大于 1。这样 c-a 的记录构成一段连续的索引键范围，再在这一段内找 seq<7 与倒序结果。与之相反，仅有 seq<7、却没有固定会话，可能命中 c-a 与 c-b 两段及更多会话；它在这个复合键上不是一个单独的连续会话前缀范围。
不要把“左前缀有利于定位”误背成“缺左列时绝对不能使用索引”。PostgreSQL 当前多列 B-tree 文档允许在一定条件下使用 skip scan，规划器也可能选择全索引扫描或其他计划；具体收益取决于数据分布。MongoDB 的复合索引也要求先看索引字段顺序与可用前缀。一个可审阅的论证是：为固定会话的历史分页优先研究 (conversation_id,seq)，再用该引擎的计划核对是否真的命中目标访问路径。PostgreSQL 多列索引 · MongoDB 复合索引
反向遍历有序索引可能服务 DESC，但排序方向、NULL、混合升降序和引擎实现会改变可用性，不把 CREATE INDEX ... ASC 推导成所有数据库都能消掉任意 ORDER BY。若真实排序字段不唯一，例如多个消息有同一时间戳，游标还要包含稳定的次级键（如 message_id），查询条件和排序共同确定完整顺序；本题假定 (conversation_id,seq) 在会话内唯一，所以只用 seq 即可演示。
五、消息 ID 点查：哈希和 B+ 树都能等值，目标却不同
另一需求是 message_id='m-a'。02.04 学过哈希函数把键映射到桶：即使两键发生碰撞，也必须继续比较原键才能判定是否相等。若只有等值查找，哈希能提供候选访问路径；但哈希后的桶顺序不等于消息 ID 的业务顺序，无法靠桶顺序自然支持 <、> 或 ORDER BY 范围扫描。B+ 树同样能查单键，还保留键序，可承担更多范围需求。PostgreSQL 哈希索引文档
这里先提出一个教学索引草案：历史用 (conversation_id,seq)，点查用 message_id 的独立唯一索引或主键（是否已由主键实现，取决于已选表模式）。这不是“必须再创建两个索引”的命令。若 message_id 已是主键，再重复建同列索引只会增加维护成本；若一个点查请求在读取正文前还需检查会话成员，索引命中并不会绕过授权与记录可见性。唯一性也不能靠普通哈希碰撞概率代替数据库约束。
| 访问方式 | 等值 m-a | c-a 序号范围 | 需要额外看什么 |
|---|---|---|---|
| B+ 树键序 | 可用 | 复合键适配后可顺序扫描 | 根/叶页、回表、选择率 |
| 哈希键桶 | 可用，碰撞需核对原键 | 无自然有序范围 | 引擎限制、桶维护、点查比例 |
| 全表扫描 | 语义上可找出 | 语义上可筛选排序 | 行数、过滤率、排序和缓存 |
六、覆盖索引不是“永远不读数据页”
假设历史接口这一小题只要 message_id，而不是正文。以 PostgreSQL 为语法示意，可以研究：
CREATE INDEX messages_history_cover_idx
ON messages (conversation_id, seq) INCLUDE (message_id);
SELECT message_id FROM messages
WHERE conversation_id = 'c-a' AND seq < 7
ORDER BY seq DESC LIMIT 3;键列承担筛选与排序；INCLUDE 把 message_id 作为非键负载保存在索引里，这叫覆盖该查询所需的列。在 PostgreSQL，规划器可能选 index-only scan，但 MVCC 可见性信息不全时仍要访问 heap；“覆盖列”只满足索引里有数据这一条件，并不保证零 heap fetch。若改为 SELECT body，上面的索引根本不含正文；把大型正文也塞入索引，又会让索引项、空间与写入负担增加。PostgreSQL Index-Only Scans and Covering Indexes
每加一个索引，消息写入时就多了一份需维护的结构和持久数据；B+ 树可能分裂页，更新索引列可能引起新索引项，删除与可见性清理还受具体引擎规则影响。读三条的收益应和实际写入频率、索引尺寸、查询计划、回表量一起衡量。06.06 将学习读取 EXPLAIN 的估计与执行证据；本章不假装上面 SQL 已被执行，也不从纸上两叶算出生产 P95。
七、LSM：先聚写再合并的另一条索引/存储路线
B+ 树按页维护有序结构，LSM（Log-Structured Merge-Tree）则先把新键写入内存中的有序 memtable，在合适条件下把一批键刷成磁盘上有序的 SST 文件；多个时期的有序 run 再通过后台 compaction 合并。以 RocksDB 为例，它还有可配置的事务日志和同步选项；“写进 memtable”绝不能直接等同“消息已按应用合同耐久”。原始 LSM 论文提供该类结构的历史背景，RocksDB 架构文档说明 memtable、SST、log 和 range iterator。
为什么不直接宣布 LSM 更适合 IM？因为查一个键可能要考虑当前 memtable 和多个尚未合并的 SST；范围扫描也可能把多个有序 run 的候选合并。Bloom filter 等辅助结构可减少某些不存在键的文件探查，但需额外空间、构建和维护，且不能替代返回范围中真实键的读取。compaction 会重写数据，占用后台 I/O，并带来写放大、读放大和空间放大之间的取舍；不同压实策略方向不同。RocksDB Compaction 文档
这一节是比较结构，不是说 MongoDB、所有 NoSQL 或 OpenIM 都在使用 LSM。MongoDB 官方将其常规索引类型中的单字段与复合索引描述为 B-tree 类索引；对某个实际集合，仍需核对具体版本、索引定义和查询计划。MongoDB Index Types
| 决策问题 | B+ 树方向 | LSM 方向 | 仍需证据 |
|---|---|---|---|
| 连续历史读取 | 有序叶页范围扫描 | 多个有序 run 的归并与缓存 | 页/块访问、计划与热点 |
| 持续写入 | 更新有序页与索引项 | memtable、刷出与压实 | 写入率、压实压力与持久合同 |
| 按 ID 找消息 | 单键定位 | 查最新层及可能的旧层 | 缓存、过滤器、版本与负查比例 |
八、交付一个可复核的索引评审，而不是一条口号
把评审写成四步：①写清真实业务查询与成员权限；②列出键顺序和预期返回；③纸上推导范围/点查会经过哪些结构；④在具备隔离环境时用 06.06 的计划、数据分布与业务测量核对。当前可交付物如下，均为静态推导：
| 交付物 | 可核对结果 | 未声称的事 |
|---|---|---|
c-a、seq<7、降序取 3 | 6,5,4；玩具叶页 L2、L1 | 真实 SQL 只触两页 |
message_id=m-a 点查草案 | 检查既有唯一/主键索引，避免重复 | m-a 的具体消息正文 |
| 复合键/覆盖候选 | (conversation_id,seq)，可研究 INCLUDE(message_id) | 规划器必用、零回表、P95 改善 |
| 存储取舍记录 | 比较读、写、空间、压实、权限和可见性 | OpenIM 实际物理实现 |
分层练习与反馈
先做 1–8 的概念与键序，再做 9–16 的纸上查询，最后做 17–22 的设计评审。每题先写预测，再展开答案；任何“会更快”的结论都要附数据量、访问模式与验证方法。
1. `seq=6`、索引键和数据库页号分别是什么？
seq=6 是会话内业务序号；索引键可以是 (c-a,6)；页号是引擎用来定位某个索引或数据页的物理/逻辑页身份。三者不等同。
2. 本题历史查询的完整结果是什么？
在 c-a 的 1..8 中，严格小于 7 的最大三个序号是 6,5,4。不包含 7，也不混入 c-b。
3. 没有合适索引是否必然查不出正确结果？
仍可扫描、过滤、排序、限制条数，语义可能正确；成本需要另外分析。索引解决访问效率和部分排序工作，不定义授权。
4. 根页里的分隔键 5 是第五条额外消息吗？
不是。它在玩具图里是子页范围导航边界；记录的索引项仍在叶页 L2。
5. 06.04 的 P1 和本章 L1 能画等号吗？
不能。P1 是前章“每数据页四条”的玩具数据页；L1 是本章“每索引叶页两键”的玩具索引页，两模型容量与内容都不同。
6. 为什么 B+ 树的高扇出可能减少定位层数？
一个内部页能给很多子页提供范围边界，树可在较少层中覆盖大量键。实际层数取决于页和键，不能由本题四个叶页推广到生产。
7. 哈希桶碰撞时，可以只看桶号便宣布找到了 `m-a` 吗？
不能。碰撞让不同键进入相同桶，仍须比较完整原键，并执行数据库可见性及业务权限规则。
8. 哈希索引天然支持 `seq<7 ORDER BY seq DESC` 吗？
不支持按原键排序的自然范围遍历；哈希打散了键序。数据库仍可能使用其他访问与排序手段完成查询。
9. L0–L3 中，边界 `seq<7` 首先落在哪张合格叶页？
L2：其中 5,6 合格，最大的是 6。L3 的 7、8 不符合严格小于。
10. 取到 6、5 后，为什么还要看 L1？
LIMIT 3 还缺一项；按降序前一合格键是 L1 的 4，所以结果为 6,5,4。
11. 本题说“读两张叶页”包含根页和数据页了吗？
没有。只数教学叶页 L2、L1；定位还需根页，取正文还可能读数据页，缓存和可见性也会改变实际访问。
12. 把条件改为 `seq<=7`、`LIMIT 3`，返回什么？
7,6,5。等号使 L3 的 7 合格，随后走到 L2 的 6、5。
13. 保持 `seq<7`，把 `LIMIT` 改为 4，返回什么？
6,5,4,3；在玩具图中仍能由 L2 和 L1 给出，但多取一个索引项。
14. `(c-a,8)` 与 `(c-b,1)` 谁先排？
(c-a,8) 先排。字典序先比较会话 ID；只有会话相同时才比较 seq。
15. 只写 `seq<7`，没有会话条件，为何不是本题的同一连续范围？
每个会话有自己的序号段，满足条件的项分布于不同会话前缀段。引擎仍可能全索引扫描、skip scan 或采用其他计划，不能说绝对不能用索引。
16. 如果真实排序按可能相同的时间戳，游标还需要什么？
需要一个能打破同时间戳并保持稳定顺序的次级键，且排序与游标比较必须用同一组键。
17. `message_id` 已为唯一主键，是否应照草案再建一份同列唯一索引？
先检查主键现有访问路径；重复同列索引可能只是额外空间和写入维护，不应机械添加。
18. `INCLUDE(message_id)` 后可保证 PostgreSQL 永远零 heap fetch 吗？
不能。索引包含列仍需满足 MVCC 可见性条件；可见性映射不足时可能访问 heap，且规划器未必选择 index-only scan。
19. `SELECT body` 能被示例覆盖索引完整满足吗？
不能。示例键列是 conversation_id,seq，负载列只有 message_id，没有正文。把大正文盲目放索引会增加空间和写入成本。
20. 为什么不能把 LSM 的 memtable 写入直接叫“消息已耐久”？
memtable 在内存中。实际持久保证取决于日志是否启用、同步选项、存储故障模型与应用对外确认合同；需单独证明。
21. LSM 的 compaction 对写入没有任何代价吗？
有代价。合并可能重读和重写数据，耗 I/O 与空间；不同策略在读放大、写放大、空间放大间取舍。
22. 给“历史查询变慢，马上改 LSM”写一段评审反馈。
先核对查询与权限语义、现有复合索引和计划、数据分布、缓存/回表、业务 P95 与写入负载；再评估存储方案的读写空间代价和迁移成本。纸上模型不能证明瓶颈或新方案收益。
本章完成标准与下一步
不看答案，能画出 L0–L3，手推 6,5,4，说清两张索引叶页以外还可能发生的工作；能解释为什么 m-a 需独立点查路径、复合键列序为何服务历史查询，以及覆盖与 LSM 各有什么代价，才算完成第一轮。第二轮把这些假设带到 06.06 的查询计划，用真实数据规模和选择率核对，而不是据玩具页数宣布性能结果。
按学习路线，下一章06.06 查询执行与优化会从过滤、排序、连接、统计信息和 EXPLAIN 判断数据库实际上选了哪条路径；06.08–06.09 再处理并发版本和恢复边界。