第14章 索引
依据原书第7版完整目录覆盖11个节点：比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本
第14章 索引
本课程对应Abraham Silberschatz、Henry F. Korth、S. 在“第14章 索引”的证据链中，Sudarshan著，杨冬青、李红燕、张金波等译《数据库系统概念（原书第7版）》，机械工业出版社2021年6月出版，820页，ISBN 9787111681816。原版第7版由McGraw-Hill于2019年发布。课程按原书11部分、32章与附录A逐项重构，不复制原文。
中文版第7版纸书正文收录第1-23章；第24-26章由中文版提供中文在线内容；第27-32章是原版官网英文在线章节；附录A在纸书中。本页媒介为“纸书正文”。 全课程另设学习地图与总复习，共35页；正式知识分母仍是32章与附录A。本页属于“第五部分 存储管理与索引”，依据正式目录覆盖11个节点。
“第14章 索引”没有使用未获授权的中文纸书正文；以 作者官网第 7 版完整目录 界定 32 章与附录 A，以 作者公开在线章节、大学模式实验 和 McGraw-Hill 第 7 版变更说明 核对可公开内容。中文解释、SQL、图示、实验与练习均为独立教学重写；实现行为再以 PostgreSQL 官方文档 等一手规范复核。
学习目标
- 能解释“第14章 索引”的11个正式节点，并把它们连接到“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”主线。
- 能复现B+树动画、索引选择矩阵、写放大测量和执行计划证据，记录输入版本、配置、预期、实际结果与失败边界。
- 能比较至少两种实现或故障条件，证明“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”。
- 能设计反例推翻“为每列盲目建索引，或只看单次查询加速而忽略写放大、空间和维护成本”，并给出修复、回退和独立验收条件。
从一次可观察状态变化开始
先预测：给定一份固定的大学数据库、一个操作和一个故障时刻，哪些逻辑行、物理页、锁、版本或日志记录应该变化，哪些绝不能变化？不要先运行再解释。把预测写成状态表，然后用独立查询、执行统计、页或日志轨迹核对。若预测与观察不一致，先检查模型和实验边界，而不是立即改配置。
本页主问题是“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”。交付不以读完为准，而以另一位学习者能从B+树动画、索引选择矩阵、写放大测量和执行计划证据复现同一结论为准。最小正确性合同是：索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量。
核心词汇与系统边界
↡B+树是“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”中的第1个核心概念；必须由状态、机制、反例和证据共同定义、↡哈希索引是“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”中的第2个核心概念；必须由状态、机制、反例和证据共同定义、↡聚簇索引是“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”中的第3个核心概念；必须由状态、机制、反例和证据共同定义、↡LSM树是“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”中的第4个核心概念；必须由状态、机制、反例和证据共同定义、↡位图索引是“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”中的第5个核心概念；必须由状态、机制、反例和证据共同定义 构成本页词汇表。每个词都要回答四个问题：它约束什么状态，由哪个模块执行，在哪个故障或并发边界会失效，用什么证据发现失效。只给一句名词解释不构成掌握。
平衡多路搜索树：点查范围都高效，顺序访问叶子链表，是关系库的主力索引。
第七版机制逐项深读
14.1 基本概念
在“第14章 索引”中，“14.1 基本概念”的交付物至少包含可重放 SQL、输入基线、正常轨迹、失败样本和恢复终点，不能只留最终截图。
14.2 顺序索引
在“第14章 索引”中，分析“14.2 顺序索引”先固定键分布与谓词选择率，再比较全表扫描、树、哈希或位图路径的真实页访问。
14.3 B+树索引文件
在“第14章 索引”中，“14.3 B+树索引文件”用额外结构换取定位速度；必须同时计算搜索 I/O、维护成本、空间和范围查询能力。
14.4 B+树扩展
在“第14章 索引”中，“14.4 B+树扩展”不会自动提升所有查询；低选择率、过多随机写和统计信息偏差都可能让优化器放弃它。
14.5 哈希索引
在“第14章 索引”中，“14.5 哈希索引”不会自动提升所有查询；低选择率、过多随机写和统计信息偏差都可能让优化器放弃它。
14.6 多码访问
在“第14章 索引”中，“14.6 多码访问”用最小属性集唯一标识元组，并通过外码把引用限制到被参照键；验证要覆盖重复、NULL、更新与删除四条路径。
14.7 索引创建
在“第14章 索引”中，验证“14.7 索引创建”只改变数据倾斜或写入比例，记录树高、分裂/合并、写放大和计划是否切换。
14.8 写优化索引结构
在“第14章 索引”中，“14.8 写优化索引结构”用额外结构换取定位速度；必须同时计算搜索 I/O、维护成本、空间和范围查询能力。
14.9 位图索引
在“第14章 索引”中，验证“14.9 位图索引”只改变数据倾斜或写入比例，记录树高、分裂/合并、写放大和计划是否切换。
14.10 空间与时态数据索引
在“第14章 索引”中，“14.10 空间与时态数据索引”提供超出扁平标量的结构表达；验证要保存模式约束、路径查询、缺失字段和索引能否得到相同语义。
14.11 小结
在“第14章 索引”中，“14.11 小结”组织“依据原书第7版完整目录覆盖11个节点：比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”的语义、结构、执行和证据；若不能给出一个状态变化与独立对账，本节点仍未完成。
机制推演：从语义到物理证据
B+树通过有序叶链支持点查与范围查，哈希擅长等值访问，LSM把随机写转为顺序合并，位图利用低基数压缩，空间索引按区域层次剪枝。选型必须同时测读、写、放大和并发维护。
推演时始终区分五层。在“第14章 索引”的证据链中，第一层是业务不变量，说明哪些数据库状态合法；第二层是逻辑模型与查询语义，说明结果应该是什么；第三层是物理计划和数据结构，说明系统怎样得到结果；第四层是并发、日志与复制协议，说明交错和故障后仍保留哪些承诺；第五层是观测证据，说明我们怎样知道前四层真的成立。性能优化只能改变第三层和部分第四层的实现，不能悄悄改变前两层。
对每个节点建立因果链：输入版本与配置 → 操作或调度 → 中间状态 → 可观察输出 → 独立对账。在“第14章 索引”的证据链中，若结论涉及性能，报告中位数、尾延迟、吞吐、I/O和等待，而不是只截一条最快记录；若涉及正确性，至少准备一个应成功样本和一个应失败样本，并记录错误类别或恢复终点。
证据解释与交接
语义证据证明结果定义没有漂移。保存关系模式、约束、查询文本、参数、隔离级别和预期行集；涉及NULL、重复、顺序或聚集时，单独列出处理规则。任何实现比较都必须共享同一语义合同。
执行证据证明机制判断可以复核。保存计划、实际行数、缓冲命中、I/O、锁或版本、日志位置和错误状态中与本章相关的部分。计划估计与实际偏差本身就是结果，不应通过只截取计划名称隐藏。
失败证据证明边界真实存在。每次只注入一个变量：空输入、重复键、倾斜、并发冲突、进程崩溃、存储丢失或网络分区。明确失败前最后一个持久状态、恢复后第一个可用状态，以及是否需要人工介入。
交接证据让另一位学习者无需口头补充就能复现。最少包括版本卡、大学模式加载与重置脚本、预测表、B+树动画、索引选择矩阵、写放大测量和执行计划证据、正常与失败轨迹、独立对账、已知限制和回退条件。若更换DBMS或版本，先重跑基线再比较。
本章回顾
重新完成“比较B+树、哈希、LSM、位图与空间索引的查找、写入和维护成本”：先声明不变量和输入版本，按11个目录节点建立模型，手算正常路径，注入一个边界或故障，收集语义与执行证据，最后由独立查询对账。最终交付B+树动画、索引选择矩阵、写放大测量和执行计划证据，并能证明“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”。
小结
- B+ 树平衡查找与范围扫
- 哈希索引只适合等值查询
- LSM 优化写密集场景
- 位图索引服务低基数列
- 索引维护成本随写入累积
复习与独立验收
练习
问题 1：为什么“第14章 索引”必须覆盖11个目录节点？
问题 2：本页最小正确性合同是什么？
问题 3：怎样构造能推翻常见错误的最小反例？
问题 4：为什么执行成功不能证明数据库设计正确？
问题 5：性能结论至少需要哪些数据？
问题 6：独立交接至少包含什么？
名词解释
本章出现的专业名词，用大白话再讲一遍。
- B+树
B+树在本页中以“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”为正确性边界，并由可重放实验验证。
- 哈希索引
哈希索引在本页中以“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”为正确性边界，并由可重放实验验证。
- 聚簇索引
聚簇索引在本页中以“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”为正确性边界，并由可重放实验验证。
- LSM树
LSM树在本页中以“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”为正确性边界，并由可重放实验验证。
- 位图索引
位图索引在本页中以“索引顺序、选择性与覆盖属性匹配谓词，结构在分裂、合并和并发更新后保持不变量”为正确性边界，并由可重放实验验证。