概念篇

项目一：基于 BusTub 的数据库系统内核 —— 零基础超详细教程

零基础友好可运行代码逐行精讲

项目一：BusTub 数据库系统零基础教程（CMU 15-445）

写在最前面：这份教程怎么用

笔记写给谁看：完全没有写过代码的大一同学。我们从"Excel 成绩单"讲起，一路讲到你能在简历上写下"实现了一个教学型关系数据库内核"，并能扛住面试官的连环追问。

我们先说清楚三件事。

第一件事，这份教程不讲"怎么配环境怎么跑测试"，那些课程官网和仓库 README 写得很清楚。这份教程只干一件事：把这个项目背后所有的"为什么"讲透。因为面试官从来不问你环境怎么配，他只问"缓冲池为什么用 LRU-K 不用 LRU"。

第二件事，我们的讲法固定三步。第一步，先演示一个朴素做法是怎么翻车的。第二步，再给出真正的机制。第三步，用具体数字把机制钉死。比如我们会说"内存读一次约 100 纳秒，磁盘读一次约 10 毫秒，差了 10 万倍"，而不是干巴巴地说"磁盘比内存慢"。

第三件事，所有代码我们逐行讲。每一行注释是什么意思、为什么这么写，都会说清楚。你没写过代码没关系，跟着读就行。

第〇部分：数据库到底是什么

0.1 从一张 Excel 成绩单说起

假设你是班长，老师让你统计全班成绩。你最自然的做法是建一个 Excel 表：

第一行是表头：学号、姓名、数学、英语。
第二行：51、小明、135、128。
第三行：52、Alice、142、119。
第四行：53、Bob、98、140。

这就是一张"表"。在数据库的语言里，每一行叫一条记录（Record）或者叫元组（Tuple），每一列叫一个字段（Field）或者属性（Attribute）。整张表叫一个关系（Relation）——这也是"关系数据库"里"关系"两个字的来历，别想复杂了，它就是一张二维表。

一张 Excel 表，一个人用，完全没问题。问题出在"多个人同时用"。

0.2 朴素做法的翻车：多个程序同时改成绩

假设教务处、班主任、英语老师三个人，各自写了个小程序，都要改这份成绩文件。教务处的程序把 Alice 的数学从 142 改成 145（复核加分），同一瞬间英语老师的程序把 Alice 的英语从 119 改成 121。

如果这两个程序都是"先把整个文件读进内存、改完、再整个写回去"，那么谁先写回、谁后写回，就决定了最终结果。后写回的那个会把先写回的那个的修改整个覆盖掉。教务处的加分可能凭空消失。这在数据库里有个名字，叫丢失更新（Lost Update）。

再假设更惨的：程序写文件写到一半断电了，文件只写了一半，前半截是新数据后半截是旧数据，整张表直接报废。

所以朴素做法的结论是：直接拿一个文件当数据库，只要并发一上来、或者中途出故障，数据就会错、会丢、会坏。

0.3 数据库管理系统存在的理由

于是我们需要一个专门的软件，坐在"数据文件"和"各种应用程序"中间，统一管理所有的读写。这个软件就叫数据库管理系统（DBMS, Database Management System）。MySQL、PostgreSQL、Oracle，都是 DBMS。我们要做的 BusTub，也是一个迷你 DBMS。

DBMS 至少要替我们解决四个问题，而这四个问题恰好对应 BusTub 的四个 Project：

第一种问题：数据在磁盘上，程序要的是"快"。磁盘慢内存快，怎么让大部分读写都命中内存？这就是缓冲池（Buffer Pool），Project 1。

第二种问题：数据多了以后，"按学号查一个人"不能每次都把全表翻一遍。怎么让查找飞快？这就是索引，用 B+ 树（B+ Tree）来做，Project 2。

第三种问题：用户说一句"把数学 90 分以上的名单给我"，DBMS 得知道先读哪张表、再过滤、再输出。这就是查询执行（Query Execution），Project 3。

第四种问题：就是上面说的并发翻车。多个人同时改数据，怎么保证不错不乱？这就是并发控制（Concurrency Control），Project 4。

你看，这门课的结构不是随便排的，它就是"一个 DBMS 最少必须有的四块积木"。

0.4 SQL 是什么

用户总不能直接调用 C++ 函数来查数据吧，所以 DBMS 对外提供一门声明式的语言，叫结构化查询语言（SQL, Structured Query Language）。"声明式"的意思是：你只说"我要什么"，不说"怎么拿"。怎么拿，是 DBMS 自己的事（这正是 Project 3 的活）。

我们用学生表 scores（学号 sid、姓名 name、数学 math、英语 english）把最常用的四类语句过一遍。每条后面我都写"这行话在让数据库干什么"。

第一条，查询：

SQL

SELECT name, math FROM scores WHERE math >= 90;

这行话在让数据库：把 scores 表扫一遍（或者走索引），凡是 math 大于等于 90 的行，只把 name 和 math 两列挑出来返回。比如会返回"小明 135"和"Alice 142"，Bob 数学 98 也会返回。

第二条，插入：

SQL

INSERT INTO scores VALUES (54, 'Carol', 120, 130);

这行话在让数据库：往 scores 表末尾加一行新记录，四个字段依次是 54、Carol、120、130。

第三条，更新：

SQL

UPDATE scores SET math = 145 WHERE name = 'Alice';

这行话在让数据库：找到 name 等于 Alice 的那一行，把她的 math 改成 145，其他列不动。注意 WHERE 是关键，不写 WHERE 会把全表所有人的数学都改成 145，这是新手最容易闯的祸。

第四条，删除：

SQL

DELETE FROM scores WHERE sid = 53;

这行话在让数据库：把学号 53（也就是 Bob）那一整行删掉。

还有一个稍高级但面试常问的：连接（JOIN）。假设还有一张表 students（学号 sid、班级 class），我们想查"每个学生的数学分和他所在的班级"。数据分散在两张表里，靠学号对上：

SQL

SELECT s.name, s.math, t.class
FROM scores s JOIN students t ON s.sid = t.sid;

这行话在让数据库：拿 scores 里的每一行，去 students 里找学号相同的那一行，把两行拼成一行再返回。小明的学号 51 在两张表里都有，于是拼出"小明、135、3班"。至于"怎么找"——是逐行比对还是用索引——那是 Project 3 里 Join 算子的事，写 SQL 的人不用管。

到这里，你对"数据库是干嘛的"已经有体感了：它就是一个帮你管二维表、并且保证多人同时用也不出错的软件。接下来我们先补工具——C++。

第一部分：C++ 语法从零速成（只讲 BusTub 用得上的）

BusTub 是用 C++ 写的。C++ 这门语言很大，但项目里反复用到的其实就那七八个东西。我们一个一个来，每个都配生活例子。

1.1 变量与类型

变量就是一个贴了名字的盒子，盒子里装数据。类型（Type）规定了盒子能装什么、占多大地方。

C++

int math = 135;        // 定义一个整型变量 math，里面放 135
double pi = 3.14159;   // 定义一个双精度浮点数 pi
char grade = 'A';      // 定义一个字符 grade
bool passed = true;    // 定义一个布尔值，只有 true/false 两种可能

逐行说。第一行：int 是类型名，表示"整数"；math 是我们给盒子起的名字；= 135 是往盒子里放初始值。分号是 C++ 的"句号"，每句话说完都要点一个。第二行 double 装小数，比 float 精度高一倍，所以叫 double（双精度）。第三行 char 只装一个字符，注意用单引号。第四行 bool 只有真和假，后面讲锁和条件判断时到处是它。

还有一类会自动推导的写法，项目里满天飞：

C++

auto it = page_table.find(page_id);  // auto 让编译器自己猜 it 的类型

auto 的意思是"类型太长我懒得写，编译器你看着办"。右边 find 返回什么类型，it 就是什么类型。这不是偷懒，是因为 C++ 里迭代器的类型名长得像咒语，比如 std::unordered_map<int, Frame*>::iterator，没人想手写。

1.2 指针和引用：门牌号 vs 房子本身

这是零基础同学的第一道坎，我们慢慢过。

每个变量都住在内存里，内存就像一条街，每个房子有门牌号（地址）。指针（Pointer）就是一个专门存"门牌号"的变量——它存的不是房子本身，而是"房子在哪"。

C++

int math = 135;      // 一个普通的整数房子，里面住 135
int* p = &math;      // p 是一个指针，里面存 math 的门牌号
                     // & 是"取地址"，意思是"把 math 的门牌号给我"
*p = 140;            // * 是"顺着门牌号找到房子"，把里面的值改成 140
                     // 现在 math 本人也变成 140 了

逐行说。第二行 int* 读作"指向 int 的指针"，&math 拿到 math 的地址。第三行 *p 叫解引用（Dereference），意思是"别给我看门牌号了，带我去那个房子"，然后对房子里的值动手。所以改 *p 就是改 math。

为什么要这么绕？因为"共享"。比如缓冲池里，哈希表存的是某个帧（Frame）的指针，执行器拿到的也是同一个帧的指针——大家手里都是同一个门牌号，谁改了房子里住的人，所有人立刻看到新值。如果不用指针，每个人复印一份房子，那就各改各的，数据全乱。

引用（Reference）是指针的"文明版"，它是给变量起的外号：

C++

int math = 135;
int& r = math;   // r 是 math 的引用，也就是 math 的别名
r = 140;         // 改 r 就是改 math，不需要 * 也不需要 &

引用定义时必须立刻绑定一个变量，而且一辈子不能改绑别人。函数参数用引用传递（void f(int& x)），就能在函数里直接改外面的变量，又不用像指针那样写一堆 *。BusTub 里函数签名大量是 Page* （返回指针）和 const std::string& name（常量引用，只读借用，不复制），混个眼熟就行。

1.3 类（class）和对象（object）

类（Class）是图纸，对象（Object）是按图纸盖出来的具体房子。

C++

class Student {
 public:                       // public 表示下面这些东西谁都能用
  int sid;                     // 成员变量：学号
  int math;                    // 成员变量：数学分
  void Print() {               // 成员函数：打印自己
    printf("sid=%d math=%d\n", sid, math);
  }
};

Student xiaoming;   // 按图纸盖一个对象，叫 xiaoming
xiaoming.sid = 51;  // 用 . 访问成员：把小明的学号设为 51
xiaoming.Print();   // 调用成员函数

class Student 说"学生这种事物有学号、有分数、还会自我打印"。Student xiaoming 造出一个具体的对象。对象之间相互独立：你再 Student alice; 造一个 Alice，她的 math 和小明的互不干扰。

BusTub 里一切皆是类：BufferPoolManager 是一个类（缓冲池大管家），Page 是一个类（一页数据），LRUKReplacer 是一个类（替换算法）。整个 Project 1 说白了就是你把 BufferPoolManager 这个类的几个成员函数填出来。

1.4 继承（Inheritance）

继承就是"子类自动拥有父类的一切，还能加自己的东西"。

C++

class Animal {
 public:
  std::string name;   // 所有动物都有名字
};

class Dog : public Animal {   // Dog 继承 Animal，": public" 是固定写法
 public:
  void Bark() { printf("wang\n"); }  // 狗额外会叫
};

Dog d;
d.name = "旺财";   // name 是从 Animal 继承来的，直接用
d.Bark();          // Bark 是 Dog 自己加的

class Dog : public Animal 读作"Dog 是一种 Animal"。狗自动有了 name，又多了 Bark()。

1.5 多态和虚函数（virtual）：父类指针调子类方法

这是 C++ 里最重要的一个机制，也是 BusTub 的骨架设计，必须讲透。

先看问题。假设动物园里有狗有猫，都会叫，但叫声不同。我们想写一段统一代码："让每只动物叫一声"，而不想给狗写一套、给猫写一套。

C++

class Animal {
 public:
  virtual void Speak() { printf("...\n"); }  // virtual：允许子类覆盖我
  virtual ~Animal() = default;               // 虚析构，父类指针删除子类对象时必须
};

class Dog : public Animal {
 public:
  void Speak() override { printf("wang\n"); }  // override：我是故意覆盖父类的
};

class Cat : public Animal {
 public:
  void Speak() override { printf("miao\n"); }
};

现在见证奇迹：

C++

Animal* a1 = new Dog();   // 父类指针 a1，实际指向一只狗
Animal* a2 = new Cat();   // 父类指针 a2，实际指向一只猫
a1->Speak();              // 输出 wang！指针是 Animal*，却调到了 Dog 的版本
a2->Speak();              // 输出 miao！

-> 是"指针版"的 .，a1->Speak() 等价于 (*a1).Speak()。关键在于：虽然 a1 的静态类型是"Animal 的指针"，但因为 Speak 是虚函数（Virtual Function），程序运行时会去看指针真正指向的对象是什么品种，然后调用那个品种的 Speak。这叫多态（Polymorphism）——同一个函数调用，不同的对象有不同的表现。

BusTub 里到处都是这个套路。Project 3 里所有执行算子（SeqScan、Filter、Join）都继承自一个抽象父类 AbstractExecutor，父类规定"每个算子必须有 Next() 方法"，调度器拿着 AbstractExecutor* 指针挨个调 Next()，根本不用关心底下具体是扫描还是连接。这就是第五部分"火山模型"的代码地基。删掉 virtual 试试？那调用的永远是父类的空实现，程序直接废掉——所以 virtual 不是装饰，是命门。

1.6 模板（template）

模板（Template）就是"一份代码，适配所有类型"。

问题引入：你想写一个函数 Max 求两个数的较大者。给 int 写一份，给 double 又得复制一份，太蠢。模板让你写一份：

C++

template <typename T>   // 声明：下面这份代码里的 T 是个占位类型
T Max(T a, T b) {
  return a > b ? a : b;  // 三元运算符：a>b 成立就取 a，否则取 b
}

int m = Max(3, 5);          // T 自动变成 int
double d = Max(1.5, 2.7);   // T 自动变成 double

template <typename T> 相当于说"这份代码有个类型参数 T，用的时候再告诉我 T 是什么"。编译器看到 Max(3, 5) 就自动生成一份 int 版的 Max。

STL（Standard Template Library，标准模板库）里所有容器都是模板：std::vector<int> 是装 int 的动态数组，std::unordered_map<int, Page*> 是"键为 int、值为 Page 指针"的哈希表。所以你在 BusTub 里看到的尖括号 <>，就是在给模板"填类型参数"。

1.7 智能指针：为什么不能用裸 new

先看裸 new 的翻车现场：

C++

void F() {
  int* p = new int(135);  // new：在堆上申请一块内存，返回指针
  // ... 中间干了好多事，如果这里抛异常或者直接 return ...
  delete p;               // delete：释放这块内存。忘了写？内存泄漏！
}

new 申请的内存，必须手动 delete 还回去，否则这块内存就永远占着——这叫内存泄漏（Memory Leak）。程序跑久了内存被慢慢吃光。问题在于"忘记"太容易了：函数中间提前 return、抛异常，都会跳过 delete。

智能指针（Smart Pointer）的思路是：把裸指针包在一个小对象里，对象死的时候（离开作用域）自动帮你 delete。这叫 RAII（Resource Acquisition Is Initialization，资源获取即初始化）——把"释放资源"绑在"对象生命周期"上，想忘都忘不了。

第一种：std::unique_ptr，独占式。

C++

{
  auto p = std::make_unique<int>(135);  // p 独占这块内存
  // 出了这个大括号，p 自动销毁，内存自动释放，不用 delete
}

unique_ptr 的意思是"这块内存只有一个主人"。它不能被复制（不能有两个主人），但可以"移交"所有权（std::move）。

第二种：std::shared_ptr，共享式。

C++

auto a = std::make_shared<Page>();  // 内部有个引用计数，现在是 1
auto b = a;                         // b 也指向同一个 Page，计数变 2
// a 销毁，计数变 1；b 也销毁，计数变 0，内存这才释放

shared_ptr 内部记着一个数："现在有几个人指着这块内存"。每多一个 shared_ptr 指向它，计数加一；每销毁一个，减一；减到零，没人用了，自动释放。

经验法则：默认用 unique_ptr，确实需要多方共享所有权才用 shared_ptr。BusTub 的测试代码里大量 std::make_unique<BufferPoolManager>(...)，你混个脸熟即可。面试如果问"为什么不直接 new"，标准答案就一句：手动 delete 容易因异常或提前 return 被跳过造成泄漏，智能指针用 RAII 把释放绑定到作用域上，异常安全。

1.8 STL 容器重点：哈希表 unordered_map

容器就是"装一堆同类型东西的盒子"。先一句话带过三种常用的：

第一种，std::vector：动态数组。像一根可以自动加长的糖葫芦，按下标访问飞快，v[3] 直接拿到第 4 个。BusTub 里 free_list_（空闲帧列表）就用 std::list（链表，和 vector 类似但擅长头尾插删）。

第二种，std::unordered_map：哈希表（Hash Table），本项目的绝对主角，重点讲。

第三种，std::mutex 不是容器，是锁，1.9 单独讲。

现在讲哈希表。生活类比：查字典。如果一本《新华字典》没有拼音索引，你查"鲱"字只能从第一页翻到最后一页，这是 O(n)——n 是总页数，意思是"查找时间和数据量成正比"。但有了拼音索引，你按 fei 直接跳到那一页，不管字典多厚，差不多都是一步到位，这就是 O(1)——常数时间，和数据量无关。

哈希表就是给数据做的"拼音索引"。它内部有一个数组（很多个桶，Bucket），和一个哈希函数（Hash Function）。流程是：把键（Key）丢进哈希函数，算出一个数字，对桶数取余，得到"该放第几号桶"。

具体到 BusTub：page_table_ 就是一个 std::unordered_map<page_id_t, frame_id_t>。它回答的问题是："第 10086 号页（Page）现在住在内存的哪个帧（Frame）里？"查询时，哈希函数把 10086 一算，直接定位到存着答案的桶，O(1) 拿到帧号。如果没有它，每次访问页都得把几百个帧挨个问一遍"你是不是 10086 号页"，缓冲池就失去意义了。

冲突（Collision）怎么办？两个不同的页号，哈希函数算出同一个桶号，就像"飞"和"菲"都查 fei。教科书的解法叫链地址法：每个桶里挂一条小链表，同桶的键排排坐，找到桶后再在链表里比对真正的键。只要哈希函数够均匀，链表平均长度接近 1，查找仍然是 O(1)。unordered_map 内部就是这么干的，你不用自己写。

用法就三行：

C++

std::unordered_map<page_id_t, frame_id_t> page_table_;  // 定义
page_table_[10086] = 3;        // 插入/更新：10086 号页住 3 号帧
auto it = page_table_.find(10086);   // 查找：返回一个"迭代器"
if (it != page_table_.end()) {       // end() 是"没找到"的哨兵
  frame_id_t f = it->second;         // it->first 是键，it->second 是值
  page_table_.erase(it);             // 删除这一条
}

find 返回的迭代器（Iterator）你可以理解成"指向表里某一根手指"。如果手指指向 end()（表外），说明没找到；找到了，it->first 是键、it->second 是值。

1.9 互斥锁（mutex）

最后一块拼图。回到 0.2 的翻车：两个线程同时改 page_table_ 会发生什么？哈希表内部要挪动链表，两个线程同时挪，链表会被拧成麻花，程序直接崩溃或者丢数据。

互斥锁（Mutex，Mutual Exclusion，互斥）的规则像厕所门锁：谁进去谁锁门，出来后开锁，别人才能进。同一时间只有一个线程能持有锁。

C++

std::mutex latch;            // 定义一把锁

void Worker() {
  latch.lock();              // 抢锁，抢不到就排队等着
  page_table_[1] = 2;        // 临界区：只有持锁者能执行这里
  latch.unlock();            // 放锁
}

但手动 lock/unlock 有个和裸 new 一样的毛病：中间提前 return 就忘了 unlock，锁永远不放，其他线程全部饿死（死锁的一种）。所以还是 RAII：

C++

void Worker() {
  std::scoped_lock lk{latch};   // 构造时自动 lock
  page_table_[1] = 2;           // 安全地改
}                               // 出了作用域，lk 自动销毁，自动 unlock

std::scoped_lock（老代码里叫 std::lock_guard）一出生就抢锁，一死亡就放锁，绝无遗漏。BusTub 的 BufferPoolManager 里每个公开函数第一行几乎都是 std::scoped_lock latch(latch_);——整个缓冲池一把大锁，简单粗暴但正确。性能优化的余地面试可以聊，先说对。

第一部分到此结束。你现在拥有读 BusTub 代码所需的全部 C++ 知识：类型、指针引用、类、继承、虚函数多态、模板、智能指针、哈希表、锁。下面我们正式进入 BusTub。

第二部分：BusTub 是什么

2.1 来历

BusTub 是卡内基梅隆大学（CMU, Carnegie Mellon University）著名数据库课程 15-445/645（Database Systems）的配套教学项目，由 Andy Pavlo 教授主讲——他的公开课录像在网上免费，是数据库圈最有名的入门课，没有之一。

BusTub 本身是一个教学用的小型关系数据库管理系统。注意"教学用"三个字：它不能真的上线给淘宝用，但它的架构是"真数据库的等比缩小模型"——缓冲池、B+ 树索引、火山执行引擎、两阶段锁，这些部件在 MySQL InnoDB 和 PostgreSQL 里都有对应物，只是工业界的版本大了三个数量级。吃透 BusTub，等于把数据库内核的骨架亲手摸了一遍。

2.2 四个 Project 分别做什么

Project 0 是热身，写一个小 C++ 程序（近几年是一个并发字典树），目的是让你熟悉 C++ 和项目的提交、评测流程。

Project 1：缓冲池（Buffer Pool）。实现 LRU-K 替换算法、缓冲池管理器。管"内存和磁盘之间怎么搬数据"。第三部分细讲。

Project 2：B+ 树索引（B+ Tree Index）。实现一棵支持并发存取的磁盘友好 B+ 树。管"怎么快速定位一条记录"。第四部分细讲。

Project 3：查询执行（Query Execution）。实现一堆执行算子：顺序扫描、索引扫描、过滤、嵌套循环连接、聚合、TopN 排序等。管"一句 SQL 怎么真正跑出结果"。第五部分细讲。

Project 4：并发控制（Concurrency Control）。实现锁管理器和死锁检测，让多个事务同时跑也不出错。管"并发安全"。第六部分细讲。

四个 Project 层层递进：先会搬数据（P1），再会找数据（P2），再会算数据（P3），最后会多人一起用（P4）。做完你就拥有了一个能跑简单 SQL 的迷你数据库。

2.3 为什么在简历上值钱

一句话：岗位对口。国内大厂的数据库内核团队（做分布式数据库、存储引擎、云原生数据库的那些组），面试考察的核心知识点——缓冲池替换算法、B+ 树、LSM 树、执行器、事务与锁——恰好就是 15-445 四个 Project 的内容。存储岗也一样，因为存储系统（文件系统、KV 引擎）和数据库内核共享同一套底层知识：页式管理、缓存替换、索引结构、并发控制。

面试官看到一个本科生独立完成过 BusTub，他的第一反应是：这个人知道数据库内部长什么样，不是只会调 pymysql。而你能不能拿到 offer，取决于你能不能答出他接下来的追问——比如"LRU-K 的 K 是干嘛的""B+ 树为什么比 B 树好"。这份教程的第七部分，就把这些追问和答案要点全部列给你。

第三部分：Project 1 缓冲池（Buffer Pool）

3.1 先讲清楚：内存和磁盘差多少

我们的老规矩，先看朴素做法：不用缓冲池，数据库每次要数据都直接读磁盘，会怎样？

看数字。内存（DRAM）读一次大约 100 纳秒。机械硬盘（HDD）随机读一次大约 10 毫秒。10 毫秒等于 10,000,000 纳秒——差了 10 万倍。就算是固态硬盘（SSD），随机读一次也要约 100 微秒，还是比内存慢 1000 倍。

10 万倍是什么概念？打个比方：你在书桌前写作业（CPU 在计算），笔就在手边（数据在内存），伸手 1 秒拿到；如果笔在另一个城市的仓库里（数据在磁盘），快递要 3 天。如果每条 SQL 都要等"快递"，你的数据库一秒只能响应几十次查询，抖音那种每秒几十万次点赞的系统早就崩了。

所以结论一出来：数据库必须尽量把"热数据"放在内存里，磁盘读写能省一次是一次。这就是缓冲池存在的全部理由。

3.2 页（Page）和帧（Frame）：搬运的最小单位

下一个问题：内存和磁盘之间，数据按什么粒度搬？一个字节一个字节搬？那搬一次的开销（磁盘寻道）远大于搬运本身，太亏。所以数据库规定：搬运的最小单位是页（Page），一页固定大小，BusTub 里默认 4096 字节（4KB），MySQL InnoDB 默认 16KB。

为什么这么定？因为磁盘（尤其机械盘）的特点是"定位慢、连续读快"。读 1 字节和读 4KB，寻道时间一样，后者等于白送 4000 倍的数据。所以干脆一次搬一整页，赌你接下来还会用到这页里的其他数据——这叫空间局部性，通常赌得赢。

对应地，内存里的缓冲池被切成一个个同样大小的槽位，每个槽位叫一帧（Frame）。页是磁盘上的单位，帧是内存里的槽位，两者大小相同，所以一页恰好放进一帧。把磁盘上第 10086 页读进内存第 3 帧，这个动作叫"把页装入帧"。

类比：磁盘是城市图书馆的总书库（容量巨大但远），缓冲池是你宿舍的书桌（容量小但随手可得），页是一本本书，帧是桌面上一个个固定的格子，每个格子恰好放一本书。

3.3 缓冲池管理器要回答的四个问题

BufferPoolManager（缓冲池管理器）就是书桌管理员。它对外提供几个操作，背后要回答四个问题：

第一个问题：要用的页在不在内存里？用 1.8 讲的哈希表 page_table_ 回答：查一下 page_table_ 里有没有这个页号，O(1) 出答案。

第二个问题：不在的话，放哪个帧？优先用空闲帧，空闲帧记录在 free_list_（一个链表）里，从链表中摘一个就行。

第三个问题：空闲帧用完了怎么办？这时要"赶人"——从书桌上的书里挑一本最不值得留的，放回书架，腾出格子。挑哪本？这就是替换算法（Replacement Algorithm）的事，下一节讲 LRU-K。

第四个问题：被赶的页如果改过了怎么办？比如小明把数学 135 改成了 145，这个改动目前只在内存的帧里，磁盘上还是旧值。如果直接把帧让给别人，改动就丢了。所以每个帧要记一个脏标记（Dirty Flag）：这页在内存里被写过没有？被写过（脏页）的，赶人之前必须先写回磁盘；没写过的（干净页），直接扔掉就行，反正磁盘上还有一模一样的副本。

还有一对操作必须讲：pin 和 unpin。pin（钉住）的意思是"我正在用这页，谁也不许把它赶走"。每个帧记一个计数器 pin_count_，有人用就加一，用完 unpin 减一。计数大于零的页是不可替换的——替换算法再讨厌它也不能动它。为什么必须这样？想象执行器正在读某页第 300 字节到第 400 字节的内容，读到一半缓冲池把这页赶走了、装进了别的页，执行器手里那个指针就变成了"指向别人家的指针"，读到的是乱码。pin 就是防止这种灾难。

3.4 LRU-K 替换算法

先讲纯 LRU 再说 K。

LRU（Least Recently Used，最近最少使用）的直觉：书桌上放不下的书，把"最久没碰过的"放回书架。背后的赌注是：最近用过的书，接下来大概率还会用（时间局部性）；最久没用的，大概率也不用了。

实现上，LRU 就是维护一条"使用顺序"的链表：每访问一次某页，就把它挪到链表头部；要赶人时，从链表尾部拿一个——尾部就是最久没用的。

纯 LRU 有个著名缺陷：扫描污染（Scan Pollution）。假设教务处在年底跑一次"统计全校数学平均分"，这个查询要顺序扫过整个成绩表，100 万行、几千页，每一页只读一次、以后再也不读。这些"一次性页"涌入缓冲池，每一页都会把链表尾部的一本"常用书"挤回书架——比如小红书的评论热帖页、你天天查的那几页索引。扫描结束后，缓冲池里堆满了再也不会被读的垃圾页，而真正的热页全被赶走了，之后所有查询都开始疯狂读磁盘。一次大扫描，把缓存"洗"成了废池。

LRU-K（Least Recently Used K，最近第 K 次使用）就是为了治这个病。它的思路：不看"最近一次使用是什么时候"，改看"最近第 K 次使用是什么时候"。BusTub 里 K 通常取 2，我们就按 K=2 讲。

每个帧维护它最近 K 次的访问时间戳。要赶人时，比的是"倒数第 K 次访问距今多久"（这叫 backward K-distance）：距今越久的越该被赶走。还没被访问够 K 次的页（比如那个一次性扫描页，只被访问了 1 次），它的倒数第 K 次时间视为"无穷久远"，排第一优先被赶。

效果立竿见影：一次性扫描页只被访问一次，backward K-distance 是无穷大，每次赶人第一个赶的就是它自己人——扫描页在缓冲池里互相挤兑，而真正的热页（被访问过 2 次以上的）稳坐钓鱼台。书桌比喻版：LRU 是"最久没碰的书回书架"，LRU-2 是"只翻过一次的生面孔优先回书架，翻过两次以上的常客留下"。生面孔再多也挤不走常客，这就是 LRU-K 防扫描污染的原理。

BusTub 里 LRUKReplacer 要实现的核心接口有三个：Evict()（选一个受害者帧返回）、RecordAccess(frame_id)（记录某帧被访问了一次）、SetEvictable(frame_id, bool)（设置某帧可不可以被赶——pin 住的帧就是不可赶的）。

3.5 BufferPoolManager 核心代码骨架逐行讲

下面是一份简化后的骨架（伪真混合，突出结构），我们逐行过。

C++

class BufferPoolManager {
 private:
  size_t num_frames_;      // 缓冲池一共多少帧，比如 100
  Page *pages_;            // 所有帧排成的数组，pages_[3] 就是 3 号帧
  std::unordered_map<page_id_t, frame_id_t> page_table_;  // 页号 -> 帧号
  std::list<frame_id_t> free_list_;   // 空闲帧链表
  LRUKReplacer *replacer_;            // 替换算法，上一节那个
  DiskManager *disk_manager_;         // 负责真正读写磁盘的工具人
  std::mutex latch_;                  // 保护上面所有东西的大锁
};

逐行讲。num_frames_ 记录书桌有多少格子。pages_ 是帧数组本体，每一帧本质是一块 4KB 内存外加几个记账字段（页号、脏标记、pin 计数）。page_table_ 是哈希表，回答"页住在哪帧"。free_list_ 是空闲格子清单。replacer_ 是赶人策略。disk_manager_ 干脏活：真正调操作系统读盘写盘。latch_ 是那把大锁。

再看"取一页进来"的完整流程（FetchPage 的骨架）：

C++

Page *FetchPage(page_id_t page_id) {
  std::scoped_lock latch(latch_);          // 进门先抢锁，全程独占缓冲池

  // 情况一：页已经在内存里
  if (page_table_.count(page_id) > 0) {    // count 返回 1 表示哈希表里有
    frame_id_t f = page_table_[page_id];   // 查到帧号
    pages_[f].pin_count_++;                // pin 计数加一：我在用，别赶它
    replacer_->RecordAccess(f);            // 告诉 LRU-K：这帧又被访问了
    replacer_->SetEvictable(f, false);     // pin 住的帧设为不可替换
    return &pages_[f];                     // 把帧的指针交给调用者
  }

  // 情况二：不在内存，得找个空帧装它
  frame_id_t f;
  if (!free_list_.empty()) {               // 先问空闲链表
    f = free_list_.front();                // 拿链表头一个空闲帧
    free_list_.pop_front();                // 从清单里划掉
  } else if (replacer_->Evict(&f)) {       // 没空闲的，让 LRU-K 挑个受害者
    if (pages_[f].is_dirty_) {             // 受害者是脏页？
      disk_manager_->WritePage(pages_[f].page_id_, pages_[f].GetData());
                                           // 先写回磁盘，保住修改
    }
    page_table_.erase(pages_[f].page_id_); // 哈希表里删掉旧住户的登记
  } else {
    return nullptr;                        // 所有帧都被 pin 住，没辙，失败
  }

  // 把新页读进腾出来的帧
  disk_manager_->ReadPage(page_id, pages_[f].GetData());  // 从磁盘读 4KB
  pages_[f].page_id_ = page_id;            // 帧登记新住户的页号
  pages_[f].pin_count_ = 1;                // 新页一来就被调用者用着，pin=1
  pages_[f].is_dirty_ = false;             // 刚读进来，和磁盘一致，是干净的
  page_table_[page_id] = f;                // 哈希表登记：此页住此帧
  replacer_->RecordAccess(f);              // 记录一次访问
  replacer_->SetEvictable(f, false);
  return &pages_[f];
}

这段代码就是 Project 1 的灵魂。对照着看，逻辑分三大块：命中（直接在哈希表查到，pin 加一，走人）、未命中但有空帧（直接用）、未命中且无空帧（LRU-K 赶人，脏页先写回，再装入新页）。你真正写的时候还要处理 NewPage（分配一个全新的页）、DeletePage（删页）、UnpinPage（用完放人，pin 减一，减到零就恢复可替换状态）这几个函数，但骨架思想一模一样：哈希表查位置、链表管空闲、LRU-K 管赶人、脏标记管写回、pin 计数管安全。

Project 1 完成后，你向面试官可以这样概括：我实现了一个页式缓冲池，用哈希表做到 O(1) 页定位，用 LRU-K 替换算法抵抗顺序扫描造成的缓存污染，用脏页标记加 pin 计数保证数据一致性和并发安全。这一句话里每个词，你现在都知道是什么意思了。

第四部分：Project 2 B+ 树索引

4.1 朴素做法：按学号查成绩，全表扫一遍有多慢

需求：教务系统要查"学号 1234567 的数学成绩"。

朴素做法：打开成绩表，从第一行开始，一行一行看学号对不对，不对就下一行。这叫全表扫描（Sequential Scan / Full Table Scan）。表里有 100 万行，平均要翻 50 万行才能找到；如果这人不存在，得把 100 万行全翻完才能说"没有"。

换算成时间：100 万行假如占 1 万个页（每页 100 行），全在磁盘上，全表扫一遍就是 1 万次磁盘 I/O。机械盘每次约 10 毫秒，合计 100 秒——查一个人等一分半钟。抖音每秒几十万次点赞写入，小红书每秒几万次评论查询，全表扫描在这类场景等于死刑。

所以需要索引（Index）：一本"目录"，让你不用翻全表就能定位。

4.2 哈希索引为什么不够

学了 1.8 的哈希表，你的第一反应可能是：拿学号做键、行位置做值，建个哈希索引，O(1) 查到，搞定？

对"学号等于 1234567"这种等值查询，哈希索引确实是王者，MySQL 内部某些场景也在用。但看另一个需求："数学 90 到 100 分的有哪些人？"——范围查询（Range Query）。哈希函数的设计目标恰恰是把相近的键打散到不同的桶里（90、91、92 会被扔到毫不相干的桶），所以哈希表完全不知道"90 到 100 之间有谁"，只能退化成全表扫描。

再换一个需求："按分数从高到低输出前 10 名"。排序（ORDER BY）同样是哈希表的盲区——桶里的数据没有任何顺序可言。

结论：哈希索引只支持"等于"，不支持"大于小于之间"和"排序"。而业务里范围查询和排序遍地都是（DeepSeek 的历史对话列表按时间倒序、小红书评论按热度排序），所以数据库的主力索引必须是一种"有序"的数据结构。

4.3 从二分查找到二叉搜索树

有序数据怎么查得快？第一个答案是二分查找（Binary Search）：一排按学号排好的卡片，找 51 号，先看正中间那张，是 74 号——51 比 74 小，扔掉右半边；再看剩下那半的中间……每看一眼，范围砍一半。100 万条数据，最多看 20 次（2 的 20 次方约等于 100 万）。O(log n)，比 O(n) 的 50 万次强了 2 万多倍。

但二分查找要求数据连续存放且有序，插入一个新学生怎么办？数组中间插一个元素，后面 50 万个元素全得往后挪一位，插入变成 O(n)。所以数据库要的是"查找快、插入删除也快"的有序结构——树。

二叉搜索树（BST, Binary Search Tree）：每个结点一个键，左子树的所有键比它小，右子树的所有键比它大。查找就是"从根出发，比当前结点小就往左走，大就往右走"，每下一层排除一半数据，和二分查找一个道理，也是 O(log n)；插入则是"找到该待的位置，挂上去"，不用挪动别人。

4.4 为什么磁盘时代要 B+ 树：算一笔账

二叉搜索树逻辑上很美，放到磁盘上就出事了。问题在于：树的每个结点只有 2 个孩子，树很高。100 万个结点，平衡二叉树的树高大约是 log2(100万) ≈ 20 层。如果每个结点是一个磁盘页，从根找到叶子要走 20 层，就是 20 次磁盘 I/O，每次 10 毫秒，共 200 毫秒——比全表扫描的 100 秒好了 500 倍，但还是不够快。数据库的目标是：把树高压到 3~4 层。

怎么压？答案简单粗暴：让每个结点不止 2 个孩子，而是几百个孩子。这就是 B 树家族的思路——"矮胖"的树。

算一笔具体的账。一个页 4KB（4096 字节）。假设一个键（学号）8 字节，一个指向孩子页的指针 8 字节，那么一个内部结点页能装的路标数约为 4096 ÷ (8+8) = 256 个，也就是一个结点能有约 256 个孩子。这个"孩子数"叫扇出（Fan-out）。

看 100 万条数据。叶子页假设每页装 100 条记录（每条记录 40 字节左右），100 万条需要 1 万个叶子页。内部结点扇出 256：第二层一个页能指 256 个叶子页；第三层一个页能指 256 个第二层页，即 256 × 256 = 65536 个叶子页——已经超过我们需要的 1 万了。所以树高只要 3 层（根 + 一层内部 + 叶子），3 次磁盘 I/O 搞定一次查找。对比二叉树的 20 次，快了约 7 倍；对比全表扫描的 1 万次，快了 3000 多倍。而且数据涨到 10 亿条，也只是再加一层而已（256 × 256 × 256 约 1677 万个叶子页，乘每页 100 条就是 16 亿条）——树高 4 层管 10 亿条数据，这就是 B 树家族的威力。

4.5 B+ 树的结构：为什么是"加号"

B+ 树（B+ Tree）是 B 树的改良版，数据库界的标准答案。它比 B 树多了两条规矩，正是这两条让它无敌：

第一条规矩：内部结点只存路标，不存数据。内部结点的键只是"指示牌"，告诉查找者"比 51 小的往左，51 及以上的往右"，真正的学生记录只存在叶子结点里。好处：内部结点不挂数据，一个页能塞下更多路标，扇出更大，树更矮。

第二条规矩：叶子结点之间用链表串起来，像糖葫芦。所有叶子页按键从小到大，用兄弟指针首尾相连。好处：范围查询原地起飞。查"90 到 100 分"，先用树根定位到 90 所在的叶子，然后顺着叶子的链表一路向右扫，扫到 100 为止——全程不再需要回到树根。B 树没有这条叶子链，范围查询得反复"上树再下树"，慢一截。

所以"B+ 树为什么比 B 树适合数据库"这个面试必考题，标准答案就两点：一是内部结点纯路标化带来更大扇出、更矮树高、更少 I/O；二是叶子链表让范围查询和排序只需要一次定位加顺序扫描，而顺序扫描恰好是磁盘最擅长的活（连续读比随机读快得多）。

4.6 插入与分裂：手算一遍

设每个结点最多装 3 个键（现实中是几百个，这里为演示取小）。往空树依次插入 51、52、53、54。

插 51：根就是叶子，里面放 [51]。插 52：[51, 52]，还没满。插 53：[51, 52, 53]，满了（3 个上限）。插 54：放不下了，分裂（Split）：把 [51, 52, 53, 54] 从中间劈开，左半 [51, 52] 留在原结点，右半 [53, 54] 进一个新结点，然后把分界线 53 复制一份"上交"给父结点当路标。现在树变成：根（内部结点）是 [53]，左孩子叶子 [51, 52]，右孩子叶子 [53, 54]。

再插 50：从根出发，50 < 53 往左走，插进 [51, 52] 变成 [50, 51, 52]，没满，结束。

再插 70、71、72：70 ≥ 53 往右，[53,54] 变成 [53,54,70] 满了；再插 71，分裂成 [53,54] 和 [70,71]，上交 70 给根，根变成 [53, 70]；再插 72，进最右叶子 [70,71,72]。注意如果根自己也撑爆了（4 个路标超过上限 3），根也要分裂，树就长高一层——B+ 树是从顶部（根分裂）长高的，这是它天然保持平衡的原因：所有叶子永远在同一层。

4.7 删除：借用与合并

删除是插入的逆操作，但麻烦在"结点太空了怎么办"。设每个结点至少装 2 个键（上限 3 的一半向上取整）。

上面最后的树：根 [53, 70]，叶子依次是 [50,51,52]、[53,54]、[70,71,72]（叶子间有链表相连）。

删 52：叶子 [50,51,52] 变 [50,51]，还有 2 个，达标，收工。删 51：叶子变 [50]，只有 1 个，不达标了。先看兄弟能不能借：左无兄弟，右兄弟 [53,54] 有 2 个，借了它就只剩 1 个，自身不保，不能借。于是合并（Merge）：把自己 [50] 和右兄弟 [53,54] 并成一个结点 [50,53,54]，同时把父结点里隔开它俩的路标 53 删掉（父结点 [53,70] 变 [70]）。父结点删完还剩 1 个路标，如果父结点也因此不达标，就继续向上借用或合并，最坏一路合并到根。根如果空了，树就降一层。

一句话记忆：插入太满就分裂、往上交路标；删除太空就先向兄弟借，借不到就和兄弟合并、从父结点抽回路标。树的每一次长高和变矮都发生在根，所以整棵树永远平衡，所有查找都稳定地走同样多的层数——这就是"性能可预期"，数据库最爱这种性质。

4.8 BusTub 里你要写什么

Project 2 要求实现 B+ 树的 Insert（含分裂）、Remove（含借用合并）、GetValue（点查）、以及一个按叶子链表走的扫描迭代器（对应范围查询）。所有结点都住在页里——看，Project 1 的缓冲池在这里接上了：B+ 树每访问一个结点，都是向 BufferPoolManager FetchPage 一页，用完 UnpinPage。也就是说 Project 2 天然建在 Project 1 的地基上，这就是为什么课程顺序不能乱。

另外 BusTub 的 Project 2 还要求"并发安全"：多个线程同时在树上查找、插入时不能乱。主流做法叫闩锁蟹行（Latch Crabbing）：从根往下走时，手上一把一把地抓锁，确认子结点"安全"（不会因为这次操作分裂或合并）就放掉父结点的锁。这个思想你先有个印象，第六部分讲完锁再回头看就通了。

第五部分：Project 3 查询执行

5.1 一句 SQL 的三个旅程

用户写下 SELECT name, math FROM scores WHERE math >= 90;，数据库内部要走三段路。

第一段，解析（Parsing）。把这句字符串拆成一棵语法树，确认每个单词合法、表名列名存在。拆错了就报错——你打错 SELCT 时看到的就是这一阶段的报错。

第二段，优化（Optimization）。同一句 SQL 有一百种执行方式：先过滤再扫，还是扫完再过滤？两张表 Join 谁当外层谁当内层？有没有索引可用？优化器（Optimizer）估算每种方案的代价（主要估磁盘 I/O 次数），挑一个最便宜的，产出执行计划（Query Plan）。这是数据库里最深水区的领域，BusTub 只要求点到为止，你知道有这回事即可。

第三段，执行（Execution）。拿着计划，真刀真枪把数据读出来、过滤、拼接、返回。Project 3 干的就是这一段。

5.2 火山模型：一节一节拉数据的流水线

先看朴素做法的翻车：如果执行方式是"扫描完整个表、把 100 万行全部物化（Materialize）在内存里，再一次性交给过滤"，那么内存直接爆炸，而且用户要等全部扫完才能看到第一行结果。

火山模型（Volcano Model，也叫迭代器模型 Iterator Model）的解法：把执行计划组织成一棵树，每个结点是一个算子（Operator），每个算子只对外暴露一个方法——Next()。父算子每次调子算子的 Next()，子算子就返回一行；子算子自己也可能再去调它的子算子的 Next()。数据就像被一根管子从底层一页一页"拉"上来，一次只流动一行，内存占用极小，第一行结果瞬间就能返回。

回忆 1.5 的多态：BusTub 里所有算子继承 AbstractExecutor，都实现了虚函数 Next()。顶层拿着 AbstractExecutor* 一路 Next() 下去，根本不需要知道底层具体是什么算子——火山模型就是多态最漂亮的应用。

5.3 逐个算子讲

第一种，SeqScan（顺序扫描算子）。对应"全表扫描"。它的 Next() 每次从表里取下一行返回。底层每一行数据都住在页里，所以它干活的方式是不断向缓冲池 FetchPage——Project 1 的地基又一次出现。

第二种，IndexScan（索引扫描算子）。对应"走 B+ 树"。WHERE sid = 1234567 时，它的 Next() 直接用 Project 2 的 B+ 树定位到那行，一次树高（约 3 次 I/O）搞定，不用扫全表。

第三种，Filter（过滤算子）。对应 WHERE math >= 90。它坐在 SeqScan 头上：每次 Next() 被调用，它就反复调用子算子的 Next() 拿行，拿到一行就检查"math ≥ 90 吗"，不满足就丢掉再拿下一行，直到拿到满足的行才返回给上层。小明 135 通过，Bob 98 也通过（98 ≥ 90），假设有个 Dave 88 分就会被 Filter 在这一层扔掉。

第四种，Join（连接算子），Project 3 的重头戏。最朴素的实现叫嵌套循环连接（Nested Loop Join）。逻辑就像两张 Excel 表的手工对账：外层表 scores 每取一行，就把内层表 students 从头到尾扫一遍，找学号相同的那行，找到就把两行拼起来输出。伪代码：

C++

// NestedLoopJoin 的 Next() 逻辑（简化）
while (outer_->Next(&outer_tuple)) {        // 外层取一行，比如小明(51, 135)
  while (inner_->Next(&inner_tuple)) {      // 内层扫一遍，51号3班、52号3班...
    if (outer_tuple.sid == inner_tuple.sid) {  // 学号对上了
      return Join(outer_tuple, inner_tuple);   // 拼成 (小明,135,3班) 返回
    }
  }
  inner_->Reset();                          // 外层每换一行，内层从头再扫
}

代价是外层行数乘内层行数：scores 100 万行、students 100 万行，就是 10 的 12 次方次比较，完全不可接受。所以实战中有更聪明的：如果内层表的学号上有 B+ 树索引，内层那一遍扫描就换成一次索引查找（Index Nested Loop Join），代价从"乘"变"外层行数 × 3 次 I/O"，立刻可行。这就是"索引"和"执行器"两个 Project 在实际查询中的会师。

除此之外 BusTub 还要求实现 Aggregation（聚合，对应 COUNT/AVG，内部又是一个哈希表：按分组键把累计值塞进 unordered_map）、OrderBy/Limit（排序与取前 N）等算子，思想都一样：每个算子管好自己那一节的流水线。

5.4 串起来看

SELECT name, math FROM scores WHERE math >= 90 的计划树大概是：顶层 Projection（只留 name、math 两列）→ Filter（math ≥ 90）→ SeqScan（scores）。顶层要一行，Filter 就向 SeqScan 要，SeqScan 向缓冲池要页，缓冲池不够就向磁盘要。四个 Project 的知识在一行 SQL 里全部跑了一遍——这就是 BusTub 最美的地方：它不是四个孤立作业，而是一台层层咬合的机器。

第六部分：Project 4 并发控制

6.1 翻车现场：两笔转账同时改余额

假设小明卡里有 100 元。两个转账同时发生：事务 A 给小明转 50（100→150），事务 B 给小明转 30（100→130）。两个事务的执行都是"读出余额、加上钱、写回去"。

如果执行顺序穿插成这样：A 读出 100；B 读出 100；A 算 100+50=150 写回；B 算 100+30=130 写回。最终余额 130——A 转的 50 块凭空蒸发了。这就是 0.2 讲过的丢失更新在转账场景的重演。银行系统出现一次这种事故，就上新闻了。

6.2 事务（Transaction）与 ACID

数据库的解法是把一组操作打包成事务（Transaction）：要么这一组操作全部生效，要么一个都不生效。事务有四条金标准，缩写 ACID：

A，原子性（Atomicity）：转账的"扣 A 的钱"和"加 B 的钱"必须同生共死，不允许只执行一半。

C，一致性（Consistency）：事务前后，数据必须满足所有约束（比如"账户余额不能为负"）。

I，隔离性（Isolation）：并发执行的多个事务，效果必须像排队挨个执行一样，互相看不见对方的半成品。上面的转账翻车就是隔离性被破坏。

D，持久性（Durability）：事务一旦提交成功，哪怕下一秒断电，改动也不能丢（这条靠写日志 WAL 保证，BusTub 不深入，知道名词即可）。

6.3 锁（Lock）和闩锁（Latch）的区别

面试高频题，必须分清。中文都叫"锁"，英文是两个词。

闩锁（Latch）：保护的是物理数据结构，比如 B+ 树的结点、缓冲池的哈希表。生命周期极短（改个指针的工夫），粒度是"这个数据结构的内部一致性"。我们 1.9 讲的 std::mutex、4.8 讲的闩锁蟹行，都是 Latch。

锁（Lock）：保护的是逻辑数据，比如"学号 51 这一行"。生命周期是整个事务，从加锁一直持有到事务提交才放。粒度是"并发事务之间的隔离"。Project 4 实现的是 Lock。

一句话：Latch 防止线程把 B+ 树拧成麻花，Lock 防止事务把账户余额改错。前者管纳秒级的内存操作，后者管毫秒级的事务全程。

6.4 两阶段锁（2PL）

怎么加锁才能保证隔离性？教科书答案是两阶段锁（2PL, Two-Phase Locking）。规则朴素得不像话：一个事务的生命周期分两段。第一段是增长阶段（Growing Phase），只能加锁，不能放锁；第二段是收缩阶段（Shrinking Phase），一旦放了第一把锁，就永远不许再加新锁，只能一路放到事务结束。

配合锁的两种模式：读之前加共享锁（Shared Lock，S 锁），读读不冲突，一百个事务可以同时读同一行；写之前加排他锁（Exclusive Lock，X 锁），写写、读写都冲突，拿到 X 锁的行别人碰都不能碰。

回到转账翻车：用了 2PL 之后，A 先给小明那行加 X 锁；B 也想加 X 锁，发现被占，只能排队等；A 改完提交、放锁，B 才拿到锁，此时读到的是 A 改后的 150，150+30=180，正确。穿插执行的灾难被"排队"化解了。

为什么"一旦放锁就不能再加"这条这么关键？因为可以证明（证明略）：只要所有事务都遵守 2PL，任何并发调度的效果都等价于某种串行顺序，隔离性就有了铁保证。这条规则用一句话记：先攒齐粮草（锁）再开打，开打途中不许再征新粮。

6.5 死锁与检测

2PL 带来了新麻烦：死锁（Deadlock）。事务 A 锁了小明的行，又想去锁 Alice 的行；事务 B 锁了 Alice 的行，又想去锁小明的行。A 等 B 放 Alice，B 等 A 放小明，谁也不放，双双等到天荒地老。

解法有两派。一派是预防：规定所有事务按固定顺序加锁（比如按学号从小到大），环就形不成。另一派是检测加杀死，BusTub 采用这派：后台跑一个死锁检测线程，维护一张"等待图"（Waits-for Graph）——每个事务是结点，"A 在等 B"就画一条 A→B 的边。图里一旦出现环，说明死锁成立，检测线程就挑环上的一个倒霉蛋事务强行中止（Abort），让它释放所有锁，其他人得救。被中止的事务由上层重试即可。

Project 4 你要写的核心就是：LockManager（锁管理器，处理"加锁/放锁/排队等锁"）和一个死锁检测器（周期性在等待图上找环）。写完这个，你的迷你数据库就能让多个事务安全地并发跑了。

第七部分：简历怎么写 + 面试怎么答

7.1 简历项目描述（可直接改写使用）

项目名称：BusTub 教学型关系数据库内核（CMU 15-445 课程项目，C++，独立完成，约 X 千行代码）

描述示例（STAR 结构）：

背景与目标（S/T）：基于 CMU 15-445 的 BusTub 框架，独立实现一个支持 SQL 查询与事务并发的教学型关系数据库核心模块，覆盖存储、索引、执行、并发四大子系统。
行动（A）：实现基于 LRU-K 替换算法的页式缓冲池，以哈希表实现 O(1) 页定位，用脏页标记与 pin 计数保证数据一致性；实现磁盘友好的 B+ 树索引，支持点查、范围扫描与并发访问（闩锁蟹行）；实现火山模型查询执行引擎，包括顺序扫描、索引扫描、过滤、嵌套循环连接与聚合算子；实现两阶段锁锁管理器与基于等待图的死锁检测，支持多事务并发。
结果（R）：通过课程全部线上测试（Gradescope 满分/XX 分）；对 B+ 树索引下的点查与范围查询性能做了对比实验，点查较全表扫描提升约 X 个数量级（此处填你自己实测的数字）。

注意：数字那一栏最好自己跑个小实验填真数据，面试官就爱听你自己测过。

7.2 面试高频十问及答案要点

第一问：缓冲池为什么用 LRU-K 不用 LRU？答：纯 LRU 会被顺序扫描污染——一次只读一遍的海量冷页会把真正的热页全部挤出缓存。LRU-K 比较的是"倒数第 K 次访问时间"，只访问过一次的扫描页距离视为无穷大，会优先被淘汰，热页得以保留。K 通常取 2，因为 K 再大就要存更多历史时间戳，收益递减。

第二问：B+ 树为什么比 B 树适合数据库索引？答：两点。B+ 树内部结点只存路标不存数据，扇出更大，树更矮，磁盘 I/O 更少；B+ 树叶子结点串成有序链表，范围查询和排序只需一次定位加顺序扫描，而 B 树范围查询要反复回到内部结点遍历。

第三问：为什么不用哈希索引？答：哈希索引只支持等值查询，不支持范围查询（哈希函数把相近键打散）和排序。数据库业务中范围与排序是刚需，所以主力索引用 B+ 树，哈希只在特定场景（如内存表等值查询）使用。

第四问：B+ 树为什么树矮？给数据。答：扇出大。4KB 页、8 字节键加 8 字节指针，内部结点扇出约 256。3 层树可索引约 256×256×100 约 650 万条记录，4 层约 16 亿条。查找一次的 I/O 次数等于树高，所以 3~4 次 I/O 就能在亿级数据里定位一行。

第五问：pin/unpin 是干嘛的？答：pin 计数标记"这页正被使用"。pin 大于零的页不可被替换算法驱逐，防止执行器读到一半页被换掉导致悬垂指针。用完 unpin 减计数，归零后恢复可替换。

第六问：脏页是什么？为什么淘汰时区别对待？答：脏页是在内存中被修改但尚未写回磁盘的页。淘汰脏页必须先写回磁盘，否则修改丢失；干净页可直接丢弃，因为磁盘上有相同副本。这就是 is_dirty 标记的作用。

第七问：火山模型是什么？有什么缺点？答：每个算子实现统一的 Next() 接口，父算子向子算子逐行拉数据，数据以元组为单位在算子树中流动，内存占用小、首行返回快。缺点是每行都要走一串虚函数调用，对 CPU 缓存不友好，所以工业界分析型数据库多用向量化模型（一次处理一批行）——能主动提到这个缺点是加分项。

第八问：Lock 和 Latch 的区别？答：Latch 保护物理数据结构（B+ 树结点、哈希表）的内存一致性，持有时间极短，用 mutex 实现；Lock 保护逻辑数据（某行、某表）的事务隔离性，持有到事务结束，由锁管理器实现。前者防数据结构被并发线程破坏，后者防事务互相看到半成品。

第九问：什么是 2PL？为什么能保证隔离性？答：两阶段锁：事务分增长阶段（只加锁）和收缩阶段（只放锁），一旦放了第一把锁就不得再加新锁。可以证明，所有事务遵守 2PL 时，任何并发调度都等价于某个串行调度，因此可串行化、隔离性成立。代价是并发度降低且可能死锁，所以要配死锁检测。

第十问：死锁怎么检测？答：维护等待图（Waits-for Graph），结点是事务，边表示"等待持有锁者"。后台线程周期性地在图上找环，有环即死锁，选中环上一个事务中止并释放其全部锁，打破环路。代价选择通常考虑事务已做的工作量、持有锁的数量等。

结语：接下来怎么走

把四个 Project 按顺序做完，每做完一个就回来重读本教程对应的部分，把代码和你脑子里的概念对上号。然后做两件事巩固：第一件，给每个模块写一个小实验，比如"开 100 万行数据，对比有索引和无索引的查询耗时"，把数字记下来放进简历；第二件，把第七部分的十个问题对着镜子自问自答，答不顺的地方回到对应章节重读。

数据库内核这条路，入行门槛高，但正因为高，竞争者少。你能在大一就把 BusTub 吃透，就已经站在了绝大多数同龄人的前面。加油。