索引与事务的系统原理

知识点地图#

• 知识类别：数据库系统原理的两个核心机制——索引（查询加速的 数据结构选择）与事务（正确性的系统设计）。本文是 590-DatabaseSystemPrinciple 速查表（索引复杂度一列、ACID 一张表）的展开深读。
• 解决什么问题：磁盘比内存慢五六个数量级，随机读尤其慢——索引与 WAL 是数据库对这一物理事实的两个回答：前者把随机读变少，后者把 随机写变少。理解这条主线，SQL 模块里散落的语法与参数全部有了着落。
• 什么时候用到：面试讲「为什么用 B+ 树不用红黑树/哈希/跳表」； 设计表结构时预判索引行为；理解崩溃恢复、主从复制为什么长那样； 学习 016-sql/017-mysql 深读篇之前先建立系统观。

与 016/017 模块的分工声明#

本文讲的是任何数据库管理系统都成立的通用原理与代价模型，采用 CS 课程 （数据库系统概念、CMU 15-445 一系）的视角：机制为什么被发明、代价怎么推导。 以下具体实现内容不在本文展开，由专篇负责：

• 聚簇索引与二级索引、回表的具体行为 → 017-mysql/220-ClusteredIndexSecondaryIndex
• 最左前缀、索引失效场景 → 017-mysql/230-CompositeIndexLeftmostPrefixPrinciple、 017-mysql/310-IndexFailureScene
• 脏读/不可重复读/幻读的逐级演示与 MySQL 实现 → 016-sql/380-DirtyReadNonRepeatablePhantom、 017-mysql/420-TransactionIsolationImplementation
• MVCC 版本链实现 → 016-sql/400-MVCC、017-mysql/430-MVCCPrinciple
• redo/undo/binlog 的具体格式与刷盘时机 → 017-mysql/500-RedoLog、510-UndoLog、520 系列

本文只保留让你能推导出这些行为的最小原理集。

真实场景：一条慢查询从 EXPLAIN 到加索引的推演#

后台报表接口突然从 50ms 变成 8 秒。DBA 给出的处理路径人人背得出： 看执行计划、发现全表扫描、加索引、变回 50ms。但「为什么加索引能快」 这一步，多数人止步于「索引像书的目录」。

用本文的代价模型把推演走完：表 1000 万行，页大小 16KB，每页约 100 行， 全表扫描读 10 万个页；二级索引 B+ 树高 3 层，定位到主键最多读 3 个页， 回表再读 1 个页——总 IO 从 100000 页降到 4 页，四个数量级的差距， 这才是慢查询变快的全部物理原因。至于「为什么是 3 层」， 第 2 节推导；「回表是什么」，第 3 节讲通用模型。

1. 前提：数据库构建在 OS 存储层次之上#

数据库不信任内存，一切以「页」为单元在磁盘与内存缓冲池之间搬运 （存储层次的代价金字塔见 120-StorageSystem，磁盘的物理寻道延迟见 240-DiskScheduling）：

内存（缓冲池 Buffer Pool）        磁盘（持久层）
  +--------------------+          +--------------------+
  | 页1 页2 页3 ...     |  <-读->   | 表数据文件（页组织）|
  | 命中率决定 IO 次数  |          | 索引文件（页组织）   |
  +--------------------+          +--------------------+

• 一次磁盘随机 IO 约 10ms 级，内存访问约 100ns 级，差 10 万倍；
• 因此数据库设计的头号目标不是省 CPU，是省 IO 次数，尤其是随机 IO；
• 「页」是磁盘与内存之间的最小搬运单位（MySQL InnoDB 默认 16KB， PostgreSQL 默认 8KB）。接下来的每个数据结构选择，都是围绕 「一棵树里找一个值要读几个页」展开的。

2. B+ 树：为「页 IO」定制的搜索树#

2.1 为什么不是二叉平衡树#

红黑树/AVL 树每个节点存 1 个键。1000 万行数据树高约 $\log_2(10^7) \approx 23$ 层， 最坏 23 次页 IO，每次 10ms——230ms 一次查询，不可用。

问题的本质：树的高度决定 IO 次数，而二叉树太瘦高。解法是让每个节点 （= 一个磁盘页）装尽可能多的键，把树压扁——这就是多路平衡搜索树。

2.2 扇出推导：三层数千万行#

B+ 树每个节点是一个页，非叶节点只存键与子指针。设主键 8 字节、 页内指针 6 字节，一个 16KB 页可容纳约 $16 \times 1024 / 14 \approx 1170$ 个键：

$1170^3 \approx 16 亿 > 2000 万$

三层即可索引 2000 万行以上——一次点查最多 3 次页 IO，根节点还常年 常驻缓冲池，实际磁盘 IO 常常只有 1-2 次。这就是 B+ 树战胜红黑树的完整论证： 不是「B+ 树更快」，是「B+ 树的高度对应磁盘 IO 次数，而扇出能把高度压到 3」。

2.3 为什么叶子还串成链表#

范围查询 WHERE id BETWEEN 100 AND 200：先定位到 id=100 的叶子， 然后沿叶子层的链表横向扫描——只需一次定位 + 顺序读。哈希表没有这个能力 （等值 O(1) 但范围退化为全表），跳表有类似的链但每个节点的键容量 受限于内存节点而非磁盘页。「叶子链表 + 高扇出」是 B+ 树对磁盘的两个适配， 对照 016-sql/430-ExecutionPlan 里的 range 扫描类型，原理即此。

3. 索引的通用代价模型：写放大与空间开销#

索引不是免费的，每加一个索引都要回答三个代价问题：

推论（这些推论在 016/017 的语法篇里都是「最佳实践」条目，此处给出物理原因）：

• 不要给低区分度列建普通索引：性别列只有 2 个值，一个值对应一半的行， 优化器算出「走索引还要回表一半的行，不如全表扫描」，索引形同虚设；
• 联合索引列顺序有讲究：查询条件必须能从最左列开始连续匹配， 否则这棵树对这次查询等价于不存在（细节见 017-mysql/230）；
• 主键要单调：随机主键（如 UUID）插入时落在树的各处，引发大量页分裂 与缓存失效；自增主键永远追加在最右叶子，写放大最小。

第三个场景（真实工程）：某同步任务批量导入 500 万行，空表加好 5 个索引后 导入耗时 40 分钟；先导数据后建索引只要 6 分钟——差值就是「边写边维护 5 棵 B+ 树」的写放大。MySQL 的 ALTER TABLE ... ADD INDEX 会用 排序法批量建树，比逐行维护快得多。

4. 事务与隔离性：并发正确性的通用模型#

4.1 为什么需要隔离级别：异常来自交错#

两个事务的读写操作在时间轴上交错时，可能出现三类经典异常 （每类的逐条演示见 016-sql/380）：

• 脏读：读到了别人尚未提交的数据——若对方回滚，你基于幻影做了决策；
• 不可重复读：同一事务内两次读同一行结果不同（中间被别人 UPDATE 并提交）；
• 幻读：同一事务内两次按相同条件查询，行数不同（别人 INSERT 了新行）。

注意三者与「读-写、写-写冲突」的对应关系：不可重复读是读-写冲突， 幻读是读-（写新行）冲突。SQL 标准的四个隔离级别就是「愿意付出多少 并发代价，换取消除哪几类冲突」的四个档位：

课程视角的要点：隔离级别不是产品特性而是调度正确性强度的档位， 任何支持并发的存储系统（包括 550-Redis、各种 NewSQL）都要回答同一道题， 只是实现手段不同（锁协议或 MVCC 的多版本思想，实现细节见 016-sql/390、400）。

4.2 并发下的转账实验（思维实验）#

账户 A=1000，B=1000。T1 从 A 转 200 到 B，T2 同时读两个账户算总资产：

• T2 在 T1 扣款后、加款前读 A=800、B=1000，报出「总资产 1800」—— 这是 RC 级别下合法的结果，账没丢，只是读到中间状态；
• Serializable 下 T2 必须等 T1 提交（或 T1 等 T2），读到的要么是转账前 2000 要么是转账后 2000。

哪个「对」取决于业务：报表允许中间态（RC 即可），审计不允许 （Serializable 或应用层对账）。没有默认正确，只有按业务选档位—— 这是教材教会而框架文档不讲的一句话。

5. WAL：为什么崩溃恢复必须先写日志#

5.1 问题的物理结构#

持久性要求「提交成功的数据断电不丢」。直接写数据文件为什么不行：

1. 一次事务改动散布在多个数据页（B+ 树节点、页头、空闲链表）， 全部刷盘是多次随机 IO；
2. 刷一半断电，数据页处于半新半旧状态——文件系统与磁盘都不保证 多页写入的原子性，库就坏了。

5.2 WAL 的解法：把随机写变顺序写#

Write-Ahead Logging（先写日志）：事务提交时只把一条描述性的日志记录 （「页 P 的位置 X 改为值 V」）追加到日志文件并 fsync——日志文件是 顺序追加的，一次顺序 IO 的代价几乎恒定；数据页的修改先留在内存 缓冲池里，之后由后台线程慢悠悠地批量刷盘（checkpoint）。

提交瞬间：  事务日志 fsync（顺序 IO，快）        <- 持久性在这一刻达成
稍后台：    脏页批量写回数据文件（随机 IO，慢）   <- 可以慢慢来，反正日志能重放

崩溃后重启：重放日志（redo 重做已提交未落盘的改动），未提交事务的改动 用 undo 回滚——只要日志在磁盘上，数据文件坏到什么程度都能恢复。 这就是 590 速查表里「原子性靠日志、持久性靠日志」两行的完整物理故事： 一条顺序追加的日志同时解决了原子性与持久性，代价是恢复时间与日志空间。

与 120 篇的联动：WAL 本质是把「随机小写」转化为「顺序大写」， 与 250-ZeroCopy 讲的「减少用户态/内核态拷贝」是同一类系统设计手法 ——为存储介质的物理特性改变写入模式。顺序写快于随机写也解释了 Kafka、LSM-Tree（LevelDB/RocksDB）等系统的核心设计。

常见陷阱与调试#

• 坑 1：把「索引存在」当成「索引被用」。 优化器按代价模型选路， 区分度低、回表代价超过全表扫描时它宁可全表扫。验证手段是执行计划 （016-sql/430），不是想当然。
• 坑 2：隔离级别选高就安全。 Serializable 消除异常的同时把并发度 打回串行，吞吐可能跌一个数量级；更常见的做法是 RC/RR + 业务层唯一约束 与乐观重试（016-sql/410-OptimisticPessimisticLock）。
• 坑 3：把 fsync 优化当成可有可无。 「每提交都 fsync 太慢，改成 每秒刷一次」——这是把持久性从「不丢已提交事务」降级为「最多丢 1 秒」。 这个取舍有名字（MySQL 的 innodb_flush_log_at_trx_commit）， 改之前必须明确业务能接受丢多少。
• 坑 4：推导树高时忽略非叶节点装不下。 键太长（如长字符串主键） 会让页内键数骤减、树变高。索引列选短小、基数高的列， 物理原因在此。

动手实践#

任务：不用任何数据库，用 Python 手写一个迷你存储引擎，体验 B+ 树 扇出与 WAL 两个机制的最小形态。

1. 实现一个「两层索引」：内存字典模拟叶子页（每页最多 4 个键）， 上层节点存每页的最大键；写入 20 个递增键，统计查找任一键需要 「读几个页」；
2. 给写入加一个最小 WAL：每次插入先把 (key, value) 追加写进 wal.txt 并 flush，然后才更新内存字典；写一个恢复函数， 启动时重放 wal.txt 重建字典；
3. 用随机 key 再测一次：观察「无序插入导致页分裂」在页计数上的表现。

提示：第 1 步不需要真 B+ 树，重点是感受「树高 x 扇出 = 容量」； 第 2 步的 flush 不能省，否则进程崩溃时日志还在用户态缓冲区； 第 3 步对比递增键与随机键的页数量差，就是自增主键优势的微缩版。

# minidb.py —— 两层页式索引 + 最小 WAL
import os, random

PAGE_SIZE = 4                      # 每页 4 键（真实引擎是千级，原理相同）

class MiniDB:
    def __init__(self, wal_path="wal.txt"):
        self.pages = []            # [[k1,k2,...], ...] 每个内层 list 是一页
        self.wal = open(wal_path, "a", encoding="utf-8")

    def put(self, key, val):       # 1) 先写日志  2) 再改数据
        self.wal.write(f"{key},{val}\n")
        self.wal.flush()           # 模拟 fsync：不 flush 崩溃时日志丢失
        for page in self.pages:    # 页内查找（真实引擎页内二分）
            if key in page:
                return
        if not self.pages or len(self.pages[-1]) >= PAGE_SIZE:
            self.pages.append([])  # 最后一页满 -> 新页（简化版页分裂）
        self.pages[-1].append(key)

    def get(self, key):            # 两层查找 = 根节点页 + 叶子页
        upper = [p[-1] for p in self.pages]   # 上层节点：每页最大键
        for i, hi in enumerate(upper):
            if key <= hi:
                return key in self.pages[i], 2   # 读 2 个页
        return False, 1                     # 只读了根页就判负

    @staticmethod
    def recover(wal_path="wal.txt"):
        db = MiniDB.__new__(MiniDB)          # 跳过 __init__ 里的追加句柄
        db.pages, db.wal = [], open(os.devnull, "a")
        if os.path.exists(wal_path):
            for line in open(wal_path, encoding="utf-8"):
                k, v = line.strip().split(",", 1)
                MiniDB.put(db, int(k), v)    # 重放日志重建状态
        return db

db = MiniDB()
for k in range(20): db.put(k, f"v{k}")       # 递增键：5 页，页不空洞
print(db.get(7), "页数:", len(db.pages))     # (True, 2) 页数 5

db2 = MiniDB.recover()
print("恢复后取 7:", db2.get(7)[0])          # True —— 日志重放成功

小结与下一步#

• 存储层次的物理事实（随机 IO 慢十万倍）推出数据库的两大设计： 索引用高扇出 B+ 树减少随机读，WAL 用顺序日志减少随机写；
• 隔离级别是并发正确性的档位选择，没有默认正确，只有按业务选型；
• 具体到 MySQL/PostgreSQL 的实现细节（聚簇、MVCC 版本链、redo 格式） 一律让位给 016-sql 与 017-mysql 的深读篇，本文给你的是推导它们的 最小原理集。

下一步：磁盘的物理寻道与调度见 240-DiskScheduling，零拷贝见 250-ZeroCopy；进入实现层先读 016-sql/420-Index 与 017-mysql/220 系列， 再按需深入 017-mysql/410-InnoDBSystemArchitecture。

参考与致谢#

• PostgreSQL 文档 Chapter 66「B-Tree Indexes」（https://www.postgresql.org/docs/current/btree.html ，PostgreSQL Licence，开放许可）
• CMU 15-445 Database Systems 课程公开讲义（https://15445.courses.cs.cmu.edu/ ，课程资料开放访问；本文仅参照其主题组织，文字全部自写）
• 场景素材：本仓库 021-cs-fundamentals/590-DatabaseSystemPrinciple 速查表 （索引复杂度表与 ACID 表）的展开深读