06 · B 树与复合索引：沿着查询找数据
目标：根据过滤和排序条件解释一个复合索引能减少哪些读取。
从页面走到记录
上一课把更新写进不可变段。B 树家族通常把索引组织为固定大小的页：内部页保存分隔键和子页引用，沿着键范围逐层向下，直到叶层找到记录或记录位置。常见 B+ 树把记录放在叶层并连接叶页，便于范围扫描。页满了需要分裂，修改多个页时还需日志或写时复制等恢复机制。
这里的树不是每个键一个节点的普通二叉树。一页能容纳许多键，所以树往往很浅。真实读取成本还取决于缓存、行大小、回表和存储介质。LSM 与 B 树的选择也不能只用“写多或读多”一句话决定：都应测量稳定运行及维护期间的负载。
活动列表查询是 city = ?，按 starts_at 排序。索引 (city, starts_at) 先按城市分组，再按时间排列，同一城市的一段数据自然有序。反过来 (starts_at, city) 不能同样高效地缩小到一个城市。复合索引的字段顺序有业务含义。
让数据库说明读取路径
保存 indexes.py。下面确实使用 SQLite 的查询规划器，先预测加索引前是否需要扫描整个活动表。
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE activity(id INTEGER PRIMARY KEY, city TEXT, starts_at INTEGER)")
db.executemany("INSERT INTO activity VALUES (?, ?, ?)",
[(i, "north" if i % 2 == 0 else "south", i) for i in range(100)])
query = "SELECT starts_at FROM activity WHERE city = ? ORDER BY starts_at LIMIT 3"
before = db.execute("EXPLAIN QUERY PLAN " + query, ("north",)).fetchall()
db.execute("CREATE INDEX by_city_time ON activity(city, starts_at)")
after = db.execute("EXPLAIN QUERY PLAN " + query, ("north",)).fetchall()
assert any("SCAN activity" in row[3] for row in before)
assert any("by_city_time" in row[3] for row in after)
result = db.execute(query, ("north",)).fetchall()
assert result == [(0,), (2,), (4,)]
print("before_scan:", any("SCAN activity" in row[3] for row in before))
print("after_index:", any("by_city_time" in row[3] for row in after))
print(result)
db.close()
uv run --python 3.12 --no-project indexes.py
预期输出：
before_scan: True
after_index: True
[(0,), (2,), (4,)]
EXPLAIN QUERY PLAN 返回执行策略，具体描述字符串可能随 SQLite 版本变化，因此这里只检查关键特征。查询仅需索引中的字段，可以利用覆盖索引。若返回不在索引里的大段详情，通常还需要访问表记录。多建一个索引也意味着插入、更新和空间上的额外成本。
引导练习：① 将参数改为 south；② 预期结果改为 [(1,), (3,), (5,)]；③ 确认仍用同一个索引。不要为每个城市单建索引，它们共享同一种查询形状。
独立练习：增加条件 starts_at >= 90，保持城市过滤和升序，预测结果。说明只按 starts_at 查询时，为什么不能直接套用本课的效率结论。
参考修改
把查询替换成 SELECT starts_at FROM activity WHERE city = ? AND starts_at >= 90 ORDER BY starts_at LIMIT 3，参数恢复 north，预期 [(90,), (92,), (94,)]。同一城市内部可做时间范围扫描。不提供城市时，不同城市的时间分散在不同索引段，规划器可能扫描索引或选择其他策略；应重新看计划与实际读取量。
若查询没有使用索引，检查过滤字段是否包在表达式里、参数类型是否符合预期，以及数据规模和选择性。若运行更慢，别把 100 行实验的计时当基准；规划器路径证明了机制，没有证明大规模性能。
把 (city, starts_at) 及其服务的确切查询写进 design.md，同时记录每个新增索引都会增加写入成本。