从零实现关系型数据库内核：存储引擎、查询优化与事务管理的工程实践

简介：本资源是全国大学生计算机系统能力大赛数据库管理系统赛道的完整参赛项目，面向系统能力培养导向的高校本科生与研究生，聚焦关系型数据库内核开发实践。项目基于RMDB框架实现了一套支持TPC-C基准测试的轻量级RDBMS，覆盖存储引擎、查询优化器、事务管理等核心模块，可作为数据库原理课程设计、系统级编程实训及竞赛备赛的高质量参考方案。压缩包共442个文件（2.43MB），含121个C/C++头文件（h/hpp）与146个源码文件（cc/cpp/c）、47个Python脚本（用于测试与工具链）、30个Markdown文档（含设计说明与接口规范）、11个CMake/Bazel构建配置文件，以及PDF技术报告和CSV测试数据等，目录结构体现典型DBMS分层架构。已有70人学习下载，读者可直接复现编译环境、剖析关键算法实现（如B+树索引、基于代价的连接优化）、运行TPC-C负载验证性能，并参考配套文档理解从SQL解析到物理执行的全链路设计逻辑。

1. 项目概述：从零构建一个“能跑”的关系型数据库

如果你是一名计算机专业的学生，或者对数据库底层技术充满好奇，那么“自己动手写一个数据库”这个想法，大概率在你脑海里闪现过。它听起来既酷炫又遥不可及，仿佛是系统软件领域的皇冠。全国大学生计算机系统能力大赛数据库管理系统赛道，就是为有这样想法的同学准备的顶级舞台。这个项目，正是我们团队为参赛而开发的一个完整的关系型数据库管理系统（RDBMS）。它不是玩具，而是一个从存储引擎、查询优化器到事务管理，内核功能齐全，并且能通过标准工业级基准测试TPC-C验证的系统。

简单来说，我们的目标不是重复造一个MySQL或PostgreSQL，而是在有限的时间和资源下，深入理解一个现代数据库内核的骨架与灵魂。我们选择了基于RMDB这个教学/研究型框架进行深度开发。RMDB提供了一个不错的起点，它定义了模块接口和基础架构，但真正的“血肉”——如何高效地组织数据、如何聪明地执行查询、如何保证数据在并发下的正确性——都需要我们亲手填充。最终，我们实现了一个支持标准SQL子集、具备ACID事务特性、并能承受TPC-C这种复杂OLTP负载考验的数据库系统。这个过程，就像是在导师提供的汽车底盘上，自己设计发动机、变速箱和控制系统，最后让它真正跑起来，甚至去赛道上测个速。接下来，我将详细拆解我们是如何一步步完成这个挑战的。

2. 核心架构设计与技术选型思路

当我们决定基于RMDB框架开发时，首先需要吃透它的架构，并在此基础上做出我们的技术决策。RMDB采用了经典的分层架构，这为我们清晰地划分了工作模块。

2.1 为什么选择RMDB框架？

市面上教学用的数据库框架不止一个，比如CMU的BusTub、Stanford的SimpleDB。我们选择RMDB，主要基于几点考量。首先，它的代码结构清晰，模块耦合度相对较低，每个核心组件（如StorageManager，Executor，Planner）的接口定义明确，这非常有利于团队分工。其次，RMDB使用C++编写，这让我们能更贴近工业级数据库（如MySQL、SQLite）的实现语言，对内存管理、性能优化有更直接的掌控感，同时也避免了Java等语言GC带来的不确定性对性能测试的影响。最后，RMDB的社区和配套资料在国内相对丰富，遇到深层次问题时有更多可参考的解决方案。

但RMDB只是一个骨架。它提供了磁盘I/O的抽象、缓冲池的基本管理、记录格式的定义，以及查询执行的大致流程。而真正的难点在于：缓冲池替换策略用什么算法？数据在磁盘上用什么结构组织（堆文件、B+树）？查询优化器基于什么规则进行等价变换和代价估算？事务管理器如何实现锁或多版本并发控制（MVCC）？这些都需要我们做出独立的设计和实现。

2.2 整体系统架构拆解

我们的系统最终呈现为以下核心模块的协同工作：

1. 存储管理层：这是系统的基石。负责管理数据在磁盘上的持久化存储。我们实现了基于缓冲池（Buffer Pool）的磁盘数据缓存机制，并在此基础上构建了两种主要的存储引擎结构：用于顺序存储的堆文件（Heap File）和用于高效索引的B+树。这一层直接决定了数据存取的效率。
2. 查询处理层：这是系统的“大脑”。它接收SQL语句，经过解析器（Parser）生成抽象语法树（AST），然后由查询优化器（Optimizer）进行重写、选择执行路径，生成最优的物理执行计划，最后由执行器（Executor）调用存储层的接口，逐行处理数据。优化器是我们投入精力最多的模块之一。
3. 事务管理层：这是系统的“安全卫士”。它确保数据库的ACID特性。我们实现了基于锁的并发控制协议（两阶段锁，2PL）和Write-Ahead Logging（WAL）日志机制，来保证事务的原子性、一致性和隔离性。恢复管理器则基于WAL日志在系统崩溃后恢复数据一致性。
4. TPC-C驱动与测试层：这不是数据库内核的一部分，但却是项目的“验收官”。我们实现了TPC-C基准测试的标准驱动程序，模拟一个批发公司的业务负载（新建订单、支付、订单状态查询等），持续对数据库施加压力，并最终收集衡量性能的指标tpmC（每分钟完成的事务数）。

这个架构决定了我们的开发路线图：先让存储引擎稳定读写，再让执行器能跑通简单查询，接着优化器提升复杂查询效率，然后事务管理器保证并发正确性，最后用TPC-C验证整体性能和稳定性。每一步都环环相扣。

3. 存储引擎：数据如何被高效地放置与查找

存储引擎是数据库的“仓库管理员”，它的设计直接决定了数据存取的性能。我们的核心工作是实现了缓冲池管理、堆文件组织和B+树索引。

3.1 缓冲池：在内存与磁盘之间架起高速桥梁

数据库的数据远大于内存容量，因此需要一个智能的缓存系统。缓冲池就是一块固定的内存区域，用于缓存从磁盘读出的数据页（Page）。我们的实现关键点在于：

• 页面置换算法：当缓冲池满时，需要淘汰一个旧页面。我们对比了LRU（最近最少使用）和Clock算法。LRU实现简单，但对顺序扫描（全表扫描）不友好，会污染缓存。我们最终实现了改进版的LRU-K算法，它不只记录最近一次访问，而是记录最近K次访问的历史，能更好地区分“热点数据”和“一次性扫描数据”，在TPC-C的混合负载下表现更稳定。
• 钉住（Pin）与脏页（Dirty Page）：执行器在读取或修改一个页面时，必须“钉住”它，防止被置换出去。修改后的页面标记为“脏”，由后台线程或检查点机制定期刷回磁盘。这里的一个关键细节是，我们严格管理了pin_count和dirty标志，确保线程安全，避免一个正在被事务修改的页面被意外淘汰。
• 预取（Prefetching）：对于顺序扫描操作，我们实现了简单的顺序预取。当执行器请求第N页时，缓冲池管理器会异步地将第N+1, N+2页也加载到缓冲池中，有效减少了I/O等待。

实操心得：缓冲池的调试陷阱。初期我们曾遇到一个诡异的“数据消失”问题：事务提交后，再次查询数据有时会丢失。排查了很久，最终发现是在某个错误处理分支中，页面被修改后没有正确标记为dirty，导致刷盘时漏掉了这个页面。教训是：所有修改页面的操作，必须在同一原子操作中递增pin_count和设置dirty标志，并且要有完善的单元测试覆盖所有异常路径。

3.2 堆文件与B+树：两种核心数据组织方式

• 堆文件（Heap File）：这是最简单的存储方式，数据记录按插入顺序依次存放。我们使用一个“空闲空间映射”来快速找到有空间插入新记录的页面。堆文件的优势是插入极快（O(1)），但根据条件查找特定记录需要全表扫描（O(n)）。它适合数据仓库中追加式的批量加载，或者作为没有索引的表的底层存储。
• B+树索引：这是数据库索引的绝对核心。我们实现了典型的B+树结构，支持等值查找、范围查找和有序遍历。叶子节点存储键值（Key）和记录ID（RID），内部节点存储导航键。实现难点包括：
  • 分裂与合并：当节点满时需分裂，当节点元素过少时需与兄弟节点合并或重新分配。这些操作必须保证树的平衡，并且是原子性的，我们通过精心设计页面操作顺序和WAL日志来保证。
  • 并发控制：B+树的并发访问非常频繁。我们实现了Crabbing Protocol（蟹行协议）的变种。搜索时从根到叶子一路共享锁（S锁），仅在需要修改的叶子节点才升级为排他锁（X锁）；插入/删除时，从根向下，在可能发生分裂/合并的路径节点上使用排他锁，但范围控制得尽可能小，以减少锁冲突。这比直接锁整棵树效率高得多。

为什么选择B+树而不是B树或哈希？B+树所有数据都在叶子节点，且叶子节点链表连接，这使得范围查询和全键值顺序遍历的效率极高，非常适合数据库最常见的“WHERE ... BETWEEN ...”和“ORDER BY”场景。哈希索引虽然等值查询是O(1)，但无法支持范围查询。B树的数据可能在任何节点，遍历不如B+树高效。因此，B+树在关系型数据库中成为了索引的默认选择。

4. 查询优化器：让SQL执行从“蛮干”到“巧干”

如果没有优化器，执行器可能会用最笨的方式执行查询。例如，SELECT * FROM A, B WHERE A.id = B.a_id AND A.name = ‘foo‘，可能会先对A做全表扫描找出所有name=‘foo‘的记录，然后对每一条记录再去B表做全表扫描找匹配的a_id。如果表很大，这就是灾难。优化器的任务就是把这种“蛮干”计划，变成“巧干”计划。

4.1 优化器的核心工作流程

我们的优化器遵循经典的Volcano/Cascades风格模型，分为几个阶段：

1. 语法分析与生成初始逻辑计划：解析器将SQL变成语法树，然后转换成初始的关系代数表达式树（如Select, Project, Join, Scan）。
2. 逻辑优化：基于关系代数等价规则，对表达式树进行重写，目标是减少中间结果集的大小。我们实现了以下常见规则：
   • 谓词下推：尽早执行选择（Select）操作，把过滤条件A.name = ‘foo‘推到连接（Join）之前，减少参与连接的数据量。
   • 投影下推：尽早执行投影（Project）操作，只取出后续计算需要的列，减少数据在内存中的体积。
   • 连接重排序：对于多表连接（A JOIN B JOIN C），连接顺序不同，产生的中间结果大小天差地别。我们实现了基于动态规划的连接顺序优化算法，估算每种连接顺序的代价，选择代价最小的。
3. 物理优化与代价估算：为逻辑计划中的每个操作符选择具体的物理实现算法，并估算其代价。这是最核心也最困难的部分。
   • 代价模型：我们建立了一个简单的代价模型：Cost = CPU_Cost + I/O_Cost。I/O成本占主导，我们主要计算需要读写的页面数。为此，系统需要维护表的统计信息，包括总行数、每列的不同值数量（基数）、最大值、最小值等。这些信息通过ANALYZE命令定期收集。
   • 选择率估算：对于WHERE col = value这样的条件，优化器需要估算满足条件的行数占总行数的比例。我们假设数据均匀分布，利用列基数来估算：选择率 ≈ 1 / NDV(col)。对于范围查询，则利用最大值最小值来估算。
   • 连接算法选择：对于Join操作，我们实现了三种物理算法，优化器根据情况选择：
     • 嵌套循环连接：适用于小表驱动大表，或者有索引可用的情况。
     • 哈希连接：适用于内存能装下其中一张表（或分区）的情况，它是等值连接效率最高的算法之一。我们实现了Grace Hash Join，当表太大时进行分区落盘。
     • 排序合并连接：当输入数据已经有序，或者需要输出有序结果时很有优势。
4. 生成最终执行计划：经过以上步骤，得到一棵附带了具体算法和代价估算的物理执行计划树，交给执行器去执行。

4.2 一个优化实例分析

假设查询：SELECT * FROM orders, customer WHERE orders.c_id = customer.id AND customer.credit = ‘good‘。

• 糟糕的计划：全表扫描customer，对每一行credit=‘good‘的记录，全表扫描orders找匹配的c_id。代价是|customer| + |good_customer| * |orders|次页面I/O。
• 优化后的计划：
  1. 谓词下推：先对customer表执行credit=‘good‘的选择操作，得到一个小的结果集good_cust。
  2. 连接重排序与算法选择：现在连接good_cust和orders。因为good_cust很小，优化器可能选择以它为构建表，orders为探测表，进行哈希连接。如果orders在c_id上有B+树索引，也可能选择索引嵌套循环连接，即遍历good_cust，每次用c_id去索引中快速查找orders记录。
  3. 最终，代价可能降低为：扫描customer表的代价 + 构建good_cust哈希表的代价 + 扫描orders表一次的代价（哈希连接）或|good_cust|次索引查找的代价。

注意事项：统计信息的重要性与局限性。优化器的好坏极度依赖统计信息的准确性。如果统计信息过时（例如，customer表刚插入大量credit=‘bad‘的记录，但统计信息显示credit分布均匀），优化器可能会严重误判选择率，选出糟糕的计划。因此，在TPC-C测试前，我们必须对测试表执行ANALYZE。此外，我们的简单代价模型无法考虑CPU缓存命中率、顺序I/O与随机I/O的差异等更复杂的硬件因素，这是一个可以继续深化的方向。

5. 事务管理与恢复：保障数据的“金科玉律”

数据库事务必须满足ACID特性，我们通过锁管理器（Lock Manager）和预写日志（WAL）两大组件来实现。

5.1 基于锁的并发控制

我们实现了严格的**两阶段锁（2PL）**协议：事务在释放任何一个锁之后，就不能再申请任何新的锁。这保证了可串行化隔离级别。锁管理器维护一个全局的锁表，记录每个资源（我们以RID，即记录ID，为粒度）上的锁信息。

• 锁的升级与等待：事务T1持有R1的共享锁(S锁)，事务T2也想获得R1的排他锁(X锁)进行修改，T2必须等待。锁管理器处理这种等待队列，防止饿死。当T1释放锁后，唤醒等待队列中的T2。
• 死锁检测与处理：我们采用周期性的死锁检测而非预防。维护一个“等待图”（Wait-for Graph），节点是事务，边表示T1正在等待T2占用的资源。定期运行一个后台线程检测图中是否有环。一旦发现死锁，选择一个“代价最小”的事务（如修改数据最少的事务）进行回滚（Abort），释放其所有锁，从而打破死锁。
• 锁粒度：我们主要实现了记录级锁，这对OLTP的TPC-C负载比较合适。也在表级提供了意向锁（IS, IX），用于在B+树遍历时快速判断子树是否可能被上锁，提高效率。

5.2 预写日志与恢复

为了保证原子性和持久性，我们实现了Write-Ahead Logging。其核心原则是：任何数据页面的修改必须在页面本身被写回磁盘之前，先将其对应的日志记录持久化到磁盘上的日志文件中。

• 日志格式：每条日志记录包含唯一LSN（日志序列号）、事务ID、日志类型（Update, Commit, Abort等）、修改的前像（Before-Image）和后像（After-Image）。
• 提交协议：事务提交时，并不立即将所有修改的脏页刷盘（这很慢），而是只需强制写入一条COMMIT日志记录到磁盘。只要这条日志落盘，事务就算持久化提交了。脏页由后台的检查点（Checkpoint）线程异步刷回。
• 恢复过程：系统崩溃重启后，恢复管理器启动，扫描日志文件：
  1. 重做阶段（Redo）：从最后一个检查点开始，正向扫描日志，对所有日志（包括已提交和未提交事务），根据后像重新执行一遍操作。这保证了已提交事务的修改不会丢失（即使脏页没刷盘）。
  2. 撤销阶段（Undo）：反向扫描日志，对所有在崩溃时未提交的事务，根据前像执行反向操作，回滚所有修改。这保证了未提交事务的修改不会残留。

我们实现了ARIES恢复算法的简化版，支持逻辑Undo和检查点，使得恢复过程更快、更健壮。

踩坑实录：日志序列号与页面LSN的同步。在实现WAL时，我们曾遇到一个棘手的Bug：系统恢复后，某些已提交事务的修改丢失了。经过逐条日志分析，发现是在写日志记录和更新数据页面pageLSN（页面最后修改的日志号）时，顺序出了问题。正确的顺序必须是：1) 在内存中组装好日志记录；2) 将日志记录写入日志缓冲区；3)更新内存中页面的pageLSN；4) 修改页面内容。如果步骤3和4颠倒，可能在页面修改后、pageLSN更新前发生崩溃，导致恢复时误认为这个页面的修改已经持久化（因为其pageLSN小于日志中的LSN），从而跳过重做，造成数据丢失。这个细节对保证恢复的正确性至关重要。

6. TPC-C基准测试：工业级的压力检验

实现所有内核功能后，我们需要一个公正的“考官”来检验系统的成色。TPC-C是事务处理性能委员会制定的经典OLTP基准测试，模拟了一个批发公司的业务，包含5种事务类型和9张表，非常复杂且贴近真实场景。

6.1 TPC-C负载特性与我们的适配

TPC-C的核心指标是tpmC（Transactions per Minute, C），即系统每分钟能完成多少个“新订单”事务。它强调系统的整体吞吐量和响应时间。其负载特点包括：

• 混合读写：包含插入（新订单）、更新（支付）、删除（交付）和复杂查询（订单状态、库存水平）。
• 高并发：模拟多个终端同时操作。
• 数据争用：热点数据（如最后一个仓库的库存）访问频繁，对并发控制机制是严峻考验。

我们的测试驱动程序严格按照TPC-C规范实现：

1. 建表与数据加载：生成符合规模要求的初始数据（例如，配置了10个仓库的数据）。
2. 事务混合：以特定比例随机执行5种事务（新订单约45%，支付约43%等）。
3. 键值生成：遵循规范要求的非均匀分布（如大部分订单访问本地仓库）。
4. 度量与报告：持续运行一段时间（如2小时），收集吞吐量（tpmC）和平均/百分位响应时间。

6.2 性能调优实战

在初始测试中，我们的tpmC值很低。通过性能剖析（Profiling），我们发现了瓶颈并逐一优化：

• 瓶颈一：锁竞争激烈。在“支付”事务中，需要更新仓库和地区的销售总额（YTD），这两条记录是全局热点。我们最初使用记录锁，导致大量事务串行等待。
  • 优化：对于这种“读-修改-写”的计数器更新模式，我们引入了增量更新和延迟合并。事务只在日志中记录增量（如+10），而不直接更新主数据页。后台线程定期合并增量。这大大减少了热点记录上的排他锁持有时间。当然，这增加了读操作的复杂度（需要读主数据并累加所有未合并的增量），但在TPC-C以更新为主的负载下收益显著。
• 瓶颈二：日志刷盘成为瓶颈。每个事务提交都要强制刷日志，I/O等待高。
  • 优化：实现了组提交。将短时间内多个事务的提交日志在一次性I/O中刷入磁盘，摊薄了每次刷盘的开销。
• 瓶颈三：B+树索引分裂频繁。在大量插入下，主键索引分裂导致页面锁升级和额外I/O。
  • 优化：采用了B+树的分裂预分配策略。在新建索引或插入非常频繁时，提前分配好一批空的叶子页面，形成一个“缓冲带”，减少分裂的即时开销。

经过多轮调优，我们的系统tpmC得到了数倍的提升。这个过程让我们深刻体会到，数据库性能是设计、算法和工程细节共同作用的结果。

7. 开发历程中的典型问题与排查心法

在长达数月的开发中，我们遇到了无数问题。这里分享几个最具代表性的案例和排查思路。

7.1 问题一：查询结果偶尔不正确，但非必现

• 现象：一个简单的等值查询，在并发测试时，偶尔会多返回或少返回一行数据。
• 排查：
  1. 隔离怀疑对象：首先在单线程下测试，问题不复现，初步判断是并发控制问题。
  2. 日志分析：增加了事务操作和加锁的详细日志。发现异常出现时，两个事务对同一范围的数据加锁顺序出现了交叉。
  3. 根因定位：我们的范围查询（如WHERE id BETWEEN 10 AND 20）最初实现是：先找到id=10的记录上锁，然后沿着叶子节点链表扫描并逐条上锁直到id=20。问题在于，在扫描过程中，如果另一个事务在已扫描过的位置插入了一条新记录（例如id=15），而这条记录恰好也满足范围条件，它就会被漏掉。这就是幻读现象。
• 解决：为了在可串行化隔离级别下防止幻读，仅靠记录锁不够。我们引入了间隙锁。在BETWEEN 10 AND 20时，不仅锁住范围内所有存在的记录，还要锁住记录之间的“间隙”，以及两端的“上界”和“下界”间隙，阻止其他事务在范围内插入新记录。这彻底解决了幻读问题。

7.2 问题二：系统在长时间TPC-C测试后吞吐量逐渐下降

• 现象：测试开始时tpmC正常，运行几小时后，吞吐量缓慢下降，响应时间变长。
• 排查：
  1. 监控资源：使用top、iostat监控，发现内存使用稳定，但磁盘I/O等待时间在后期明显增高。
  2. 检查缓冲池：发现缓冲池的命中率在后期显著下降。分析缓冲池内容，充满了大量几乎不再被访问的“冷数据”页面。
  3. 根因定位：我们的LRU-K算法中，K值设置得较小（为2），且对历史访问记录的衰减策略不够积极。在TPC-C的混合负载下，一些大规模的分析型查询（如库存水平查询）会顺序扫描大表，将大量“一次性”页面刷进缓冲池，污染了缓存，挤出了真正热点的数据（如仓库、地区表）。
• 解决：我们改进了置换算法，引入了“访问频率”和“最近性”的加权评估，并对顺序扫描的页面进行了特殊标记，让它们在缓冲池中的“生存优先级”更低。同时，增加了后台线程定期清理过于陈旧的访问历史。调整后，缓冲池命中率在长期运行中保持稳定。

7.3 问题速查表

8. 参赛总结与对数据库内核学习的建议

回顾整个项目，从阅读RMDB框架代码时的懵懂，到调试第一个B+树分裂成功时的兴奋，再到看到TPC-C测试通过时的如释重负，这是一段极其扎实和宝贵的系统编程训练。它强迫你去思考数据在磁盘和内存中的每一比特是如何组织的，去设计算法在效率和正确性之间权衡，去处理并发环境下各种诡异的边界条件。

对于也想深入数据库内核的同学，我的建议是：不要一开始就试图读懂MySQL或PostgreSQL那样庞大的代码库。那会让你望而生畏。最好的路径就是像这个赛道一样，从一个清晰的小框架（如RMDB、BusTub）开始，亲手实现每一个核心模块。实现一遍B+树，你会对索引的理解远超任何书本；实现一遍优化器，你会真正明白为什么查询会慢；实现一遍事务恢复，你会对“持久化”有刻骨铭心的认识。

在实现过程中，一定要写测试。为每个模块编写单元测试（例如，测试B+树的插入、删除、范围查询），为整个系统编写集成测试（例如，测试多语句事务的原子性）。TPC-C就是一个终极的集成测试。调试并发和恢复问题非常困难，良好的日志系统是你的“眼睛”，要设计不同级别的日志输出，在出问题时能快速定位。

最后，数据库是一个博大精深的领域，我们这个项目只是叩开了大门。现代数据库还有太多值得探索的方向：向量化执行引擎、基于代价的优化器中的深度学习、存算分离架构、云原生分布式事务……但通过这个从零到一的过程，你获得的是解决复杂系统问题的底层能力和信心，这是无论未来研究哪个方向都无比珍贵的财富。

本文还有配套的精品资源，点击获取