本页目录
数据库 I · 存储与索引
对标：CMU 15-445 前半 / Database Internals（Petrov）｜ 前置：csapp-02（存储层级）、os-03（磁盘、页缓存） 数据库是"把数据可靠、高效地存取"这件事做到极致的系统。你已是它的用户（Medusa 的
medusa-postgres、pgvector），这条线让你成为懂它内部的人。第一页讲最底层两件事：数据怎么在磁盘上按页组织，以及索引——为什么加一个索引能让查询从几秒变几毫秒，它底下的 B+ 树凭什么统治了数据库半个世纪。
学习层：一亿行数据，为什么只需要几次页访问？
具体谜题：索引的“快”到底从哪里来？
页大小为 8 KB，每个键和子指针占 16 字节；一张表有一亿行。顺序扫描需要碰到大量数据页，而 B+ 树的一个内部页大约能容纳 512 个分支。三层索引能否把定位成本压到根页、内部页、叶页三次 I/O？范围查询和等值查询是否应该用同一种索引？
最小心智模型：页、扇出与叶链
数据库把磁盘读写组织成页；B+ 树内部节点只存分隔键和子指针，所有记录入口集中在叶节点，叶节点按键排序并用兄弟指针相连。一次查找先沿分隔键下降，范围扫描到左端叶后沿链顺序读取。
形式机制与不变量
若有效扇出为 \(f\)，树高为 \(h\)，点查成本约为 \(O(h)=O(\log_f N)\) 页；范围查询还要加上结果覆盖的叶页。B+ 树的关键不变量是每个分隔键准确界定左右子树、叶链全局有序、除根外节点保持最小填充率。页式设计让 I/O 成本按页而非按行计量。
反例与失效边界
哈希索引的等值查找可近似常数时间，却不能提供范围与排序；低选择性谓词、严重偏斜或过期统计信息可能让顺序扫描比索引回表更便宜。B+ 树的分裂、合并和随机写入也有维护成本，不能把“有索引”直接等同于“必然更快”。
迁移任务：把页账本交给真实系统
在 L05 B+ 树实验中记录每次插入导致的分裂页与叶链变化，再用 `EXPLAIN ANALYZE` 对 Medusa 的一个过滤查询核对估算行数和实际页访问。P02-A 会继续把页式存储、索引和持久化约束组合起来；本层实验不替代 L05 的真实实现。
交互实验：B+ 树路径、范围扫描与页预算
无 JavaScript 时的静态读法：教学树的根分隔键为 30、60，三片叶子分别为 [10,20,30]、[40,50,60]、[70,80,90]。查找 73 的路径是“根→第三叶”，访问 2 页；范围 [35,75] 从第二叶的 40、50、60 扫到第三叶的 70，访问 2 片叶页并返回 4 个键。若页为 8192 B、每个键/指针 16 B，扇出约 512，三层容量约为 \(512^3\approx1.34\times10^8\) 个入口。
| 查询 | B+ 树路径 | 叶键 | 叶页数 |
|---|---|---|---|
| 等值 73 | 根→第三叶 | 70,80,90（候选 70–90） | 1 |
| 范围 [35,75] | 根→第二叶→叶链 | 40,50,60,70 | 2 |
| 顺序扫描 | 无索引路径 | 全表 | 所有数据页 |
1. 面向磁盘的设计：一切从"页"开始
数据库的第一性原理：数据比内存大、要持久化，所以面向磁盘设计（🔗 csapp-02 金字塔、os-03）。核心单位是页（page，通常 4~16 KB）——磁盘以块读写，数据库也以页为单位组织和缓存。
- 堆文件 + 页布局：表存成一堆页，每页里放若干元组（行），配一个槽目录（slot array）记录每行在页内的偏移——于是变长行、删除留空洞都能处理。行的定位符 = (页号, 槽号)。
- 缓冲池（buffer pool）：数据库自己管一块内存当磁盘的缓存（不完全信任 OS 页缓存，为了控制刷盘时机——这对 db-03 的恢复至关重要）。命中内存则快，未命中则从磁盘调页、满了按策略（LRU 变种如 LRU-K、Clock）换出。这本质上是 os-01/csapp-02 缓存思想在数据库里的重演，但数据库因为懂自己的访问模式，能做得比通用 OS 更聪明。
列存 vs 行存：传统行存（一行连续）适合 OLTP（事务，读写整行）；列存（一列连续）适合 OLAP（分析，只扫几列做聚合）——列存的连续性让压缩和向量化扫描起飞（🔗 perf 线）。"按查询模式选存储布局"是数据库性能的第一决策。
2. 索引：为什么快，代价是什么
没有索引，WHERE id = 42 要全表扫描（读每一页）。索引是一个额外的数据结构，把"列值 → 行位置"组织得便于查找——用空间和写入变慢，换查询变快。这个权衡是索引的全部本质：读多写少的列值得建索引，反之未必。
3. B+ 树：数据库索引之王【机理级】
为什么不是二叉搜索树、不是哈希表，而是 B+ 树？答案全在"面向磁盘"：
- 多路、矮胖：每个节点是一整页、含几百个键——于是几百万行的树只有 3~4 层。查一个键 = 3~4 次磁盘 I/O（且上层节点常驻缓冲池，实际更少）。二叉树高达几十层、每层一次 I/O，磁盘上完败。"用高扇出把树压矮"是对抗磁盘延迟的核心招式。
- 数据全在叶子、叶子串成链表：内部节点只存索引键导航，所有真实数据/指针在叶层，且叶子按序用指针连成链表——于是范围查询（
WHERE age BETWEEN 20 AND 30）超高效：定位起点后顺着叶链扫即可，不用回树。这是 B+ 树相比哈希索引的决定性优势（哈希只能等值查，不能范围、不能排序）。 - 自平衡：插入满了分裂、删除少了合并，永远保持矮而平衡——最坏情况仍 \(O(\log n)\)。
这就是 [实验 L05]：亲手实现 B+ 树的插入、分裂、范围扫描——数据库索引的心脏，写一遍就懂了 Postgres 的 CREATE INDEX 底下是什么。
哈希索引 vs B+ 树：哈希索引等值查 \(O(1)\) 更快，但不支持范围、排序、前缀——所以数据库默认索引几乎都是 B+ 树。LSM 树（LevelDB/RocksDB、写优化）是另一条路线：写入先进内存 + 顺序刷盘、后台合并——牺牲读、优化写，适合写密集场景（时序、日志）。B+ 树 vs LSM 是现代存储引擎的两大门派。
4. 索引的实战判断（Medusa 视角）
你天天在用索引，这里把决策讲透：
- 建在哪列：高频出现在
WHERE/JOIN/ORDER BY的列。Medusa 的articles.published_at（时间范围查）、events.entities（jsonb，用 GIN 索引）、article_id外键都是典型。 - 复合索引的顺序：
(a, b)索引能加速WHERE a=? AND b=?和WHERE a=?，但加速不了单独WHERE b=?（最左前缀原则——因为 B+ 树按 a 先排）。 - 别过度索引：每个索引都拖慢写入、占空间。索引是给读优化、向写收税。
- 向量索引（你在用的 pgvector）：高维向量的近邻搜索用的是 HNSW / IVF 等近似索引（🔗 adv-01 的 LSH、数学站高维几何）——精确近邻在高维不可行，这是"维度诅咒"的工程妥协。
方法论：看懂 EXPLAIN ANALYZE（查询计划）是数据库调优的核心技能——它告诉你查询有没有用上索引、是全表扫还是索引扫、每步花多少。db-02 会专门讲怎么读它。
5. 练习与要点
例 1（B+ 树扇出数感） 页 8 KB、键 + 指针共 16 字节 → 每节点约 500 路。三层能存多少行？\(500^3 \approx 1.25\) 亿。"三次 I/O 定位一亿行"——亲手算一次，你就懂了矮胖树的威力。
例 2（最左前缀） 建了 (city, age) 复合索引，判断 WHERE city='SH'、WHERE age=30、WHERE city='SH' AND age=30 分别能否用上索引——这个真实的调优陷阱，很多工程师栽过。
例 3（读你自己的计划） 在 Medusa 的只读连接上对一个慢查询跑 EXPLAIN ANALYZE，找出是不是缺索引（Seq Scan on 大表 = 危险信号）——把本页理论用到你正在运营的库。\(\blacksquare\)
▶ 实验 L05（B+ 树）：
labs/L05-bplustree/—— 插入/分裂/合并/范围扫描，可视化树的生长。跑在 Mac（Python）。
📋 大 Project P02（第一阶段）· 存储引擎
教师版作业说明书，不提供完整解。 P02 分三阶段随 db-01/02/03 展开，最终交付一个能跑 SQL 子集、带索引、带事务恢复的迷你关系数据库。
P02-A · 页式存储与索引
- 学习目标：把“表是一堆页、索引是一棵页树、缓冲池是数据库自己的缓存”落成代码。
- 教师提供：统一磁盘文件格式说明、
PageId/RID/Tuple接口骨架、随机插入/删除测试、百万行数据生成器、B+ 树可视化脚本。- 学生任务：① 页式堆文件 + 槽目录，支持变长行的 insert/delete/update/get；② 缓冲池，支持 pin/unpin、dirty page、LRU 或 Clock 淘汰；③ 持久化 B+ 树索引，支持等值查找、范围扫描、节点分裂与合并。
- 接口约束：页大小固定；所有磁盘访问必须经过缓冲池；RID 在行移动或删除后语义要清楚；B+ 树叶子必须按序串联。
- 验收测试：重启后数据与索引仍一致；百万行导入可完成；索引查询比全表扫快至少一个数量级；随机删除后范围扫描顺序正确。
- 评分重点：页格式 25%，缓冲池 25%，B+ 树正确性 35%，持久化与压力测试 15%。
- 延伸挑战：实现 LRU-K，并用一组顺序扫 + 热点查找混合负载解释它为什么优于朴素 LRU。
下一页：数据库 II——查询执行与优化：一条 SQL 怎么变成执行计划，优化器如何选出快的那条路。