数据库索引
索引先将条件缩小到候选键，再通过 RID 找到行所在堆页。RID 是地址，不是行内容；请求列不在索引中，还要读堆页。本课用“索引页读取 + 不同堆页读取”与全表扫描比较，只有前者更少，才在该冷页计数模型中节省访问。
哈希索引用于等值桶定位，B+ 树保留键顺序，INCLUDE 载荷可能直接回答投影。同一张小表与相同查询结果下，变化的是需要访问的页，不是结果行。
数据库索引如何工作
默认查询：
SELECT tier
FROM customers
WHERE customer_id = 84;
表有 16 行，每堆页两行，共八页。物理顺序与 customer_id 无关，匹配行为 RID P7:S0，即第 7 页第 0 槽。
全表扫描读取八页，逐页检查两行，即使只有一行符合也读完。页而非行是本模型计费单位。
哈希索引计算桶号。桶中有多个 key→RID，可能碰撞，所以要比较完整键。84 落在 H4，找到 84 → P7:S0 后再读 P7，共两页。
B+ 树先读根 I0，按分隔键选叶 L3，找到同一 RID，再读 P7，共三页。覆盖 B+ 树把 tier 放在叶载荷中，I0、L3 就能返回 Basic，无需 P7，共两页。
| 路径 | 默认读取 | 构成 |
|---|---|---|
| 全表扫描 | 8 | 全部堆页 |
| 哈希索引 | 2 | 一桶加一堆页 |
| B+ 树 | 3 | 根、叶、堆页 |
B+ 树 + INCLUDE (tier) | 2 | 根、叶，投影在叶中 |
数值属于当前布局，不是数据库通用基准。要保留的是索引页与不同堆页的成本拆分。
等值、范围与键顺序
哈希把精确键映射到桶，但不保留键大小顺序。68 到 84 不一定落在相邻桶，按桶号区间模拟 BETWEEN 会漏行。
B+ 树范围查询 customer_id BETWEEN 68 AND 84 先下降到 L2，再沿有序兄弟链接到 L3，找到五个键。普通树跟随五个 RID 到五个不同堆页，总计根一页、叶两页、堆五页，八次读取。覆盖树的 tier 已在叶中，只读三索引页。
等值可使用两种结构，范围需要支持键顺序的访问方式，不能凭桶号看起来有序就当范围索引。
覆盖与回表
二级索引定位行，不必然包含所需列。RID 将逻辑键顺序连接到物理堆存储。同一次路径中，多个符合 RID 若在同一堆页，会合并成一次读取，不重复计费。
覆盖与查询有关：(customer_id) INCLUDE (tier) 能回答默认条件和投影，若投影改成 email，同一叶就不够。未覆盖预设仍需沿 P7:S0 回表。加入更多列会加宽索引、增加空间和写入成本，不是免费补全。
优化器为何可能不用索引
低选择性预设查询十个 Basic 客户，它们分布在全部八堆页。普通 B+ 树读一根、三叶、八堆，共 12；全表只读八堆，省去四索引页，因此选择扫描合理。
选择性决定符合条目数量，聚簇程度决定 RID 分散到多少页。少量结果在一页，与大量结果散布全表，成本不同。索引合法也可能更贵。
比较面板保留四种路径的模型成本，但当前问题是“所选索引是否值得代替扫描”。其他总数标成假设方案，不表示所有索引同时存在，也应实际回放对应路径后再检查依据。低选择性普通 B+ 树答案为否；若另有覆盖索引，可免堆读，候选方案便不同。
索引访问逐步演示
- 查看 SQL 条件与投影，明确等值或范围需要的能力。
- 回放扫描基线，每个
P# heap标记代表整页读取。 - 回放所选索引，哈希定位桶，B+ 树读取根及所需叶。
- 核验候选键，碰撞需完整比较，树叶则维持有序区间。
- 判断载荷是否覆盖投影，不覆盖就收集 RID。
- 按堆页分组，每个不同页读一次。
- 比较当前冷逻辑页总量，保留成本最低的合法方案。
缺失键预设中，85 不在候选桶或叶，索引即可证明无匹配，不读堆。失败查找可能比成功更便宜，因为不再取行。
边界情况
- 缺失等值键在桶或叶中确认，无回表。
- 跨叶范围从 L2 沿兄弟链到 L3，哈希没有相同的有序路径。
- 44、52、68、84 共用 H4，桶相同不等于键相同。
- 同页多个 RID 共享一次逻辑页读取。
- 覆盖 tier 不保证覆盖 email。
- 低选择性普通索引可能读全部堆页，再额外付索引成本。
页读取复杂度
设堆页数 P、索引条目 N、B+ 树扇出 f、访问叶页 L、匹配所在不同堆页 H。
- 扫描为
O(P)堆读。 - 哈希等值平均
O(1)桶页，加 H 个堆页。 - B+ 点查为
O(log_f N)层，加 H。 - B+ 范围为
O(log_f N + L + H)。 - 当前覆盖模型走同样索引路径，但投影在叶中，H=0。
这些是访问规模，不是耗时。缓存、预取、硬件、并发、统计估计会改变真实成本；实际 index-only 扫描还可能因可见性检查访问堆。
阅读实际查询计划
检查估计与实际符合行数；索引条件、投影及是否 index-only；堆取次数与数据页，而非只看索引查找；竞争扫描方案及统计过时、聚簇差、基数估错；缓存、预取、引擎对哈希和 INCLUDE 的支持；宽索引的存储与写放大。
这些因素都可能改变冷页模型的选择。要问的是这条路径增加了哪些工作，又避开了哪些页。
常见错误
- 认为索引让所有查询更快，低选择性非覆盖索引可能先增成本再扫近全表。
- 把有编号的哈希桶当有序键范围。
- 把 RID 当值，忽略跟随地址还需读页。
- 不说明查询就说“这个索引覆盖”，覆盖依赖条件和投影。
- 每个匹配行算一次堆读，忽略同页合并。
- 把显示总数当 PostgreSQL、MySQL 的固定成本。
模型范围
冷逻辑页模型只含两层小 B+ 树、固定桶、非聚簇堆。省略缓冲驻留、系统缓存、预取、可见性、MVCC、锁、压缩、溢出桶链、树高变化、统计不确定性、写放大、引擎布局。真实优化器同时估算 CPU、I/O、缓存、相关性、基数。本课只隔离“返回相同逻辑行，需要碰哪些页”。