简介本资源是2024年全国大学生计算机系统能力大赛数据库管理系统赛道一等奖获奖作品“RMDB-2024”面向高校计算机及相关专业本科生、数据库系统课程学习者与系统级开发初学者聚焦关系型数据库核心机制的工程化实现涵盖存储管理、查询解析、事务处理与优化器设计等关键问题。压缩包共377个文件以102个C源文件.cc/.cpp和110个头文件.h/.hpp构成主体代码框架辅以30个Python脚本测试与工具、30份Markdown文档含设计说明与使用指南、25个文本配置与日志样例以及BUILD.bazel等构建配置文件完整呈现基于Bazel构建的现代DBMS工程结构包体仅2.21MB轻量但信息密度高。已有455人学习下载可直接获取一套通过权威赛事验证的、具备ACID支持与SQL子集执行能力的轻量级RDBMS参考实现包含可编译源码、单元测试用例gmock/gtest、词法/语法分析生成文件lex.yy.c/yacc.tab.c及清晰的模块划分逻辑是深入理解数据库内核原理与动手实践的优质教学与研究素材。1. 项目概述从零到一构建一个教学级关系型数据库去年带队参加全国大学生计算机系统能力大赛数据库管理系统赛道最终拿下一等奖的经历现在回想起来依然觉得热血沸腾。我们团队的作品“RMDB-2024”是一个从零开始实现的教学级关系型数据库管理系统。对于很多计算机专业的学生甚至是一些刚入行的开发者来说“数据库”这三个字往往意味着MySQL、PostgreSQL这些成熟的黑盒我们知道怎么用SQL去操作它但它的内部究竟是如何运转的——比如一条简单的SELECT * FROM users WHERE id 1;是如何被解析、优化、最终从磁盘上找到那行数据的——这个过程就像魔法一样。RMDB-2024这个项目就是亲手揭开这个魔法帷幕的过程。它不是一个玩具而是一个具备了完整核心模块的、可运行的数据库系统涵盖了SQL解析、查询优化、事务管理、存储引擎等关键部分。通过复现这个项目你不仅能深刻理解数据库教科书上的每一个理论概念是如何落地的更能获得一次完整的系统软件研发实战经验这种能力对于未来从事底层开发、基础架构等工作是无价的。无论你是正在备赛的学生还是希望深入数据库内核的开发者这篇文章将为你拆解RMDB-2024的核心设计与实现细节提供一条清晰的实践路径。2. 核心架构设计与技术选型思路2.1 为什么选择C作为实现语言在项目启动之初语言选型是第一个需要权衡的决策。我们最终选择了C这背后有几层关键的考量。首先数据库系统是典型的系统软件对性能和资源控制有极高的要求。C提供了零成本抽象的能力意味着我们可以使用类、模板等现代语言特性来构建清晰的内核架构而不会引入额外的运行时开销。其次我们需要直接管理内存和磁盘I/OC的指针和手动内存管理能力虽然带来了复杂性但也给予了我们最大的控制权这对于实现缓冲池、索引结构等核心组件至关重要。最后从生态和性能标杆来看主流数据库如MySQL、PostgreSQL的核心部分均采用C/C实现选择C便于我们参考其优秀的设计思想并且能确保最终系统的性能处于可接受的基准线上。当然用C也意味着要直面其复杂性比如内存泄漏、野指针等问题。我们的策略是在核心数据路径上使用纯C和STL但对于模块间的接口、以及需要序列化传输的数据结构会明确所有权和生命周期并辅以RAII资源获取即初始化惯用法和智能指针如std::unique_ptr在非性能关键路径上进行管理在开发效率和运行时安全之间取得平衡。2.2 整体模块化架构拆解RMDB-2024采用了经典的分层架构各模块之间通过清晰的接口进行通信降低了耦合度也便于团队分工和单元测试。整个系统可以划分为以下几个核心层次SQL前端层负责接收客户端发送的SQL字符串。主要包括词法分析器和语法分析器。我们使用了Flex和Bison这对经典工具来生成解析器代码。词法分析器将SQL字符串切割成一个个有意义的词元比如关键字SELECT、标识符users、操作符等。语法分析器则根据预定义的SQL语法规则将这些词元组织成一棵抽象语法树。这棵AST是后续所有处理的基础。查询处理与优化层这是数据库的“大脑”。它接收AST并将其转化为一系列可执行的操作。这一层首先进行语义分析检查表名、列名是否存在数据类型是否匹配等。然后查询优化器登场它的任务是从众多可能的执行计划中选出一个代价最低的。例如对于SELECT * FROM A JOIN B ON A.id B.aid WHERE A.value 10;优化器需要决定是先做过滤再连接还是先连接再过滤以及使用哪种连接算法。我们实现了一个基于规则的优化器和简单的代价模型。存储引擎层这是数据库的“肌肉”直接与磁盘打交道。它负责数据的物理存储、索引和缓存。我们实现了堆文件来存储表数据即记录以无序方式追加到文件末尾。为了加速查询我们实现了B树索引这是关系型数据库最核心的索引数据结构。此外缓冲池模块至关重要它通过在内存中缓存热点数据页将昂贵的磁盘I/O降至最低。事务管理层保证数据的ACID特性。我们实现了基于两阶段锁的并发控制协议来保证隔离性。对于原子性和持久性我们采用了预写式日志机制任何数据页的修改在落盘前都必须先将其对应的重做日志记录持久化到日志文件中。当系统崩溃恢复时可以通过重放日志来恢复到一致状态。注意模块化设计时接口定义要先行。我们花了大量时间在项目初期定义每个模块的class的公共方法和需要传递的数据结构。明确的接口契约能极大减少后续联调时的“扯皮”时间。2.3 关键数据结构设计数据库内核的效率很大程度上取决于其核心数据结构的设计。这里分享两个我们精心设计的数据结构记录与页格式磁盘I/O的基本单位是“页”通常为4KB或8KB。我们设计了固定的页头包含页ID、校验和、空闲空间起始偏移等信息。记录在页内连续存储每条记录有一个小的记录头包含是否删除的标记、记录长度等。删除记录时我们并不立即进行物理删除和空间整理而是标记为“墓碑”后续的插入操作可以复用这些空间。这种设计用空间换时间提升了插入和删除的效率。B树节点设计B树索引的每个节点也对应一个磁盘页。内部节点存储键值和指向子节点的页ID。叶子节点存储键值和对应的记录位置。为了在内存中高效操作我们为B树节点设计了对应的内存结构并在缓冲池中缓存。搜索时从根节点开始利用键值的比较结果一路向下直到找到目标叶子节点。插入和删除可能导致节点的分裂与合并这些操作都需要谨慎处理并保证树结构的平衡。3. 核心模块实现深度解析3.1 SQL解析器从字符串到执行计划实现一个健壮的SQL解析器是第一步也是让数据库“活”起来的关键。我们使用Flex定义词法规则Bison定义语法规则。词法分析Flex文件.l中我们使用正则表达式匹配SQL的关键字、标识符、数字、字符串、操作符等。一个关键技巧是对于关键字我们需要确保它们不会被错误地识别为标识符。例如SELECT必须作为一个完整的词元被识别而不是SEL、ECT。我们通过定义关键字的优先级和精确匹配来解决。语法分析与AST构建Bison文件.y中我们定义了SQL的上下文无关文法。例如一个简单的SELECT语句文法可能如下select_stmt: SELECT select_list FROM table_name where_clause; select_list: * | expr_list; where_clause: /* empty */ | WHERE condition;Bison在解析过程中会根据匹配的规则触发相应的动作。我们在这些动作中动态地构建AST节点。每个节点都是一个C类对象例如SelectStmt、Expr、ColumnRefExpr等。AST构建完成后它就完全脱离了原始字符串的形态变成了一个富含语义的结构化对象可以很方便地被后续模块遍历和处理。实操心得在编写Bison语法时要特别注意消除二义性和处理运算符优先级。我们一开始没有明确定义AND和OR的优先级导致WHERE a1 AND b2 OR c3这样的条件解析出现歧义。后来在语法文件中显式定义了优先级%left OR%left AND问题才得以解决。3.2 查询优化器寻找最优执行路径解析器产生的“逻辑执行计划”通常是直观但低效的。优化器的任务就是将其转化为高效的“物理执行计划”。逻辑优化我们首先实施一系列基于规则的优化。例如谓词下推将过滤条件WHERE尽可能推到靠近数据源的地方减少后续操作需要处理的数据量。投影消除如果查询只用到部分列在扫描阶段就过滤掉不需要的列减少数据在内存中的搬运成本。常量折叠提前计算表达式中的常量部分如WHERE id 105优化为WHERE id 15。我们通过遍历AST应用这些规则对树结构进行重写来实现逻辑优化。物理优化与代价估算逻辑计划确定后需要为每个逻辑操作符选择具体的物理实现算法。例如JOIN操作可以选择嵌套循环连接、排序合并连接或哈希连接。我们实现了一个简单的基于统计信息的代价模型。对于每个表我们在系统目录中维护了行数、唯一值数量等基本信息。代价估算主要考虑I/O成本读取数据页的数量和CPU成本比较操作的次数。最终优化器会生成一个由物理操作符节点组成的执行计划树。3.3 存储引擎B树索引与缓冲池实战B树索引的实现B树的核心操作是搜索、插入和删除。我们为树定义了BPlusTree类为页定义了BPlusTreePage基类并派生出InternalPage和LeafPage。搜索从根页开始在内部页中二分查找第一个大于等于目标键的键值根据其对应的指针找到子页递归直至叶子页。在叶子页中再次二分查找找到目标键或确认其不存在。插入先搜索到应插入的叶子页。如果该页未满直接插入并排序。如果已满则需要进行分裂创建一个新的叶子页将原页一半的数据移动过去更新兄弟指针并将新页的最小键插入到父节点中。这个过程可能递归向上直到根节点。如果根节点也分裂则需要创建新的根节点树的高度增加。删除过程与插入类似但相反涉及节点的合并或重分配以维持树的平衡。缓冲池管理缓冲池是性能的关键。我们实现了BufferPoolManager类它管理着一个固定大小的页帧数组。每个页帧有一个frame_id并可以装载一个磁盘页。我们使用一个哈希表来快速根据page_id找到页在缓冲池中的位置并使用一个LRU淘汰策略来管理哪些页可以被替换出去。当执行器需要读取一个页时它调用FetchPage(page_id)。缓冲池管理器首先检查该页是否已在池中缓存命中如果是则直接返回。如果未命中则需要找到一个空闲帧或淘汰一个现有页。如果被淘汰的页是脏页被修改过则必须将其写回磁盘。然后将请求的页从磁盘读入该帧并更新哈希表和LRU列表。踩坑记录实现缓冲池时我们最初忽略了锁的粒度问题。在并发测试下对整个缓冲池加一把大锁导致性能急剧下降。后来我们改为对每个页帧使用更细粒度的锁并配合std::shared_mutex实现读写锁读操作可以并发只有写操作才互斥性能得到了显著提升。4. 事务与并发控制实现4.1 基于锁的并发控制为了保证事务的隔离性Isolation我们实现了两阶段锁协议。每个事务在访问数据项如一个记录或一个页前必须先获得相应的锁。锁分为共享锁和排他锁。2PL要求事务分为两个阶段增长阶段只能获取锁不能释放锁和收缩阶段只能释放锁不能获取锁。这保证了事务的可串行化调度。我们实现了LockManager类来集中管理锁。它维护着一个锁表记录每个数据项上的锁请求队列。当一个事务请求锁时锁管理器检查是否与现有锁兼容。如果兼容则授予锁如果不兼容则该事务必须等待。我们使用std::condition_variable来实现等待队列避免忙等待。死锁检测也是一个挑战我们实现了一个简单的基于等待图的死锁检测算法定期运行如果发现环则选择一个事务进行回滚以打破死锁。4.2 预写式日志与恢复为了保证原子性和持久性我们实现了预写式日志。任何对数据页的修改都必须先将其对应的日志记录写入到持久化的日志文件中然后才能修改内存中的数据页。日志记录中包含了足够的信息以便在系统崩溃后能够重做或撤销操作。我们定义了多种日志类型INSERT_LOG、DELETE_LOG、UPDATE_LOG、COMMIT_LOG、ABORT_LOG等。日志管理器LogManager负责将日志记录顺序追加到日志文件并定期执行刷盘操作。我们采用了STEAL/NO-FORCE策略即允许未提交事务的脏页被替换回磁盘但提交时不必强制所有脏页立即刷盘只需保证该事务的所有日志记录已刷盘即可。恢复过程分为两个阶段分析阶段从最近的检查点开始扫描日志确定崩溃时哪些事务是活跃的已开始未提交。重做阶段从最早的未刷盘修改记录开始重做所有操作包括已提交和未提交事务将数据库恢复到崩溃前的物理状态。撤销阶段反向扫描日志对所有活跃事务的操作执行逆操作将其撤销从而保证数据库恢复到一致状态只包含已提交事务的结果。5. 系统集成、测试与性能调优5.1 模块集成与系统测试当所有核心模块开发完成后集成是一个大工程。我们编写了大量的单元测试使用Google Test框架对每个类和方法进行测试。例如为B树测试插入、删除、搜索的各种边界情况为缓冲池测试缓存命中、淘汰、脏页回写等逻辑。之后是集成测试我们模拟真实的SQL工作负载创建多张表插入大量数据执行复杂的连接和聚合查询并验证结果的正确性。我们还进行了并发压力测试启动多个线程模拟并发事务测试锁管理器和事务隔离级别是否正确工作确保没有数据竞争和死锁问题。5.2 性能瓶颈分析与调优在功能稳定后我们使用性能分析工具对系统进行了剖析。发现最初的性能瓶颈主要集中在以下几点日志同步刷盘每次写日志都调用fsync虽然安全但极其耗时。我们将其优化为组提交将一段时间内多个事务的日志先缓存在内存缓冲区然后一次性刷盘大幅减少了I/O次数。B树搜索的线性扫描在内部节点和叶子节点中我们最初使用线性搜索来定位键值。当节点容量较大时这成为瓶颈。我们将其改为二分查找搜索复杂度从O(n)降为O(log n)。内存分配频繁执行过程中频繁创建和销毁小的临时对象。我们引入了对象池对一些常用的、固定大小的数据结构进行复用减少了内存分配器的压力。经过几轮调优RMDB-2024在处理TPC-H等基准测试查询时性能有了数量级的提升。这个过程让我们深刻体会到在系统软件中数据结构和算法是骨架而细节上的优化则是血肉二者缺一不可。6. 参赛经验与项目复盘6.1 团队协作与版本管理开发一个数据库系统是庞大的工程良好的团队协作至关重要。我们使用Git进行版本控制并遵循Git Flow工作流。main分支始终保持稳定每个新功能在feature分支上开发完成后通过Pull Request合并入develop分支。定期从develop创建release分支进行集成测试测试通过后再合并回main和develop。清晰的流程避免了代码冲突和集成地狱。我们使用CMake作为构建系统它能够跨平台并方便地管理第三方依赖。文档方面除了代码注释我们使用Doxygen自动生成API文档并使用一个Wiki来记录设计决策、接口约定和开发进度确保信息在团队内透明共享。6.2 面对大赛评审的要点系统能力大赛的评审不仅看功能是否实现更看重设计的完整性、正确性和创新性。完整性你的数据库是否覆盖了大赛要求的所有核心模块SQL支持度如何事务ACID是否真正实现我们确保RMDB-2024覆盖了从解析到存储的全链路。正确性这是底线。我们准备了详尽的测试用例集包括功能测试和并发测试并在答辩现场可以自信地演示。对于边界条件如空表查询、溢出处理等都有妥善应对。创新性在实现基础功能之上是否有自己的思考和改进例如我们在查询优化器中尝试引入了一种基于简单机器学习的代价估算模型虽然最终效果有限但这个探索过程在答辩中成为了亮点。另一个创新点是在存储格式上我们为特定类型的列尝试了轻量级的压缩算法减少了I/O。演示与表达准备一个清晰的演示脚本突出系统架构和关键技术的实现。面对评委的提问要能准确地说出某个模块为什么这样设计权衡点在哪里。我们团队在决赛前进行了多次模拟答辩对可能的技术问题做了充分准备。回过头看开发RMDB-2024是一次痛并快乐着的旅程。它强迫我们跳出“数据库使用者”的舒适区深入到每一个字节、每一个指针的层面去思考问题。当你看到自己写的代码成功解析并执行了一条SQL返回正确结果时那种成就感是无与伦比的。这个项目带给我们的不仅仅是一个奖项更是一套完整的、构建复杂系统软件的思维方法和工程能力。如果你也想挑战自己不妨就从定义一个简单的存储格式和SQL语法开始一步步搭建起属于你自己的数据库世界。本文还有配套的精品资源点击获取
从零构建教学级关系型数据库：RMDB-2024核心架构与实现解析
简介本资源是2024年全国大学生计算机系统能力大赛数据库管理系统赛道一等奖获奖作品“RMDB-2024”面向高校计算机及相关专业本科生、数据库系统课程学习者与系统级开发初学者聚焦关系型数据库核心机制的工程化实现涵盖存储管理、查询解析、事务处理与优化器设计等关键问题。压缩包共377个文件以102个C源文件.cc/.cpp和110个头文件.h/.hpp构成主体代码框架辅以30个Python脚本测试与工具、30份Markdown文档含设计说明与使用指南、25个文本配置与日志样例以及BUILD.bazel等构建配置文件完整呈现基于Bazel构建的现代DBMS工程结构包体仅2.21MB轻量但信息密度高。已有455人学习下载可直接获取一套通过权威赛事验证的、具备ACID支持与SQL子集执行能力的轻量级RDBMS参考实现包含可编译源码、单元测试用例gmock/gtest、词法/语法分析生成文件lex.yy.c/yacc.tab.c及清晰的模块划分逻辑是深入理解数据库内核原理与动手实践的优质教学与研究素材。1. 项目概述从零到一构建一个教学级关系型数据库去年带队参加全国大学生计算机系统能力大赛数据库管理系统赛道最终拿下一等奖的经历现在回想起来依然觉得热血沸腾。我们团队的作品“RMDB-2024”是一个从零开始实现的教学级关系型数据库管理系统。对于很多计算机专业的学生甚至是一些刚入行的开发者来说“数据库”这三个字往往意味着MySQL、PostgreSQL这些成熟的黑盒我们知道怎么用SQL去操作它但它的内部究竟是如何运转的——比如一条简单的SELECT * FROM users WHERE id 1;是如何被解析、优化、最终从磁盘上找到那行数据的——这个过程就像魔法一样。RMDB-2024这个项目就是亲手揭开这个魔法帷幕的过程。它不是一个玩具而是一个具备了完整核心模块的、可运行的数据库系统涵盖了SQL解析、查询优化、事务管理、存储引擎等关键部分。通过复现这个项目你不仅能深刻理解数据库教科书上的每一个理论概念是如何落地的更能获得一次完整的系统软件研发实战经验这种能力对于未来从事底层开发、基础架构等工作是无价的。无论你是正在备赛的学生还是希望深入数据库内核的开发者这篇文章将为你拆解RMDB-2024的核心设计与实现细节提供一条清晰的实践路径。2. 核心架构设计与技术选型思路2.1 为什么选择C作为实现语言在项目启动之初语言选型是第一个需要权衡的决策。我们最终选择了C这背后有几层关键的考量。首先数据库系统是典型的系统软件对性能和资源控制有极高的要求。C提供了零成本抽象的能力意味着我们可以使用类、模板等现代语言特性来构建清晰的内核架构而不会引入额外的运行时开销。其次我们需要直接管理内存和磁盘I/OC的指针和手动内存管理能力虽然带来了复杂性但也给予了我们最大的控制权这对于实现缓冲池、索引结构等核心组件至关重要。最后从生态和性能标杆来看主流数据库如MySQL、PostgreSQL的核心部分均采用C/C实现选择C便于我们参考其优秀的设计思想并且能确保最终系统的性能处于可接受的基准线上。当然用C也意味着要直面其复杂性比如内存泄漏、野指针等问题。我们的策略是在核心数据路径上使用纯C和STL但对于模块间的接口、以及需要序列化传输的数据结构会明确所有权和生命周期并辅以RAII资源获取即初始化惯用法和智能指针如std::unique_ptr在非性能关键路径上进行管理在开发效率和运行时安全之间取得平衡。2.2 整体模块化架构拆解RMDB-2024采用了经典的分层架构各模块之间通过清晰的接口进行通信降低了耦合度也便于团队分工和单元测试。整个系统可以划分为以下几个核心层次SQL前端层负责接收客户端发送的SQL字符串。主要包括词法分析器和语法分析器。我们使用了Flex和Bison这对经典工具来生成解析器代码。词法分析器将SQL字符串切割成一个个有意义的词元比如关键字SELECT、标识符users、操作符等。语法分析器则根据预定义的SQL语法规则将这些词元组织成一棵抽象语法树。这棵AST是后续所有处理的基础。查询处理与优化层这是数据库的“大脑”。它接收AST并将其转化为一系列可执行的操作。这一层首先进行语义分析检查表名、列名是否存在数据类型是否匹配等。然后查询优化器登场它的任务是从众多可能的执行计划中选出一个代价最低的。例如对于SELECT * FROM A JOIN B ON A.id B.aid WHERE A.value 10;优化器需要决定是先做过滤再连接还是先连接再过滤以及使用哪种连接算法。我们实现了一个基于规则的优化器和简单的代价模型。存储引擎层这是数据库的“肌肉”直接与磁盘打交道。它负责数据的物理存储、索引和缓存。我们实现了堆文件来存储表数据即记录以无序方式追加到文件末尾。为了加速查询我们实现了B树索引这是关系型数据库最核心的索引数据结构。此外缓冲池模块至关重要它通过在内存中缓存热点数据页将昂贵的磁盘I/O降至最低。事务管理层保证数据的ACID特性。我们实现了基于两阶段锁的并发控制协议来保证隔离性。对于原子性和持久性我们采用了预写式日志机制任何数据页的修改在落盘前都必须先将其对应的重做日志记录持久化到日志文件中。当系统崩溃恢复时可以通过重放日志来恢复到一致状态。注意模块化设计时接口定义要先行。我们花了大量时间在项目初期定义每个模块的class的公共方法和需要传递的数据结构。明确的接口契约能极大减少后续联调时的“扯皮”时间。2.3 关键数据结构设计数据库内核的效率很大程度上取决于其核心数据结构的设计。这里分享两个我们精心设计的数据结构记录与页格式磁盘I/O的基本单位是“页”通常为4KB或8KB。我们设计了固定的页头包含页ID、校验和、空闲空间起始偏移等信息。记录在页内连续存储每条记录有一个小的记录头包含是否删除的标记、记录长度等。删除记录时我们并不立即进行物理删除和空间整理而是标记为“墓碑”后续的插入操作可以复用这些空间。这种设计用空间换时间提升了插入和删除的效率。B树节点设计B树索引的每个节点也对应一个磁盘页。内部节点存储键值和指向子节点的页ID。叶子节点存储键值和对应的记录位置。为了在内存中高效操作我们为B树节点设计了对应的内存结构并在缓冲池中缓存。搜索时从根节点开始利用键值的比较结果一路向下直到找到目标叶子节点。插入和删除可能导致节点的分裂与合并这些操作都需要谨慎处理并保证树结构的平衡。3. 核心模块实现深度解析3.1 SQL解析器从字符串到执行计划实现一个健壮的SQL解析器是第一步也是让数据库“活”起来的关键。我们使用Flex定义词法规则Bison定义语法规则。词法分析Flex文件.l中我们使用正则表达式匹配SQL的关键字、标识符、数字、字符串、操作符等。一个关键技巧是对于关键字我们需要确保它们不会被错误地识别为标识符。例如SELECT必须作为一个完整的词元被识别而不是SEL、ECT。我们通过定义关键字的优先级和精确匹配来解决。语法分析与AST构建Bison文件.y中我们定义了SQL的上下文无关文法。例如一个简单的SELECT语句文法可能如下select_stmt: SELECT select_list FROM table_name where_clause; select_list: * | expr_list; where_clause: /* empty */ | WHERE condition;Bison在解析过程中会根据匹配的规则触发相应的动作。我们在这些动作中动态地构建AST节点。每个节点都是一个C类对象例如SelectStmt、Expr、ColumnRefExpr等。AST构建完成后它就完全脱离了原始字符串的形态变成了一个富含语义的结构化对象可以很方便地被后续模块遍历和处理。实操心得在编写Bison语法时要特别注意消除二义性和处理运算符优先级。我们一开始没有明确定义AND和OR的优先级导致WHERE a1 AND b2 OR c3这样的条件解析出现歧义。后来在语法文件中显式定义了优先级%left OR%left AND问题才得以解决。3.2 查询优化器寻找最优执行路径解析器产生的“逻辑执行计划”通常是直观但低效的。优化器的任务就是将其转化为高效的“物理执行计划”。逻辑优化我们首先实施一系列基于规则的优化。例如谓词下推将过滤条件WHERE尽可能推到靠近数据源的地方减少后续操作需要处理的数据量。投影消除如果查询只用到部分列在扫描阶段就过滤掉不需要的列减少数据在内存中的搬运成本。常量折叠提前计算表达式中的常量部分如WHERE id 105优化为WHERE id 15。我们通过遍历AST应用这些规则对树结构进行重写来实现逻辑优化。物理优化与代价估算逻辑计划确定后需要为每个逻辑操作符选择具体的物理实现算法。例如JOIN操作可以选择嵌套循环连接、排序合并连接或哈希连接。我们实现了一个简单的基于统计信息的代价模型。对于每个表我们在系统目录中维护了行数、唯一值数量等基本信息。代价估算主要考虑I/O成本读取数据页的数量和CPU成本比较操作的次数。最终优化器会生成一个由物理操作符节点组成的执行计划树。3.3 存储引擎B树索引与缓冲池实战B树索引的实现B树的核心操作是搜索、插入和删除。我们为树定义了BPlusTree类为页定义了BPlusTreePage基类并派生出InternalPage和LeafPage。搜索从根页开始在内部页中二分查找第一个大于等于目标键的键值根据其对应的指针找到子页递归直至叶子页。在叶子页中再次二分查找找到目标键或确认其不存在。插入先搜索到应插入的叶子页。如果该页未满直接插入并排序。如果已满则需要进行分裂创建一个新的叶子页将原页一半的数据移动过去更新兄弟指针并将新页的最小键插入到父节点中。这个过程可能递归向上直到根节点。如果根节点也分裂则需要创建新的根节点树的高度增加。删除过程与插入类似但相反涉及节点的合并或重分配以维持树的平衡。缓冲池管理缓冲池是性能的关键。我们实现了BufferPoolManager类它管理着一个固定大小的页帧数组。每个页帧有一个frame_id并可以装载一个磁盘页。我们使用一个哈希表来快速根据page_id找到页在缓冲池中的位置并使用一个LRU淘汰策略来管理哪些页可以被替换出去。当执行器需要读取一个页时它调用FetchPage(page_id)。缓冲池管理器首先检查该页是否已在池中缓存命中如果是则直接返回。如果未命中则需要找到一个空闲帧或淘汰一个现有页。如果被淘汰的页是脏页被修改过则必须将其写回磁盘。然后将请求的页从磁盘读入该帧并更新哈希表和LRU列表。踩坑记录实现缓冲池时我们最初忽略了锁的粒度问题。在并发测试下对整个缓冲池加一把大锁导致性能急剧下降。后来我们改为对每个页帧使用更细粒度的锁并配合std::shared_mutex实现读写锁读操作可以并发只有写操作才互斥性能得到了显著提升。4. 事务与并发控制实现4.1 基于锁的并发控制为了保证事务的隔离性Isolation我们实现了两阶段锁协议。每个事务在访问数据项如一个记录或一个页前必须先获得相应的锁。锁分为共享锁和排他锁。2PL要求事务分为两个阶段增长阶段只能获取锁不能释放锁和收缩阶段只能释放锁不能获取锁。这保证了事务的可串行化调度。我们实现了LockManager类来集中管理锁。它维护着一个锁表记录每个数据项上的锁请求队列。当一个事务请求锁时锁管理器检查是否与现有锁兼容。如果兼容则授予锁如果不兼容则该事务必须等待。我们使用std::condition_variable来实现等待队列避免忙等待。死锁检测也是一个挑战我们实现了一个简单的基于等待图的死锁检测算法定期运行如果发现环则选择一个事务进行回滚以打破死锁。4.2 预写式日志与恢复为了保证原子性和持久性我们实现了预写式日志。任何对数据页的修改都必须先将其对应的日志记录写入到持久化的日志文件中然后才能修改内存中的数据页。日志记录中包含了足够的信息以便在系统崩溃后能够重做或撤销操作。我们定义了多种日志类型INSERT_LOG、DELETE_LOG、UPDATE_LOG、COMMIT_LOG、ABORT_LOG等。日志管理器LogManager负责将日志记录顺序追加到日志文件并定期执行刷盘操作。我们采用了STEAL/NO-FORCE策略即允许未提交事务的脏页被替换回磁盘但提交时不必强制所有脏页立即刷盘只需保证该事务的所有日志记录已刷盘即可。恢复过程分为两个阶段分析阶段从最近的检查点开始扫描日志确定崩溃时哪些事务是活跃的已开始未提交。重做阶段从最早的未刷盘修改记录开始重做所有操作包括已提交和未提交事务将数据库恢复到崩溃前的物理状态。撤销阶段反向扫描日志对所有活跃事务的操作执行逆操作将其撤销从而保证数据库恢复到一致状态只包含已提交事务的结果。5. 系统集成、测试与性能调优5.1 模块集成与系统测试当所有核心模块开发完成后集成是一个大工程。我们编写了大量的单元测试使用Google Test框架对每个类和方法进行测试。例如为B树测试插入、删除、搜索的各种边界情况为缓冲池测试缓存命中、淘汰、脏页回写等逻辑。之后是集成测试我们模拟真实的SQL工作负载创建多张表插入大量数据执行复杂的连接和聚合查询并验证结果的正确性。我们还进行了并发压力测试启动多个线程模拟并发事务测试锁管理器和事务隔离级别是否正确工作确保没有数据竞争和死锁问题。5.2 性能瓶颈分析与调优在功能稳定后我们使用性能分析工具对系统进行了剖析。发现最初的性能瓶颈主要集中在以下几点日志同步刷盘每次写日志都调用fsync虽然安全但极其耗时。我们将其优化为组提交将一段时间内多个事务的日志先缓存在内存缓冲区然后一次性刷盘大幅减少了I/O次数。B树搜索的线性扫描在内部节点和叶子节点中我们最初使用线性搜索来定位键值。当节点容量较大时这成为瓶颈。我们将其改为二分查找搜索复杂度从O(n)降为O(log n)。内存分配频繁执行过程中频繁创建和销毁小的临时对象。我们引入了对象池对一些常用的、固定大小的数据结构进行复用减少了内存分配器的压力。经过几轮调优RMDB-2024在处理TPC-H等基准测试查询时性能有了数量级的提升。这个过程让我们深刻体会到在系统软件中数据结构和算法是骨架而细节上的优化则是血肉二者缺一不可。6. 参赛经验与项目复盘6.1 团队协作与版本管理开发一个数据库系统是庞大的工程良好的团队协作至关重要。我们使用Git进行版本控制并遵循Git Flow工作流。main分支始终保持稳定每个新功能在feature分支上开发完成后通过Pull Request合并入develop分支。定期从develop创建release分支进行集成测试测试通过后再合并回main和develop。清晰的流程避免了代码冲突和集成地狱。我们使用CMake作为构建系统它能够跨平台并方便地管理第三方依赖。文档方面除了代码注释我们使用Doxygen自动生成API文档并使用一个Wiki来记录设计决策、接口约定和开发进度确保信息在团队内透明共享。6.2 面对大赛评审的要点系统能力大赛的评审不仅看功能是否实现更看重设计的完整性、正确性和创新性。完整性你的数据库是否覆盖了大赛要求的所有核心模块SQL支持度如何事务ACID是否真正实现我们确保RMDB-2024覆盖了从解析到存储的全链路。正确性这是底线。我们准备了详尽的测试用例集包括功能测试和并发测试并在答辩现场可以自信地演示。对于边界条件如空表查询、溢出处理等都有妥善应对。创新性在实现基础功能之上是否有自己的思考和改进例如我们在查询优化器中尝试引入了一种基于简单机器学习的代价估算模型虽然最终效果有限但这个探索过程在答辩中成为了亮点。另一个创新点是在存储格式上我们为特定类型的列尝试了轻量级的压缩算法减少了I/O。演示与表达准备一个清晰的演示脚本突出系统架构和关键技术的实现。面对评委的提问要能准确地说出某个模块为什么这样设计权衡点在哪里。我们团队在决赛前进行了多次模拟答辩对可能的技术问题做了充分准备。回过头看开发RMDB-2024是一次痛并快乐着的旅程。它强迫我们跳出“数据库使用者”的舒适区深入到每一个字节、每一个指针的层面去思考问题。当你看到自己写的代码成功解析并执行了一条SQL返回正确结果时那种成就感是无与伦比的。这个项目带给我们的不仅仅是一个奖项更是一套完整的、构建复杂系统软件的思维方法和工程能力。如果你也想挑战自己不妨就从定义一个简单的存储格式和SQL语法开始一步步搭建起属于你自己的数据库世界。本文还有配套的精品资源点击获取
