项目一：亲手敲出一个迷你数据库内核（BusTub 实战动手篇）
项目一：亲手敲出一个迷你数据库内核（BusTub 实战动手篇）
写在最前面：这篇教程要带你干什么
上一批概念教程你读完了。你知道了缓冲池（Buffer Pool）是什么、B+树（B+ Tree）是什么、索引和数据怎么配合。但是你说：我不会写代码，整体框架没搭起来。
没关系。这一篇不讲新概念。这一篇只做一件事：带你亲手把代码敲出来，编译通过，看到运行结果。
我们最终要做出一个迷你数据库内核，对应 CMU 15-445 这门课的 BusTub 项目的核心两样东西：
- 一个迷你缓冲池：管内存和磁盘之间的数据搬运，带 LRU（Least Recently Used，最近最少使用）替换。
- 一个迷你 B+树索引：支持插入、点查、范围查询。
最后一里程碑，我们把这两样组装起来：B+树当索引，缓冲池管数据页，录入 20 个学生，按学号点查，按分数范围查。你会亲眼看到"索引"和"数据"是怎么配合的。
你是谁，你需要什么基础
假设你是大一学生，从来没敲过一行代码。你不知道终端是什么，不知道编译是什么意思。完全没问题，我们从"终端是什么"开始教。
你不需要买任何东西。你只需要一台电脑，和一点点耐心。
我们的打法：六个里程碑，一步一个结果
整篇教程分成六个里程碑（Milestone），从 M0 到 M5。每个里程碑都能跑出一个你能看到的结果：
- M0：环境搭建，敲出人生第一行代码，看到屏幕打印出一句话。
- M1：变量、循环、容器，做一个命令行成绩单程序。
- M2：类和对象，把成绩单封装成一个 class。
- M3：迷你缓冲池，本篇的重头戏。
- M4：迷你 B+树，第二重头戏。
- M5：组装收官，索引加数据页，一个真正能查的迷你数据库。
每个里程碑都按固定的六件套来讲：先说要做出什么，再给出完整代码，再逐行讲解，再给编译运行命令，再贴出真实运行结果，最后是报错诊所和一个小练习。
注意：教程里所有代码都完整给出，一个字都不省。你要做的是照着敲，或者复制过去跑通，然后再改着玩。
你用的环境
教程里的命令以 Ubuntu 24.04 虚拟机为准。打开终端，先装编译工具：
sudo apt update
sudo apt install build-essential cmake如果你用的是 Windows 上的 MSYS2，命令完全一样，因为 MSYS2 给你提供了一模一样的 bash 终端和 g++ 编译器。本教程的全部代码都在 MSYS2 的 g++ 16.1.0 下真实编译运行过，零警告零错误，你在 Ubuntu 下跑结果一样。
所有代码只用 C++ 标准库，C++17 标准，不装任何第三方依赖。
好，我们开始。
M0M0：环境与人生第一行代码
这一步我们要做出什么
屏幕上打印出一行字：Hello, database!。就这。但你要走完"写代码、编译、运行"的完整流程，这个流程后面每一步都要用。
先搞懂两个词：终端和编译
终端（Terminal）是什么？它就是一个黑窗口，你在里面打字，电脑照做。比如你在终端里打 g++ main.cpp，电脑就去调用 g++ 这个程序。以后我们说"打开终端"，Ubuntu 下就是按 Ctrl+Alt+T，Windows 的 MSYS2 下就是打开 MSYS2 UCRT64 那个程序。
编译（Compile）是什么？你写的代码是文本文件，人看得懂，机器看不懂。编译就是把源代码翻译成机器能跑的文件。g++ 就是干这个翻译活的程序，它叫编译器（Compiler）。你写的 main.cpp 是源代码，翻译出来的 main（Windows 下叫 main.exe）是可执行文件，双击或者在终端里敲 ./main 就能跑。
整个流程永远是三步：写源代码 → 用 g++ 编译 → 运行生成的文件。记住这三步，后面每个里程碑都是这三步。
验证 g++ 装好了
打开终端，输入：
g++ --version你应该看到类似这样的输出：
g++ (Rev5, Built by MSYS2 project) 16.1.0
Copyright (C) 2026 Free Software Foundation, Inc.版本号不一样没关系，只要有版本号蹦出来，就说明编译器装好了。如果说"command not found"，Ubuntu 下就跑一遍 sudo apt install build-essential，装完再试。
用 VS Code 打开一个工作文件夹
我们需要一个地方放代码。先建一个文件夹，比如在终端里输入：
mkdir -p ~/bustub-mini/m0_hello
cd ~/bustub-mini/m0_hellomkdir 是"建文件夹"，cd 是"进到这个文件夹里"。然后打开 VS Code，菜单栏选 File，再选 Open Folder，选中刚建的 m0_hello 文件夹。以后每个里程碑都建一个新文件夹，互不干扰。
新建 main.cpp，敲入五行代码
在 VS Code 左侧文件列表上右键，选 New File，文件名输入 main.cpp。然后在里面敲入下面全部内容，一行都不许少：
#include <iostream>
int main() {
std::cout << "Hello, database!" << std::endl;
return 0;
}敲完按 Ctrl+S 保存。一定记住保存，很多人代码改了没保存，编译的还是旧文件。
逐行讲解
#include <iostream>：这一行说"我要用输入输出工具包"。iostream 是 Input Output Stream（输入输出流）的缩写，是 C++ 标准库的一部分。没有这一行，下面的 std::cout 就不存在，编译器会说不认识它。删掉它试试？编译器会报错 error: 'cout' is not a member of 'std'。
空行：啥也不干，就是为了好看，把"准备工作"和"正文"隔开。
int main()：这是程序的入口，也就是程序开始跑的地方。你写的程序必须有且只有一个 main 函数（function，函数），机器运行你的程序时，就是从 main 的第一行开始往下执行。int 表示这个函数最后会返回一个整数。
大括号 { }：main 函数的身体，里面每一行是一条语句，机器从上到下挨个执行。
std::cout << "Hello, database!" << std::endl;：这是本程序唯一真正干活的语句。std::cout 是"标准输出"（Standard Character Output），你可以把它理解成"往屏幕上打印"。<< 这个符号读作"往里面送"，把右边的内容送到左边的屏幕上去。"Hello, database!" 是要打印的文字，双引号包起来的叫字符串（String）。std::endl 是"换行"（End Line），让光标挪到下一行开头。行尾的分号 ; 表示"这句话说完了"，C++ 里几乎每条语句结尾都要打分号。
return 0;：main 函数结束，返回 0 告诉操作系统"我正常跑完了"。返回非 0 一般表示出错了。这一行删掉程序也能跑（编译器会帮你补一个），但我们写上，养成好习惯。
编译命令和运行命令
回到终端，确认你在 m0_hello 文件夹里（用 ls 命令应该能看到 main.cpp），然后输入编译命令：
g++ -std=c++17 -Wall -Wextra -o main main.cpp拆解一下这条命令。g++ 是编译器。-std=c++17 说"用 C++ 的 2017 年标准"。-Wall -Wextra 说"把所有警告都打开"，警告是编译器的善意提醒，我们要求零警告。-o main 说"翻译出来的文件取名叫 main"。最后一个 main.cpp 是源代码文件。
敲完回车，如果什么都没输出，恭喜你，编译成功了。编译器沉默就是好消息。文件夹里会多出一个叫 main（或 main.exe）的文件。
运行它：
./main./ 的意思是"当前文件夹里的"。
你应该看到的输出
Hello, database!就这一行。看到了，你的 M0 就完成了。这是你的人生第一行代码跑出来的结果。
报错诊所
这一步最容易犯四个错误，我们把每个错误的真实报错文本给你看。
错误一：忘了打分号。把第 4 行末尾的分号删掉，编译时你会看到：
main.cpp: In function 'int main()':
main.cpp:4:38: error: expected ';' before 'return'
4 | std::cout << "Hello" << std::endl
| ^
| ;读法：第 4 行第 38 个字符附近，error（错误），expected ';' before 'return'，意思是"在 return 前面少了个分号"。编译器甚至还用 ^ 给你指了位置，用分号提示你该加什么。改法：回到第 4 行末尾，把分号补上。
错误二：用了中文标点。如果你把分号打成了中文分号"；"，或者引号打成中文引号，报错长这样：
main.cpp:4:34: error: 'endl\U0000ff1b' is not a member of 'std'; did you mean 'endl'?' 意思是编译器把中文符号当成了代码的一部分，完全懵了。改法：检查报错那一行，把所有标点换成英文半角。记住：写代码时输入法永远切英文。
错误三：文件名不对。你保存成了 Main.cpp 或 main.txt，然后敲 g++ main.cpp，报错是：
g++: error: main.cpp: No such file or directory意思是"找不到这个文件"。改法：用 ls 看看文件夹里到底叫什么，文件名大小写要一模一样。
错误四：忘了保存。你在 VS Code 里改了代码，标题栏文件名旁边有个小圆点，说明没保存。这时编译跑的是旧代码，你会纳闷"我明明改了怎么没效果"。改法：Ctrl+S 养成肌肉记忆。
小练习
把打印的文字改成你的学号和名字，比如 std::cout << "我是学号51的小明" << std::endl;，重新编译运行。再试试加一行，打印第二句话。记住：每加一行，结尾都要打分号，改完要保存，保存完要重新编译。
M1M1：变量、循环、容器——命令行成绩单
这一步我们要做出什么
一个成绩单程序。程序里预录 5 个学生的数学成绩，包括学号 51 的小明，他数学考了 135 分。程序先把全班成绩打印一遍，然后问你"要查谁的"，你输入学号 51，它告诉你 135 分。
这一步你会学到三样东西：变量（存数据的盒子）、循环（重复干活）、容器（装一堆数据的集合）。容器我们直接用 unordered_map，也就是哈希表（Hash Table），概念篇里讲过，这次亲手用它。
新建文件
新建文件夹 m1_gradebook，在里面新建 main.cpp，敲入下面全部内容：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> scores;
scores[51] = 135;
scores[52] = 128;
scores[53] = 142;
scores[54] = 98;
scores[55] = 150;
std::cout << "已录入 5 个学生的数学成绩" << std::endl;
for (const auto& item : scores) {
std::cout << "学号 " << item.first << "，数学 " << item.second << " 分" << std::endl;
}
int id;
std::cout << "请输入要查询的学号：";
std::cin >> id;
auto it = scores.find(id);
if (it != scores.end()) {
std::cout << "学号 " << id << " 的数学成绩是 " << it->second << " 分" << std::endl;
} else {
std::cout << "没有找到学号 " << id << " 的成绩" << std::endl;
}
return 0;
}逐行讲解
#include <unordered_map>：引入哈希表工具包。unordered_map 是 C++ 标准库里的哈希表实现，名字直译是"无序的映射"。
std::unordered_map<int, int> scores;：创建一个哈希表，名字叫 scores。两个 int 分别说明键（Key）是整数、值（Value）是整数。我们这里键是学号，值是数学成绩。也就是一张"学号 → 成绩"的对照表。
scores[51] = 135;：往表里放一条记录：学号 51，成绩 135。这就是小明。方括号里写键，等号右边写值。下面四行同理，录入学号 52 到 55 的四个学生。
for (const auto& item : scores)：这是循环，读作"对 scores 里的每一条记录 item，都执行一遍大括号里的话"。哈希表里有 5 条记录，大括号里的话就执行 5 遍。item.first 是这条记录的键（学号），item.second 是值（成绩）。
这里有个重要细节：你运行后会看到，打印出来的顺序不是 51、52、53、54、55，而是乱的。为什么？因为哈希表内部按哈希值分桶存放，遍历顺序是桶的顺序，不是插入顺序。这就是"unordered"（无序）这个词的含义。概念篇里说过哈希表擅长点查但不擅长按顺序遍历，现在你亲眼看到了。
int id;：声明一个整数变量 id，准备装用户输入的学号。变量就是一个有名字的盒子，int 说明这个盒子只装整数。
std::cin >> id;：std::cin 是"标准输入"（Standard Character Input），和 cout 相反，它是从键盘读东西。>> 读作"从键盘拿出来放进 id"。程序跑到这一行会停下来，等你打字，你打 51 再按回车，id 这个盒子里就装上了 51。
auto it = scores.find(id);：在哈希表里查 id 这个键。find 返回一个"迭代器"（Iterator），你可以理解成"指向找到的那条记录的箭头"。
if (it != scores.end())：如果箭头不等于"末尾标记"，说明找到了。scores.end() 是哈希表约定好的"没找到"的标志。找到了就打印 it->second（成绩），否则走 else 分支打印"没找到"。
编译命令和运行命令
g++ -std=c++17 -Wall -Wextra -o main main.cpp
./main程序会停下来等你输入，输入 51 按回车。
你应该看到的输出
已录入 5 个学生的数学成绩
学号 55，数学 150 分
学号 54，数学 98 分
学号 53，数学 142 分
学号 52，数学 128 分
学号 51，数学 135 分
请输入要查询的学号：学号 51 的数学成绩是 135 分注意看遍历顺序：55、54、53、52、51，倒序纯属巧合，是哈希桶的顺序，不保证任何规律。如果你输入 99，最后一行会变成"没有找到学号 99 的成绩"。
报错诊所
错误一：把 std::cin >> id; 的方向写反成 std::cin << id;。报错：
error: no match for 'operator<<' (operand types are 'std::istream' and 'int')记法：cin 配 >>（从键盘流进变量），cout 配 <<（从变量流向屏幕）。箭头方向就是数据流动方向。
错误二：方括号写成圆括号，scores(51) = 135;。报错：
error: no match for call to '(std::unordered_map<int, int>) (int)'改法：哈希表用方括号 [ ] 取元素。
错误三：int id; 之前就用 id。C++ 要求先声明再使用，报错 error: 'id' was not declared in this scope，意思是"id 没声明过"。改法：把声明挪到使用之前。
错误四：删掉 #include <unordered_map>。报错 error: 'unordered_map' is not a member of 'std'。改法：把 include 加回来。每个标准库工具都有对应的 include，用谁引谁。
小练习
给成绩单再加两个学生：学号 56 的 Alice，数学 121 分；学号 57 的 Bob，数学 89 分。再把 54 号的成绩从 98 改成 105（提示：再写一句 scores[54] = 105;，哈希表会自动覆盖旧值）。重新编译运行，看看输出多了什么。
M2M2：类和对象——把数据和方法捆在一起
这一步我们要做出什么
功能和 M1 一模一样，但代码的组织方式变了：我们把"成绩数据"和"录入、查询、打印这三个操作"捆成一个整体，叫 GradeBook 类（Class）。这是通往数据库内核的关键一步，因为缓冲池和 B+树都要写成类。
为什么要把数据和方法捆在一起
先按我们的固定套路来：朴素做法失败 → 机制 → 具体数字钉死。
朴素做法就是 M1 那样：一个 scores 变量摆在 main 函数里，谁都能直接改。假设程序变大了，main 里有五百行代码，三个地方都在改 scores，其中一个地方手滑写成了 scores[51] = -999;，成绩变成负数，你要翻五百行才能找到凶手。这就是失败点：数据和操作它的代码散落各处，管不住。
机制就是类。类把数据藏起来（私有，private），只留几个窗口让人用（公有方法，public method）。想改成绩？只能走 add 窗口。以后出 bug 了，只看这几个窗口就行。
具体数字钉死：M2 的程序里，私有数据只有 1 个（scores_），公有窗口只有 3 个（add、query、printAll）。main 函数想碰数据，必须经过这 3 个窗口之一，没有第四条路。
新建文件
新建文件夹 m2_class，新建 main.cpp，敲入全部内容：
#include <iostream>
#include <unordered_map>
class GradeBook {
public:
GradeBook() {
std::cout << "一本新的成绩单被创建出来了" << std::endl;
}
void add(int id, int score) {
scores_[id] = score;
std::cout << "录入：学号 " << id << "，数学 " << score << " 分" << std::endl;
}
void query(int id) const {
auto it = scores_.find(id);
if (it != scores_.end()) {
std::cout << "查到：学号 " << id << "，数学 " << it->second << " 分" << std::endl;
} else {
std::cout << "没找到：学号 " << id << std::endl;
}
}
void printAll() const {
std::cout << "---- 全班成绩单（共 " << scores_.size() << " 人）----" << std::endl;
for (const auto& item : scores_) {
std::cout << "学号 " << item.first << "，数学 " << item.second << " 分" << std::endl;
}
}
private:
std::unordered_map<int, int> scores_;
};
int main() {
GradeBook book;
book.add(51, 135);
book.add(52, 128);
book.add(53, 142);
book.add(54, 98);
book.add(55, 150);
book.printAll();
int id;
std::cout << "请输入要查询的学号：";
std::cin >> id;
book.query(id);
return 0;
}逐行讲解
class GradeBook { ... };：定义一个类。类就是一张图纸，描述"这种东西里面有什么数据、能干什么事"。注意结尾大括号后面有个分号，这是类的特殊规定，忘掉它是最经典的错误。
public: 和 private:：两个区域标签。public 下面的东西谁都能用，private 下面的东西只有类自己能用。我们的图纸是：公有 4 个方法，私有 1 个数据。
GradeBook()：和类同名的函数叫构造函数（Constructor），创建对象时自动执行一次。我们在里面打印一句话，让你看到它被自动调用了。
void add(int id, int score)：定义一个方法。void 表示"不返回任何东西"。括号里是参数，调用时要传进来两个整数。函数体里 scores_[id] = score; 就是 M1 学过的哈希表写入。
void query(int id) const：结尾的 const 是一个承诺："这个方法只读不改数据"。query 只查不写，printAll 只打印不改，都标上 const。add 会改数据，不能标。
scores_：私有成员变量。结尾的下划线是程序员的命名习惯，表示"这是类内部的成员，别和局部变量搞混"。
int main() 里：GradeBook book; 用图纸造出一个具体的东西，这个东西叫对象（Object）。图纸是类，造出来的实物是对象。一行代码，先自动跑构造函数，所以你会看到第一行输出"一本新的成绩单被创建出来了"。
book.add(51, 135);：通过对象调用方法，点号 . 读作"的"，也就是"book 的 add 方法"。
编译命令和运行命令
g++ -std=c++17 -Wall -Wextra -o main main.cpp
./main输入 53 回车。
你应该看到的输出
一本新的成绩单被创建出来了
录入：学号 51，数学 135 分
录入：学号 52，数学 128 分
录入：学号 53，数学 142 分
录入：学号 54，数学 98 分
录入：学号 55，数学 150 分
---- 全班成绩单（共 5 人）----
学号 55，数学 150 分
学号 54，数学 98 分
学号 53，数学 142 分
学号 52，数学 128 分
学号 51，数学 135 分
请输入要查询的学号：查到：学号 53，数学 142 分报错诊所
错误一：类定义的大括号后面忘打分号。这是新手第一名错误，报错长这样：
error: expected ';' after class definition改法：class GradeBook { ... }; 结尾的分号补上。
错误二：在 main 里直接访问私有数据，写 book.scores_[51] = 135;。报错：
error: 'std::unordered_map<int, int> GradeBook::scores_' is private within this context编译器明确告诉你：scores_ 是私有的，这里不许碰。这正是我们要的效果，数据被保护起来了。改法：走公有窗口 book.add(51, 135);。
错误三：给 const 方法里写改数据的代码，比如在 query 里加一句 scores_[id] = 0;。报错：
error: assignment of member 'GradeBook::scores_' in read-only object意思是"你在一个承诺了只读的方法里改数据"。改法：要么删掉那句，要么把 const 去掉。
错误四：调用方法时忘传参数，book.add(51);。报错提示参数太少：error: too few arguments to function call。改法：add 要两个参数，学号和成绩都给齐。
小练习
给 GradeBook 加一个公有方法 remove(int id)，里面调用 scores_.erase(id);，功能是删除一个学生的成绩。在 main 里录入 5 人后删除 54 号，再 printAll，确认只剩 4 人。
M3M3：迷你缓冲池——本篇的重头戏
这一步我们要做出什么
真正的数据库内核代码来了。我们用一个普通文件模拟磁盘，用一个只有 3 个页框的缓冲池模拟内存，然后反复访问 10 个页。你会亲眼看到：只访问 3 个页时全部命中（hit），访问第 4 个页时最久没用的页被踢出去，脏页被换出时会写回磁盘。这就是 BusTub Project 1 的迷你版。
先回忆：为什么需要缓冲池
固定套路：朴素做法失败 → 机制 → 具体数字钉死。
朴素做法：每次查询都直接读磁盘文件。失败点在于磁盘太慢，读一次磁盘的时间够内存读十万次。假设你的抖音点赞列表有一亿行，每点一次"刷新"都从头读磁盘，app 会卡成幻灯片。
机制：在内存里留一块地方，把常用的磁盘页缓存起来。下次再要同一页，直接从内存给，不碰磁盘。内存满了怎么办？踢掉最久没用的那个，也就是 LRU 策略。
具体数字钉死：我们的迷你版里，页的大小是 4096 字节（4KB，和真实数据库一样），缓冲池只有 3 个页框（Frame）。也就是说内存最多同时装 3 页，第 4 页来了必须踢一个。数字越小，你越能看清替换过程。
整体结构：三个类分工
代码里有三个角色：
- DiskManager：管磁盘。就一个职责，按页号读写文件。页 0 在文件的第 0 到 4095 字节，页 1 在第 4096 到 8191 字节，以此类推。
- Frame：一个页框。一块 4096 字节的内存，外加三个状态：装的是哪一页（page_id）、脏不脏（dirty）、被几个人在用（pin_count）。
- BufferPool：管 3 个页框。核心是 page_table，一个哈希表，记录"磁盘页号 → 页框号"的对应关系。这就是 M1 学的 unordered_map，现在它登上内核舞台了。
新建文件
新建文件夹 m3_bufferpool，新建 main.cpp，敲入全部内容（比较长，约 170 行，稳住）：
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>
const int PAGE_SIZE = 4096; // 一页 4096 字节，和真实数据库一样
const int POOL_SIZE = 3; // 缓冲池只有 3 个页框
// 磁盘管理器：用一个普通文件模拟磁盘，按页读写
class DiskManager {
public:
explicit DiskManager(const std::string& filename) {
file_.open(filename, std::ios::in | std::ios::out | std::ios::binary);
if (!file_.is_open()) { // 文件不存在就新建
file_.clear();
file_.open(filename, std::ios::out | std::ios::binary);
file_.close();
file_.open(filename, std::ios::in | std::ios::out | std::ios::binary);
}
}
void readPage(int page_id, char* buf) {
file_.seekg(static_cast<long>(page_id) * PAGE_SIZE);
file_.read(buf, PAGE_SIZE);
if (file_.gcount() < PAGE_SIZE) { // 文件没这么长，说明这页是空的
file_.clear();
std::memset(buf, 0, PAGE_SIZE);
}
}
void writePage(int page_id, const char* buf) {
file_.seekp(static_cast<long>(page_id) * PAGE_SIZE);
file_.write(buf, PAGE_SIZE);
file_.flush();
}
private:
std::fstream file_;
};
// 一个页框：缓冲池里的一块内存，装着一页数据和它的状态
struct Frame {
char data[PAGE_SIZE];
int page_id = -1; // 装的磁盘页号，-1 表示空
bool dirty = false; // 被改写过吗？换出时要不要写回磁盘？
int pin_count = 0; // 正在被几个人用？大于 0 不许换出
};
class BufferPool {
public:
explicit BufferPool(DiskManager* disk) : disk_(disk), frames_(POOL_SIZE) {}
// 取一页：命中直接给，缺失就换入（可能踢人出去）
Frame* fetchPage(int page_id) {
auto it = page_table_.find(page_id);
if (it != page_table_.end()) { // 命中！
int fid = it->second;
frames_[fid].pin_count++;
touch(fid);
std::cout << "访问页 " << page_id << "：命中(hit)，已在页框 " << fid << std::endl;
return &frames_[fid];
}
// 缺失：找一个空页框，或者把最久没用的踢出去
int fid = findVictim();
if (fid == -1) {
std::cout << "访问页 " << page_id << "：失败，所有页框都被 pin 住了" << std::endl;
return nullptr;
}
evictIfNeeded(fid);
disk_->readPage(page_id, frames_[fid].data);
frames_[fid].page_id = page_id;
frames_[fid].dirty = false;
frames_[fid].pin_count = 1;
page_table_[page_id] = fid;
touch(fid);
std::cout << "访问页 " << page_id << "：缺失(miss)，从磁盘读入页框 " << fid << std::endl;
return &frames_[fid];
}
// 用完一页：pin 计数减一，告诉缓冲池改没改它
void unpinPage(int page_id, bool is_dirty) {
auto it = page_table_.find(page_id);
if (it == page_table_.end()) return;
Frame& f = frames_[it->second];
if (f.pin_count > 0) f.pin_count--;
if (is_dirty) f.dirty = true;
}
private:
// 找牺牲页框：优先空框，否则 LRU 链尾（最久没用且没被 pin 的）
int findVictim() {
for (int i = 0; i < POOL_SIZE; i++) {
if (frames_[i].page_id == -1) return i;
}
for (auto rit = lru_.rbegin(); rit != lru_.rend(); ++rit) {
if (frames_[*rit].pin_count == 0) return *rit;
}
return -1;
}
void evictIfNeeded(int fid) {
Frame& f = frames_[fid];
if (f.page_id == -1) return;
if (f.dirty) {
disk_->writePage(f.page_id, f.data);
std::cout << " 页框 " << fid << " 里的旧页 " << f.page_id << " 是脏页，写回磁盘" << std::endl;
} else {
std::cout << " 页框 " << fid << " 里的旧页 " << f.page_id << " 干净，直接丢弃" << std::endl;
}
page_table_.erase(f.page_id);
lru_.remove(fid);
f.page_id = -1;
}
void touch(int fid) { // 刚用过，挪到 LRU 链头
lru_.remove(fid);
lru_.push_front(fid);
}
DiskManager* disk_;
std::vector<Frame> frames_;
std::unordered_map<int, int> page_table_; // 页号 -> 页框号
std::list<int> lru_; // 链头最近用，链尾最久没用
};
int main() {
DiskManager disk("data.db");
BufferPool pool(&disk);
std::cout << "== 第一幕：只访问 0、1、2 三个页 ==" << std::endl;
for (int i = 0; i < 2; i++) {
for (int p = 0; p <= 2; p++) {
pool.fetchPage(p);
pool.unpinPage(p, false);
}
}
std::cout << std::endl << "== 第二幕：访问第 4 个页（页 3），谁会被踢出去？==" << std::endl;
Frame* f = pool.fetchPage(3);
f->data[0] = 'X'; // 写点东西，把它弄脏
pool.unpinPage(3, true);
std::cout << std::endl << "== 第三幕：再访问页 0，它还在吗？==" << std::endl;
f = pool.fetchPage(0);
pool.unpinPage(0, false);
std::cout << std::endl << "== 第四幕：连续访问 4~9，看 LRU 连环换出 ==" << std::endl;
for (int p = 4; p <= 9; p++) {
pool.fetchPage(p);
pool.unpinPage(p, false);
}
return 0;
}逐行讲解（挑重点讲）
代码太长，我们不逐行过了，挑骨架讲。
DiskManager 部分。file_.open(filename, std::ios::in | std::ios::out | std::ios::binary)：以"可读、可写、二进制"三种模式打开文件。binary 很关键，Windows 下不加它，换行符会被偷偷改掉，页的内容就错位了。构造函数里的 if 是处理"文件还不存在"的情况：先以只写模式创建它，关掉，再以读写模式重新打开。
readPage 里 file_.seekg(static_cast<long>(page_id) * PAGE_SIZE)：把文件读写指针挪到"页号乘 4096"的字节位置。页 3 就从第 12288 字节开始读。这就是"按页读写"的全部秘密：页号乘以页大小等于字节偏移量。file_.gcount() < PAGE_SIZE 的判断是处理"文件还没这么长"的情况，比如一个全新的文件里根本没有页 5，那就给一整页 0。
Frame 结构体。注意它和 class 的区别：struct 的成员默认公有。Frame 就是个数据包，不需要藏东西，用 struct 省事。char data[PAGE_SIZE] 是 4096 字节的数组，一页的内存。三个状态字段各管一件事：page_id 记身份，dirty 记"改没改"，pin_count 记"几个人在用"。
BufferPool 的构造函数 : disk_(disk), frames_(POOL_SIZE)：这是成员初始化列表，意思是"把 disk_ 设为传进来的 disk，把 frames_ 数组建成 3 个 Frame"。
fetchPage 是核心方法，分两条路。第一条路：page_table_.find 找到了，命中，pin_count 加一，touch 一下刷新 LRU 位置，返回。第二条路：没找到，先 findVictim 找牺牲页框，evictIfNeeded 把旧住户清走，readPage 把新页读进来，更新状态，登记进 page_table，返回。
pin_count 是什么用？假设查询正读着某一页，读到一半缓冲池把这页踢出去了，查询就崩了。所以正在用的页要"钉住"（pin），pin_count 大于 0 的页不许当牺牲品。用完了要 unpin，计数减一。这就是为什么代码里每个 fetchPage 后面都跟着一个 unpinPage，一对一对出现。
findVictim 的逻辑：先扫一遍有没有空页框（page_id 为 -1），有就直接用。没有空框，就从 LRU 链尾往链头找第一个 pin_count 为 0 的。链尾就是最久没用的。
touch 方法两行：lru_.remove(fid) 把这个页框从链里摘出来，lru_.push_front(fid) 塞到链头。每次访问都这么做，链头永远是刚用过的，链尾永远是最久没用的。LRU 就是这么简单。
evictIfNeeded 的脏页处理是重点：如果旧页被改过（dirty 为 true），必须先 writePage 写回磁盘再丢弃，否则修改就丢了。如果是干净的，直接丢，反正磁盘上还有一模一样的副本。
main 函数的四幕是精心设计的实验。第一幕连续两轮访问 0、1、2，第一轮三个 miss（池子是空的），第二轮应该全部 hit。第二幕访问页 3，池子满了，LRU 链尾是页 0（第一轮里它最早被访问，之后两轮循环里它虽然也被碰过——等等，注意看：循环里 0、1、2 每轮都被 touch，第二轮结束时 LRU 链从尾到头是 0、1、2，所以页 0 最"老"），页 0 被踢出去。第三幕再访问页 0，它已经被踢了，所以 miss，而且这次踢的是页 1。第四幕连续访问 4 到 9，每次都要踢人，你能看到脏页 3 被写回磁盘的那一行。
编译命令和运行命令
g++ -std=c++17 -Wall -Wextra -o main main.cpp
./main你应该看到的输出
== 第一幕：只访问 0、1、2 三个页 ==
访问页 0：缺失(miss)，从磁盘读入页框 0
访问页 1：缺失(miss)，从磁盘读入页框 1
访问页 2：缺失(miss)，从磁盘读入页框 2
访问页 0：命中(hit)，已在页框 0
访问页 1：命中(hit)，已在页框 1
访问页 2：命中(hit)，已在页框 2
== 第二幕：访问第 4 个页（页 3），谁会被踢出去？==
页框 0 里的旧页 0 干净，直接丢弃
访问页 3：缺失(miss)，从磁盘读入页框 0
== 第三幕：再访问页 0，它还在吗？==
页框 1 里的旧页 1 干净，直接丢弃
访问页 0：缺失(miss)，从磁盘读入页框 1
== 第四幕：连续访问 4~9，看 LRU 连环换出 ==
页框 2 里的旧页 2 干净，直接丢弃
访问页 4：缺失(miss)，从磁盘读入页框 2
页框 0 里的旧页 3 是脏页，写回磁盘
访问页 5：缺失(miss)，从磁盘读入页框 0
页框 1 里的旧页 0 干净，直接丢弃
访问页 6：缺失(miss)，从磁盘读入页框 1
页框 2 里的旧页 4 干净，直接丢弃
访问页 7：缺失(miss)，从磁盘读入页框 2
页框 0 里的旧页 5 干净，直接丢弃
访问页 8：缺失(miss)，从磁盘读入页框 0
页框 1 里的旧页 6 干净，直接丢弃
访问页 9：缺失(miss)，从磁盘读入页框 1对着输出检查三件事。第一，第一幕第二轮是不是全 hit。第二，第二幕页 0 是不是被踢了，第三幕页 0 回来是不是 miss。第三，第四幕第二行，页 3 是不是"脏页写回磁盘"，因为我们在第二幕把它的第一个字节改成了 X。三件都对，你的缓冲池就是对的。
跑完以后文件夹里会多出一个 data.db 文件，大小是 16384 字节，正好 4 页。这就是我们模拟的"磁盘"。想重新做实验，先删掉它再运行：rm data.db（Windows 资源管理器里删掉也行）。
报错诊所
错误一：把 const int PAGE_SIZE = 4096; 后面的分号忘了。报错 error: expected ',' or ';' before 'const' 或者指到下一行。老规矩，看报错行号的上一行。
错误二：f->data[0] = 'X'; 写成 f.data[0] = 'X';。f 是指针，指针用箭头 ->，对象用点 .。报错：
error: request for member 'data' in 'f', which is of pointer type 'Frame*' (maybe you meant to use '->' ?)编译器会直接提醒你"是不是想用 ->"，照着改就行。
错误三：include 少了 <cstring>，memset 就不认识，报错 error: 'memset' was not declared in this scope。改法：补上 include。
错误四：运行后发现没有 data.db 文件，或者行为很怪，每次都全 miss。检查你是不是在错误的文件夹里运行程序。程序在当前文件夹创建 data.db，用 ls 确认。
错误五：上一轮实验的 data.db 没删，文件里已经有内容了，行为会和教程输出对不上。改法：实验之间 rm data.db 清场。
小练习
把 POOL_SIZE 从 3 改成 4，重新编译运行。预测一下：第二幕访问页 3 时还会踢人吗？（不会，因为有空页框了。）踢人发生在第几幕？跑一遍验证你的预测。再试试把第一幕改成只访问页 0 三遍，看看输出变成什么样。
M4M4：迷你 B+树——会分裂的有序索引
这一步我们要做出什么
一棵真正的 B+树，阶数 4（每个结点最多 3 个键），支持插入、叶子分裂、点查、范围查询，还能按层打印树的形状。我们插入 1 到 20 这 20 个键，看它从小苗长成三层大树，然后范围查询 7 到 15。这是 BusTub Project 2 的迷你版。
为什么需要 B+树
固定套路。
朴素做法一：哈希表。点查飞快，但范围查询抓瞎。假设你要查"学号 100 到 200 的所有学生"，哈希表只能一个一个试 100、101、102……每个都是一次独立查找，而且别忘了 M1 里看到的，哈希表遍历顺序是乱的，它内部根本不是按学号排的。
朴素做法二：排好序的数组。范围查询爽了，二分查找定位起点，往右扫就行。但插入抓瞎：插一个中间位置的键，后面所有元素都要往后挪。假设 DeepSeek 的对话列表有一千万条记录，每发一条新消息要挪动几百万条，没人受得了。
机制：B+树。它是一棵又矮又胖的树，所有数据存在叶子结点，叶子之间用链表串起来。点查从根往下走，三层树只要跳三次。范围查询先走到 low 所在的叶子，然后顺着叶子链表往右扫，扫到 high 就停。插入满了就分裂，一个结点变两个，中间键上交。
具体数字钉死：我们的树 MAX_KEYS = 3，每个结点最多装 3 个键，装第 4 个就分裂。插入 1 到 20 之后，树会长成 1 个根、3 个内部结点、10 个叶子，共 3 层。
结点的两种形态
代码里只有一个 Node 结构，但它有两种用法：
- 叶子结点：keys 存键，values 存值，next 指向右边相邻的叶子。children 空着不用。
- 内部结点：keys 存路标，children 存孩子指针，路标 i 的意思是"大于等于 keys[i] 的往第 i+1 个孩子走"。values 空着不用。
真实数据库里两种结点分开定义，我们图简单合在一起，反正只省几个字段的内存。
新建文件
新建文件夹 m4_bplustree，新建 main.cpp，敲入全部内容（约 190 行）：
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
const int MAX_KEYS = 3; // 每个结点最多 3 个键（阶数 4），插满就分裂
struct Node {
bool is_leaf;
std::vector<int> keys;
// 叶子结点用：
std::vector<int> values;
Node* next = nullptr; // 叶子之间的链表指针，范围查询靠它
// 内部结点用：
std::vector<Node*> children;
};
class BPlusTree {
public:
BPlusTree() {
root_ = new Node;
root_->is_leaf = true;
}
void insert(int key, int value) {
Node* new_child = nullptr;
int new_key = 0;
if (insertRec(root_, key, value, new_child, new_key)) {
// 根分裂了，要长出一个新根，树加高一层
Node* new_root = new Node;
new_root->is_leaf = false;
new_root->keys.push_back(new_key);
new_root->children.push_back(root_);
new_root->children.push_back(new_child);
root_ = new_root;
std::cout << " （根结点分裂，树长高了）" << std::endl;
}
}
// 点查：返回是否找到，找到时把值放进 result
bool get(int key, int& result) const {
Node* leaf = findLeaf(key);
for (size_t i = 0; i < leaf->keys.size(); i++) {
if (leaf->keys[i] == key) {
result = leaf->values[i];
return true;
}
}
return false;
}
// 范围查询：打印 [low, high] 之间所有键值对
void rangeQuery(int low, int high) const {
Node* leaf = findLeaf(low);
std::cout << "范围查询 [" << low << ", " << high << "]：";
while (leaf != nullptr) {
for (size_t i = 0; i < leaf->keys.size(); i++) {
int k = leaf->keys[i];
if (k > high) {
std::cout << std::endl;
return;
}
if (k >= low) {
std::cout << k << "=" << leaf->values[i] << " ";
}
}
leaf = leaf->next; // 顺着叶子链表往右走，不用再回树上
}
std::cout << std::endl;
}
// 按层打印树形，每个结点打出它里面的键
void print() const {
std::cout << "---- 树的形状（每层一行）----" << std::endl;
std::queue<const Node*> q;
q.push(root_);
while (!q.empty()) {
int level_size = static_cast<int>(q.size());
for (int i = 0; i < level_size; i++) {
const Node* n = q.front();
q.pop();
std::cout << "[";
for (size_t j = 0; j < n->keys.size(); j++) {
if (j > 0) std::cout << ",";
std::cout << n->keys[j];
}
std::cout << "] ";
if (!n->is_leaf) {
for (Node* c : n->children) q.push(c);
}
}
std::cout << std::endl;
}
}
private:
// 从根往下找到 key 应该待的叶子
Node* findLeaf(int key) const {
Node* n = root_;
while (!n->is_leaf) {
size_t i = 0;
while (i < n->keys.size() && key >= n->keys[i]) i++;
n = n->children[i];
}
return n;
}
// 递归插入。返回 true 表示本结点分裂了，new_child/new_key 是要上交的新结点
bool insertRec(Node* node, int key, int value, Node*& new_child, int& new_key) {
if (node->is_leaf) {
auto pos = std::lower_bound(node->keys.begin(), node->keys.end(), key);
size_t i = pos - node->keys.begin();
if (pos != node->keys.end() && *pos == key) { // 键已存在就覆盖
node->values[i] = value;
return false;
}
node->keys.insert(pos, key);
node->values.insert(node->values.begin() + i, value);
} else {
size_t i = 0;
while (i < node->keys.size() && key >= node->keys[i]) i++;
Node* child_new = nullptr;
int child_key = 0;
if (insertRec(node->children[i], key, value, child_new, child_key)) {
// 孩子分裂了，把上交的键和新孩子插进来
node->keys.insert(node->keys.begin() + i, child_key);
node->children.insert(node->children.begin() + i + 1, child_new);
}
}
if (static_cast<int>(node->keys.size()) <= MAX_KEYS) return false;
// 键太多了，分裂成左右两个结点
Node* right = new Node;
right->is_leaf = node->is_leaf;
int mid = static_cast<int>(node->keys.size()) / 2;
if (node->is_leaf) {
// 叶子分裂：右半边的键值都搬走，中间键复制一份上交
right->keys.assign(node->keys.begin() + mid, node->keys.end());
right->values.assign(node->values.begin() + mid, node->values.end());
node->keys.resize(mid);
node->values.resize(mid);
right->next = node->next; // 接上叶子链表
node->next = right;
new_key = right->keys[0];
} else {
// 内部分裂：中间键上交（不进右边），右半边的键和孩子搬走
new_key = node->keys[mid];
right->keys.assign(node->keys.begin() + mid + 1, node->keys.end());
right->children.assign(node->children.begin() + mid + 1, node->children.end());
node->keys.resize(mid);
node->children.resize(mid + 1);
}
new_child = right;
return true;
}
Node* root_;
};
int main() {
BPlusTree tree;
std::cout << "== 插入 1 到 20 ==" << std::endl;
for (int k = 1; k <= 20; k++) {
std::cout << "插入键 " << k << std::endl;
tree.insert(k, k * 10);
}
std::cout << std::endl;
tree.print();
std::cout << std::endl << "== 点查 ==" << std::endl;
int v;
if (tree.get(7, v)) {
std::cout << "键 7 的值是 " << v << std::endl;
}
if (!tree.get(99, v)) {
std::cout << "键 99 不存在" << std::endl;
}
std::cout << std::endl << "== 范围查询 ==" << std::endl;
tree.rangeQuery(7, 15);
return 0;
}逐行讲解（挑重点讲）
BPlusTree() 构造函数：创建一棵空树。空树就是一个孤零零的叶子结点当根。
insert：调用递归函数 insertRec，如果根分裂了（返回 true），就造一个新根，左孩子是老根，右孩子是分裂出来的新结点，中间键放路标。这是 B+树长高的唯一方式：从顶上长，不是从底下长。所以 B+树永远是平衡的，所有叶子在同一层。
findLeaf：点查和范围查询都要先找到叶子。逻辑是循环：在当前内部结点里找第一个大于 key 的路标，往它左边那个孩子走。代码里 while (i < n->keys.size() && key >= n->keys[i]) i++; 就是找这个位置。
get：找到叶子后在叶子里面线性扫一遍。叶子最多 3 个键，扫起来不费事。
rangeQuery：精髓在最后一句 leaf = leaf->next;。定位到起点叶子之后，再也不碰树的上半部分了，纯走叶子链表。遇到大于 high 的键立刻收工。这就是为什么数据库的范围查询都用 B+树不用哈希表。
print：用队列做广度优先遍历（BFS，Breadth-First Search），一层一层打印。先记下本层有几个结点（level_size），打完这一层再换行。
insertRec：最复杂的方法，分三段。第一段，如果是叶子，用 std::lower_bound（二分查找，标准库自带）找到插入位置，插进去；键已存在就覆盖值。第二段，如果是内部结点，先找到该往哪个孩子走，递归插孩子，如果孩子分裂了，把上交的键和新孩子插进自己身体里。第三段，插完检查自己是不是也超编了，超了就分裂。
分裂的两种形态要看仔细。叶子分裂：4 个键从中间切，右半边 2 个搬走，中间键复制一份上交，注意是"复制"，叶子的键本身还留在右边叶子里。同时维护叶子链表：right->next 接上 node 原来的 next，node->next 指向 right，链表不断。内部分裂：中间键上交之后不进右边结点，它是路标，路标只指方向不存数据。这就是 B+树和 B 树的区别之一：B+树的内部结点不存数据，数据全在叶子。
编译命令和运行命令
g++ -std=c++17 -Wall -Wextra -o main main.cpp
./main你应该看到的输出
== 插入 1 到 20 ==
插入键 1
插入键 2
插入键 3
插入键 4
（根结点分裂，树长高了）
插入键 5
插入键 6
插入键 7
插入键 8
插入键 9
插入键 10
（根结点分裂，树长高了）
插入键 11
插入键 12
插入键 13
插入键 14
插入键 15
插入键 16
插入键 17
插入键 18
插入键 19
插入键 20
---- 树的形状（每层一行）----
[7,13]
[3,5] [9,11] [15,17,19]
[1,2] [3,4] [5,6] [7,8] [9,10] [11,12] [13,14] [15,16] [17,18] [19,20]
== 点查 ==
键 7 的值是 70
键 99 不存在
== 范围查询 ==
范围查询 [7, 15]：7=70 8=80 9=90 10=100 11=110 12=120 13=130 14=140 15=150 观察三件事。第一，插入键 4 时第一次根分裂，因为一个叶子最多装 3 个键，装第 4 个必须裂。第二，最终的树有三层：根是 [7,13]，意思是"小于 7 往左，7 到 12 往中，13 以上往右"。第三，叶子层正好 10 个结点，每个装 2 个键，从左到右严丝合缝排好序。范围查询把 7 到 15 一个不漏地打出来了，值是键的 10 倍（因为插入时我们存的值是 k*10）。
报错诊所
错误一：vector 的 insert 用错位置，写成 node->keys.insert(i, key)。vector 的 insert 要的是迭代器不是下标，报错一大堆模板错误。改法：node->keys.insert(node->keys.begin() + i, key)，begin() 加偏移量就是第 i 个位置。
错误二：递归函数忘写 return。insertRec 的所有路径都必须返回 true 或 false，否则编译器警告 warning: control reaches end of non-void function，运行行为不可预测。改法：检查每个 if 分支的尽头都有 return。
错误三：把 n->keys.size() 和 int 直接比较，比如 i < n->keys.size() 里 i 是 int。size() 返回的是无符号整数，编译器警告 warning: comparison of integer expressions of different signedness。我们的代码里用 size_t 类型的 i 或者 static_cast 转一下，就是躲这个坑。改法：把循环变量声明成 size_t。
错误四：叶子分裂时忘了接链表，漏掉 right->next = node->next; node->next = right;。程序编译能过，但范围查询会提前断掉，比如查 7 到 15 只打出 7、8。这是逻辑错误，编译器帮不了你，只能靠运行结果抓。改法：把链表那两行接回去。
小练习
把 MAX_KEYS 从 3 改成 5（也就是阶数 6），重新编译运行。预测：插入 1 到 20 之后树是几层？叶子结点有几个？跑一遍验证。再把插入循环改成 for (int k = 20; k >= 1; k--) 倒序插入，看看树的形状和正序插入一不一样，想想为什么。
M5M5：组装收官——索引和数据的第一次会师
这一步我们要做出什么
一个真正能查的迷你数据库。我们把 M3 的缓冲池、M4 的 B+树拼在一起：学生的"学号+成绩"记录存在磁盘文件的数据页里，由缓冲池管搬运；B+树当索引，记着"学号 -> 记录在第几页第几格"。录入 20 个学生，然后做两件事：按学号点查（走索引，只碰一个页），按分数段范围查（分数上没索引，只能一页一页全表扫描）。你会亲眼看到每一条查询走的路径，看到索引是怎么省事的，也看到缓冲池是怎么把重复访问变成命中的。
这一步没有新语法，全是组装。代码看着长，其实三分之二你已经在 M3、M4 敲过一遍了。
朴素做法失败
假设没有索引。你要查学号 19 的成绩，怎么办？只能把磁盘上的页一页一页读进来，一格一格看学号是不是 19。20 个学生占 5 个页，最坏要读 5 个页。2 亿条记录的真实系统里，这意味着几十万次磁盘读写，一次查询几秒钟。这就是全表扫描（Full Table Scan），数据一多就死。
反过来，假设没有缓冲池，只有索引。索引告诉你"学号 19 在页 4 第 2 格"，你每次都真去磁盘读页 4。查 100 次学号 19 就读 100 次磁盘。磁盘比内存慢十万倍，这也受不了。
所以真实数据库两个都要：索引负责"知道数据在哪"，缓冲池负责"热点数据留在内存"。这一步我们就把这两样拼起来，看它们怎么配合。
新建什么文件
在 m5_index_query 文件夹里新建 main.cpp，完整代码如下。DiskManager、BufferPool、BPlusTree 三部分和 M3、M4 几乎一样，只有打印语句精简了，B+树的 findLeaf 加了路径打印。真正的新内容是最后的 MiniDB 类和 main 函数。
#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <queue>
#include <unordered_map>
#include <vector>
const int PAGE_SIZE = 4096;
const int POOL_SIZE = 3;
const int RECORDS_PER_PAGE = 4; // 故意放小，20 个学生要占 5 个页
// ---------------- 磁盘管理器（同 M3） ----------------
class DiskManager {
public:
explicit DiskManager(const std::string& filename) {
file_.open(filename, std::ios::in | std::ios::out | std::ios::binary);
if (!file_.is_open()) {
file_.clear();
file_.open(filename, std::ios::out | std::ios::binary);
file_.close();
file_.open(filename, std::ios::in | std::ios::out | std::ios::binary);
}
}
void readPage(int page_id, char* buf) {
file_.seekg(static_cast<long>(page_id) * PAGE_SIZE);
file_.read(buf, PAGE_SIZE);
if (file_.gcount() < PAGE_SIZE) {
file_.clear();
std::memset(buf, 0, PAGE_SIZE);
}
}
void writePage(int page_id, const char* buf) {
file_.seekp(static_cast<long>(page_id) * PAGE_SIZE);
file_.write(buf, PAGE_SIZE);
file_.flush();
}
private:
std::fstream file_;
};
// ---------------- 缓冲池（同 M3，打印精简了） ----------------
struct Frame {
char data[PAGE_SIZE];
int page_id = -1;
bool dirty = false;
int pin_count = 0;
};
class BufferPool {
public:
explicit BufferPool(DiskManager* disk) : disk_(disk), frames_(POOL_SIZE) {}
Frame* fetchPage(int page_id) {
auto it = page_table_.find(page_id);
if (it != page_table_.end()) {
int fid = it->second;
frames_[fid].pin_count++;
touch(fid);
std::cout << " 缓冲池：页 " << page_id << " 命中" << std::endl;
return &frames_[fid];
}
int fid = findVictim();
evictIfNeeded(fid);
disk_->readPage(page_id, frames_[fid].data);
frames_[fid].page_id = page_id;
frames_[fid].dirty = false;
frames_[fid].pin_count = 1;
page_table_[page_id] = fid;
touch(fid);
std::cout << " 缓冲池：页 " << page_id << " 缺失，从磁盘读入" << std::endl;
return &frames_[fid];
}
void unpinPage(int page_id, bool is_dirty) {
auto it = page_table_.find(page_id);
if (it == page_table_.end()) return;
Frame& f = frames_[it->second];
if (f.pin_count > 0) f.pin_count--;
if (is_dirty) f.dirty = true;
}
private:
int findVictim() {
for (int i = 0; i < POOL_SIZE; i++) {
if (frames_[i].page_id == -1) return i;
}
for (auto rit = lru_.rbegin(); rit != lru_.rend(); ++rit) {
if (frames_[*rit].pin_count == 0) return *rit;
}
return -1;
}
void evictIfNeeded(int fid) {
Frame& f = frames_[fid];
if (f.page_id == -1) return;
if (f.dirty) {
disk_->writePage(f.page_id, f.data);
std::cout << " 缓冲池：脏页 " << f.page_id << " 写回磁盘" << std::endl;
}
page_table_.erase(f.page_id);
lru_.remove(fid);
f.page_id = -1;
}
void touch(int fid) {
lru_.remove(fid);
lru_.push_front(fid);
}
DiskManager* disk_;
std::vector<Frame> frames_;
std::unordered_map<int, int> page_table_;
std::list<int> lru_;
};
// ---------------- B+树（同 M4，findLeaf 加了路径打印） ----------------
const int MAX_KEYS = 3;
struct Node {
bool is_leaf;
std::vector<int> keys;
std::vector<int> values;
Node* next = nullptr;
std::vector<Node*> children;
};
class BPlusTree {
public:
BPlusTree() {
root_ = new Node;
root_->is_leaf = true;
}
void insert(int key, int value) {
Node* new_child = nullptr;
int new_key = 0;
if (insertRec(root_, key, value, new_child, new_key)) {
Node* new_root = new Node;
new_root->is_leaf = false;
new_root->keys.push_back(new_key);
new_root->children.push_back(root_);
new_root->children.push_back(new_child);
root_ = new_root;
}
}
bool get(int key, int& result) const {
Node* leaf = findLeaf(key, true);
for (size_t i = 0; i < leaf->keys.size(); i++) {
if (leaf->keys[i] == key) {
result = leaf->values[i];
return true;
}
}
return false;
}
private:
Node* findLeaf(int key, bool trace) const {
Node* n = root_;
int depth = 0;
while (!n->is_leaf) {
size_t i = 0;
while (i < n->keys.size() && key >= n->keys[i]) i++;
if (trace) {
std::cout << " 索引：第 " << depth << " 层结点 [";
for (size_t j = 0; j < n->keys.size(); j++) {
if (j > 0) std::cout << ",";
std::cout << n->keys[j];
}
std::cout << "]，走向第 " << i << " 个孩子" << std::endl;
}
n = n->children[i];
depth++;
}
return n;
}
bool insertRec(Node* node, int key, int value, Node*& new_child, int& new_key) {
if (node->is_leaf) {
auto pos = std::lower_bound(node->keys.begin(), node->keys.end(), key);
size_t i = pos - node->keys.begin();
if (pos != node->keys.end() && *pos == key) {
node->values[i] = value;
return false;
}
node->keys.insert(pos, key);
node->values.insert(node->values.begin() + i, value);
} else {
size_t i = 0;
while (i < node->keys.size() && key >= node->keys[i]) i++;
Node* child_new = nullptr;
int child_key = 0;
if (insertRec(node->children[i], key, value, child_new, child_key)) {
node->keys.insert(node->keys.begin() + i, child_key);
node->children.insert(node->children.begin() + i + 1, child_new);
}
}
if (static_cast<int>(node->keys.size()) <= MAX_KEYS) return false;
Node* right = new Node;
right->is_leaf = node->is_leaf;
int mid = static_cast<int>(node->keys.size()) / 2;
if (node->is_leaf) {
right->keys.assign(node->keys.begin() + mid, node->keys.end());
right->values.assign(node->values.begin() + mid, node->values.end());
node->keys.resize(mid);
node->values.resize(mid);
right->next = node->next;
node->next = right;
new_key = right->keys[0];
} else {
new_key = node->keys[mid];
right->keys.assign(node->keys.begin() + mid + 1, node->keys.end());
right->children.assign(node->children.begin() + mid + 1, node->children.end());
node->keys.resize(mid);
node->children.resize(mid + 1);
}
new_child = right;
return true;
}
Node* root_;
};
// ---------------- 迷你数据库：索引 + 缓冲池 + 磁盘 ----------------
class MiniDB {
public:
MiniDB() : disk_("students.db"), pool_(&disk_) {}
// 录入一个学生：写进数据页，再把"学号 -> 位置"写进索引
void addStudent(int id, int score) {
int loc = next_loc_++;
int page_id = loc / RECORDS_PER_PAGE;
int slot = loc % RECORDS_PER_PAGE;
Frame* f = pool_.fetchPage(page_id);
std::memcpy(f->data + slot * 8, &id, 4);
std::memcpy(f->data + slot * 8 + 4, &score, 4);
pool_.unpinPage(page_id, true); // 改过了，标脏
index_.insert(id, loc); // 索引记录位置
}
// 点查：走 B+树索引找到位置，再去缓冲池拿数据页
void queryById(int id) {
std::cout << "点查学号 " << id << "：" << std::endl;
int loc;
if (!index_.get(id, loc)) {
std::cout << " 索引里没有这个学号" << std::endl;
return;
}
int page_id = loc / RECORDS_PER_PAGE;
int slot = loc % RECORDS_PER_PAGE;
std::cout << " 索引：学号 " << id << " 在页 " << page_id << " 的第 " << slot << " 格" << std::endl;
Frame* f = pool_.fetchPage(page_id);
int sid, score;
std::memcpy(&sid, f->data + slot * 8, 4);
std::memcpy(&score, f->data + slot * 8 + 4, 4);
pool_.unpinPage(page_id, false);
std::cout << " 结果：学号 " << sid << "，数学 " << score << " 分" << std::endl;
}
// 分数范围查：分数上没有索引，只能一页一页全表扫描
void queryByScoreRange(int low, int high) {
std::cout << "范围查分数 " << low << "~" << high << "（分数没索引，全表扫描）：" << std::endl;
int total_pages = (next_loc_ + RECORDS_PER_PAGE - 1) / RECORDS_PER_PAGE;
for (int p = 0; p < total_pages; p++) {
Frame* f = pool_.fetchPage(p);
for (int s = 0; s < RECORDS_PER_PAGE; s++) {
int loc = p * RECORDS_PER_PAGE + s;
if (loc >= next_loc_) break;
int sid, score;
std::memcpy(&sid, f->data + s * 8, 4);
std::memcpy(&score, f->data + s * 8 + 4, 4);
if (score >= low && score <= high) {
std::cout << " 找到：学号 " << sid << "，数学 " << score << " 分" << std::endl;
}
}
pool_.unpinPage(p, false);
}
}
private:
DiskManager disk_;
BufferPool pool_;
BPlusTree index_;
int next_loc_ = 0;
};
int main() {
MiniDB db;
std::cout << "== 录入 20 个学生（学号 1~20）==" << std::endl;
int scores[20] = {135, 128, 142, 98, 150, 88, 120, 133, 145, 110,
95, 138, 102, 149, 118, 125, 90, 140, 108, 131};
for (int i = 0; i < 20; i++) {
db.addStudent(i + 1, scores[i]);
}
std::cout << std::endl << "== 三次点查：看索引带路、缓冲池加速 ==" << std::endl;
db.queryById(7);
db.queryById(19);
db.queryById(7); // 再查一次 7，这次页应该还在缓冲池里
std::cout << std::endl << "== 分数范围查 130~150：只能全表扫描 ==" << std::endl;
db.queryByScoreRange(130, 150);
return 0;
}逐行讲解（只讲新的部分）
DiskManager、BufferPool、BPlusTree 三个类你在 M3、M4 已经敲过一遍了，不重复讲。有两个小改动提一下。BufferPool 的打印语句变短了，因为这一步打印很多，长了刷屏。BPlusTree 的 findLeaf 多了一个参数 trace，为 true 时把"走到第几层、看到什么路标、拐向第几个孩子"打印出来，这样你能看见索引带路的全过程。
重点讲 MiniDB，它是组装者，手里握着三样东西：一个 DiskManager（磁盘）、一个 BufferPool（缓冲池）、一个 BPlusTree（索引）。
const int RECORDS_PER_PAGE = 4;。一条记录是"学号+成绩"，两个 int，一共 8 字节。一个 4096 字节的页本来能装 512 条，但那样 20 个学生全挤在一个页里，演示不出换页。所以我们故意规定每页只放 4 条，20 个学生占 5 个页，比缓冲池的 3 个页框多，戏才好看。真实数据库也是这个思路，只是数字大得多。
addStudent(int id, int score)，录入。分四步。第一步，int loc = next_loc_++;，给这个新学生分配一个全局流水号，第一个学生是 0，第二个是 1，以此类推。第二步，把流水号翻译成"第几页第几格"：page_id = loc / 4，slot = loc % 4。比如 loc 是 6，那就是页 1 的第 2 格。整数除法和取余，小学数学。第三步，找缓冲池要这个页，用 memcpy 把学号和成绩各 4 字节写进页里对应的位置，然后 unpin 并标脏——改了数据，这页将来要写回磁盘。memcpy 是内存拷贝（Memory Copy），因为它的参数是字节指针，我们要把 int 的 4 个字节原样搬过去。第四步，index_.insert(id, loc)，告诉索引：学号 id 的记录在流水号 loc 那里。注意，索引里存的不是成绩，是位置。索引是地图，不是货物本身。
queryById(int id)，点查。先问索引：index_.get(id, loc)。索引从根走到叶子，把流水号 loc 交回来，一路上打印它走过的每一层。然后把 loc 翻译成页号和格子号，找缓冲池要页，memcpy 把学号和成绩读出来，unpin（这次是读，不改，所以不标脏），打印结果。整个链条是：索引 -> 位置 -> 缓冲池 -> 数据。这就是数据库点查的标准路径。
queryByScoreRange(int low, int high)，按分数范围查。关键：我们的 B+树索引是建在学号上的，分数上没有索引。所以没法走索引，只能全表扫描：从页 0 到最后一页，一页一页找缓冲池要，一页一页翻格子，分数在范围内的就打印。这个方法的存在就是为了让你看到反差：点查只碰 1 个页，范围查要碰全部 5 个页。真实数据库遇到这种查询，要么建二级索引（Secondary Index），要么硬着头皮扫。
int next_loc_ = 0;。成员变量初始值，C++11 起允许这样直接写在声明里。
main 函数。先建 MiniDB，然后录入 20 个学生，学号 1 到 20，成绩写死在一个数组里——学号 1 是 135 分（你可以想象他就是小明），学号 5 是满分 150。然后三次点查：查 7，查 19，再查一次 7。最后范围查 130 到 150 分。
编译命令和运行命令
老规矩：
g++ -std=c++17 -Wall -Wextra -o main main.cpp
./main如果你之前跑过这个程序，文件夹里可能有旧的 students.db，先 rm students.db 清场再跑，输出才和教程一致。
你应该看到的输出
== 录入 20 个学生（学号 1~20）==
缓冲池：页 0 缺失，从磁盘读入
缓冲池：页 0 命中
缓冲池：页 0 命中
缓冲池：页 0 命中
缓冲池：页 1 缺失，从磁盘读入
缓冲池：页 1 命中
缓冲池：页 1 命中
缓冲池：页 1 命中
缓冲池：页 2 缺失，从磁盘读入
缓冲池：页 2 命中
缓冲池：页 2 命中
缓冲池：页 2 命中
缓冲池：脏页 0 写回磁盘
缓冲池：页 3 缺失，从磁盘读入
缓冲池：页 3 命中
缓冲池：页 3 命中
缓冲池：页 3 命中
缓冲池：脏页 1 写回磁盘
缓冲池：页 4 缺失，从磁盘读入
缓冲池：页 4 命中
缓冲池：页 4 命中
缓冲池：页 4 命中
== 三次点查：看索引带路、缓冲池加速 ==
点查学号 7：
索引：第 0 层结点 [7,13]，走向第 1 个孩子
索引：第 1 层结点 [9,11]，走向第 0 个孩子
索引：学号 7 在页 1 的第 2 格
缓冲池：脏页 2 写回磁盘
缓冲池：页 1 缺失，从磁盘读入
结果：学号 7，数学 120 分
点查学号 19：
索引：第 0 层结点 [7,13]，走向第 2 个孩子
索引：第 1 层结点 [15,17,19]，走向第 3 个孩子
索引：学号 19 在页 4 的第 2 格
缓冲池：页 4 命中
结果：学号 19，数学 108 分
点查学号 7：
索引：第 0 层结点 [7,13]，走向第 1 个孩子
索引：第 1 层结点 [9,11]，走向第 0 个孩子
索引：学号 7 在页 1 的第 2 格
缓冲池：页 1 命中
结果：学号 7，数学 120 分
== 分数范围查 130~150：只能全表扫描 ==
范围查分数 130~150（分数没索引，全表扫描）：
缓冲池：脏页 3 写回磁盘
缓冲池：页 0 缺失，从磁盘读入
找到：学号 1，数学 135 分
找到：学号 3，数学 142 分
缓冲池：页 1 命中
找到：学号 5，数学 150 分
找到：学号 8，数学 133 分
缓冲池：脏页 4 写回磁盘
缓冲池：页 2 缺失，从磁盘读入
找到：学号 9，数学 145 分
找到：学号 12，数学 138 分
缓冲池：页 3 缺失，从磁盘读入
找到：学号 14，数学 149 分
缓冲池：页 4 缺失，从磁盘读入
找到：学号 18，数学 140 分
找到：学号 20，数学 131 分这段输出值得逐段读，它把整篇教程的知识串起来了。
录入阶段。每个页装 4 个学生，所以每 4 个人里，第 1 个人触发 miss（页不在池子里），后 3 个人全 hit。录到第 13 个人时要用页 3 了，池子满了（页 0、1、2），LRU 踢掉最久没用的页 0——它是脏的（我们往里写过学生），所以先写回磁盘，再读页 3。这就是 M3 学的整套机制在真实录入流程里自动发生。
点查阶段。查学号 7，索引走两层：根 [7,13] 告诉他往中间孩子走，[9,11] 告诉他往第 0 个孩子走，叶子里的答案是"页 1 第 2 格"。然后缓冲池去拿页 1——不巧，页 1 刚才被踢出去了（录最后几个学生时池子装不下），所以 miss，顺便把脏页 2 写回。第二次查 19，页 4 还在池子里，命中，零磁盘读。第三次又查 7，这次页 1 还在，命中。看到没有，同样的查询，第二次就是比第一次快，这就是缓冲池存在的意义。真实系统里这个差距是内存 100 纳秒对磁盘 10 毫秒，十万倍。
范围查阶段。5 个页全部过了一遍，一个不漏。注意它找出了 9 个学生，包括 150 分的学号 5。你可以拿笔验证：数组里 130 到 150 的分数确实是这 9 个。
到这里，你的迷你数据库内核完工了。磁盘、页、缓冲池、LRU、脏页写回、B+树、点查、范围查、全表扫描，数据库系统课上半学期的东西，你亲手跑通了一遍。
报错诊所
错误一：memcpy 报错 'memcpy' was not declared in this scope。少了 #include <cstring>。补上。
错误二：把 RECORDS_PER_PAGE 写成了 RECORD_PER_PAGE 之类，编译报 error: 'RECORD_PER_PAGE' was not declared in this scope。常量名复制粘贴最稳，别手敲长名字。
错误三：addStudent 里写成了 f.data 而不是 f->data。fetchPage 返回的是指针 Frame*，指针访问成员用箭头。报错会提示 maybe you meant to use '->'，照改。
错误四：运行结果和教程对不上，比如脏页写回的位置不对。多半是上次运行留下的 students.db 没删，旧的页内容混进来了。rm students.db 再跑。
错误五：把 index_.insert(id, loc) 写成了 index_.insert(id, score)。编译能过，因为都是 int，但点查时会把分数当流水号去算页号，查出莫名其妙的野数据。这是逻辑错误，编译器救不了你。记住：索引存的是位置 loc，不是成绩 score。写代码时给变量起有意义的名字，就是为了少犯这种错。
小练习
练习一：把 POOL_SIZE 从 3 改成 5，重新跑。预测：录入阶段还会有脏页写回吗？点查学号 7 时页 1 还会 miss 吗？跑一遍验证。
练习二：给 queryById 加一行统计：在方法开头加一个静态计数器 static int query_count = 0; query_count++;，把"这是第几次查询"打印出来。然后点查 10 次，看看 hit 和 miss 的比例变化。
练习三（挑战）：给分数也建一个 B+树索引。注意分数会重复（两个学生可以同分），我们现在的 B+树假设键唯一。想一想怎么改，或者在分数索引的叶子里存"分数 -> 学号列表"。做不出来没关系，能把困难点说清楚就已经超过大多数面试者了。
收官：你的迷你版和真 BusTub 的差距地图
先祝贺你。六个里程碑走完，你手上有一个 300 行、能编译、能跑、能讲清楚每一行在干什么的迷你数据库内核。
但面试的时候，面试官一定会追问：这和真的数据库差在哪？你不能支支吾吾，要答得上来。差距主要四块。
第一块：替换策略。我们用的是最朴素的 LRU，最近最少使用。真 BusTub 用的是 LRU-K，它记录每个页最近 K 次访问的时间，踢的是"第 K 近那次访问最古老"的页。为什么？因为纯 LRU 怕全表扫描：扫一遍大表，会把池子里所有热点页都冲掉，而扫描来的页其实只读一次，再也不用了。LRU-K 能识别这种"一次性"访问，保护真正的热点。
第二块：并发。我们的缓冲池假设同一时间只有一个人在用。真数据库有几百个连接同时查，两个线程同时抢一个页框怎么办？BusTub 要求你用 latch（闩锁，数据库界对内部短锁的叫法）保护页表和每个页，还要处理死锁。这是 P1 缓冲池项目里最掉头发的部分。
第三块：执行器。我们只会"点查"和"全表扫描"两种查询。真数据库要执行任意 SQL，比如 SELECT、JOIN、GROUP BY。BusTub 的 P3 就是写一堆执行器（Executor）：SeqScan、IndexScan、NestedLoopJoin、Aggregation，用火山模型（Volcano Model）一串，每个算子只管吐下一行。
第四块：事务。两个人同时改同一个学生的成绩怎么办？真数据库用两阶段锁（Two-Phase Locking，2PL）和 MVCC（Multi-Version Concurrency Control，多版本并发控制）保证 ACID（原子性、一致性、隔离性、持久性）。BusTub 的 P4 就是干这个。
你看，我们不是白忙。你的迷你版骨架和真 BusTub 一模一样，差的只是每一块上的工业强度。面试时把这张差距地图讲出来，比假装自己全懂要加分得多。
简历上怎么写这一段
简历写项目，忌讳写"学习过""了解过"，要写你做了什么、做到了什么、有数字。给你一个可以直接改的模板：
"独立实现迷你数据库内核（C++17，约 600 行）：以文件模拟磁盘按 4KB 页读写；实现 3 页框缓冲池，含页表哈希索引、LRU 替换、pin/unpin 引用计数与脏页延迟写回；实现阶数 4 的 B+树索引，支持插入、结点分裂、点查与基于叶子链表的范围查询；组装为迷你数据库，学号点查经索引仅访问 1 个数据页，分数范围查询退化为全表扫描，复现了真实数据库的索引加速与缓存命中行为。"
里面每个词你都要能解释。面试官指着"pin/unpin 引用计数"问你，你就讲 M3 里 pin_count 大于 0 的页不许换出的故事。指着"脏页延迟写回"问你，你就讲第二幕那个被写成 X 的页 3 后来在第四幕被写回磁盘的故事。你亲手跑过，你就有故事讲，这就是动手和纯看书的区别。
下一步：怎么啃真 BusTub
真 BusTub 是 CMU 15-445 的课程项目，代码量上万行，直接跳进去会淹死。按这个顺序来。
先做 Project 0，写一个简单的并发字典（Copy-on-Write Trie）。它的目的是让你熟悉代码库、googletest 测试框架和提交评测的流程，不难，别跳过。
然后 Project 1 缓冲池。你已经有感觉了：LRU-K 替换器、磁盘调度器、缓冲池管理器三件。把你的迷你版放在旁边对照着写，你会发现结构是一样的，只是每处多了并发保护。
接着 Project 2 是 B+树。同样，你的迷你版已经包含插入和分裂的主干逻辑。真的版本难在删除（合并和重分配）和并发（latch crabbing，蟹行锁协议，从根往下走，确认安全就释放上面的锁）。
Project 3 执行器和 Project 4 并发控制是纯新内容，到时候配合 CMU 的公开课录像啃。
刷项目的方法论就一条，也是这篇教程一直在演示的：先让最小版本跑起来，再往里加复杂度。别一上来就想写全功能。
面试话术：被问"你亲手写过缓冲池吗"
面试官："你简历上写实现了缓冲池，说说？"
你可以这样答："我按 CMU 15-445 的思路写过一个迷你缓冲池。磁盘用一个文件模拟，按 4KB 页读写。池子里 3 个页框，一张哈希表做页号到页框的映射，一条双向链表维护 LRU 顺序。fetch 时命中就 pin 计数加一并挪到链表头；缺失就找空框或者从链表尾踢一个 pin 计数为 0 的牺牲页，牺牲页是脏的就先写回磁盘。我做过一个演示：反复访问 3 个页时全部命中，访问第 4 个页时最久没用的页被踢出，脏页在踢出时自动写回。我知道工业实现和我的差距主要在 LRU-K 防扫描污染和并发 latch 上，这两点我也在 BusTub 的 Project 1 里继续练过。"
这段话的杀手锏在最后一句：你主动说出了自己的边界。说自己会的，承认差距，指出补课路线。这比吹一个你兜不住的牛要强一百倍。
最后一句
你从今天起不再是"读过数据库概念的人"，你是"写出过缓冲池和 B+树的人"。这个区别，简历看得出来，面试官看得出来，你自己心里最清楚。
去把 M0 到 M5 再独立敲一遍，不看教程。敲不出来就回到对应里程碑再读一遍。能独立敲出来那天，你就可以开 BusTub 的 Project 0 了。