简介这是一份面向高校数据库课程学习者与系统编程实践者的C数据库管理系统教学原型资源专为《数据库系统实现》等课程实验设计帮助学生动手实现RDBMS核心模块。资源包共185个文件涵盖34个C源码文件含B树并发/删除测试、查询计划生成、缓冲池管理等关键模块、58个头文件支撑系统分层架构、20个SQL示例脚本用于功能验证及10个Markdown说明文档整体仅1.36MB轻量易读且结构清晰便于逐模块分析与调试。目前已有56人学习下载适合中高级C学习者深入理解事务管理、锁机制、日志恢复、查询优化等底层原理。读者可直接基于该框架开展索引实现、并发控制改进或存储引擎扩展等课程实验代码组织规范关键路径注释充分是少有的兼顾教学性与工程可读性的国产数据库教学参考实现。1. 这不是又一个玩具数据库RucBase 是面向系统级训练的 C 手写数据库内核专为理解存储引擎、查询执行与事务机制而生你可能在课程设计、毕业设计或自学数据库原理时被要求“实现一个简易数据库”。市面上多数所谓“简易”项目要么是 Python 脚本拼凑的键值模拟器要么是 Java 封装了大量现成组件的黑盒 demo。而 RucBase 不同——它是一个纯 C 实现、无外部依赖、从零构建磁盘页管理、B 树索引、SQL 解析器、查询执行器与两阶段锁事务子系统的教学型数据库管理系统。它不追求性能对标 PostgreSQL但每行代码都暴露核心决策为什么页大小设为 4KBB 树分裂时如何保证原子性SELECT 语句如何被拆解为 TableScan → Filter → Project 的物理算子链它的价值不在生产可用而在可调试、可打断点、可单步追踪一条 SQL 从词法分析到刷盘落盘的完整生命周期。适合正在啃《Database System Concepts》第 7 版第 10–12 章、刚学完操作系统内存管理与文件系统、想把“ACID”“WAL”“LSN”这些概念真正焊进肌肉记忆的开发者。如果你曾对着 SQLite 源码发懵或被 MySQL InnoDB 的宏定义绕晕RucBase 就是你该打开的第一个“透明数据库”。2. 从源码包解压到本地可运行三步构建最小可执行环境RucBase 的源码结构高度模块化但官方未提供一键 cmake 脚本新手常卡在编译环节。我一般会跳过原始 build.sh它隐式依赖某旧版 GCC改用现代 CMake 流程重组织。以下路径经实测兼容 Ubuntu 22.04 / macOS Sonoma Clang 15 / GCC 11.4。2.1 解压与目录结构确认识别核心模块边界下载解压后你会看到如下关键目录注意无third_party或vendor文件夹所有依赖均手写RucBase/ ├── src/ │ ├── buffer/ # 缓冲池管理LRU-K 替换策略 │ ├── catalog/ # 数据字典表/列元数据持久化 │ ├── execution/ # 物理执行算子SeqScan, IndexScan, HashJoin │ ├── parser/ # LALR(1) 手写语法分析器基于 flex/bison 生成 │ ├── storage/ # 存储层Page, DiskManager, BPlusTreeIndex │ └── transaction/ # 事务管理LockManager, LogManager, RecoveryManager ├── include/ # 全局头文件含 PageGuard, RID, Tuple 等核心类型定义 ├── test/ # 单元测试Google Test 框架覆盖 B 树插入/并发锁等 └── main.cpp # 命令行交互入口启动 REPL提示main.cpp是唯一可直接运行的入口它初始化DiskManager后进入 SQL 解析循环。不要试图先跑test/下的测试——它们依赖build/中生成的静态库需先完成编译。2.2 手动编写 CMakeLists.txt绕过原始脚本的 GCC 版本陷阱在RucBase/根目录新建CMakeLists.txt内容如下已适配 C17禁用 RTTI 与异常以贴近真实 DBMScmake_minimum_required(VERSION 3.10) project(RucBase LANGUAGES CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) set(CMAKE_CXX_EXTENSIONS OFF) # 关键禁用异常与 RTTIDBMS 内核级代码必须控制二进制体积与调用开销 set(CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS} -fno-exceptions -fno-rtti) # 添加子目录 add_subdirectory(src) # 主可执行文件 add_executable(rucbase main.cpp) target_link_libraries(rucbase PRIVATE rucbase_lib) target_include_directories(rucbase PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}/include)然后在src/CMakeLists.txt中定义库# src/CMakeLists.txt add_library(rucbase_lib STATIC buffer/buffer_pool_manager.cpp catalog/catalog.cpp execution/seq_scan_executor.cpp parser/yacc_parser.cpp # 注意此文件由 bison 生成需先运行 parser/build_parser.sh storage/disk_manager.cpp storage/page/page.cpp storage/index/b_plus_tree_index.cpp transaction/lock_manager.cpp ) target_include_directories(rucbase_lib PUBLIC ${CMAKE_CURRENT_SOURCE_DIR}/../include)2.3 编译前必做生成 parser 代码并修复 Bison 兼容性原始parser/build_parser.sh在新系统上大概率失败因 Bison 3.8 默认启用%define api.pure full而 RucBase 的yacc_parser.cpp依赖全局yylval。手动修复步骤进入parser/目录备份原始yacc.ycd parser cp yacc.y yacc.y.bak编辑yacc.y在%{ ... %}外部即文件顶部添加%define api.pure 0 %define parse.error verbose %code requires { #include common.h #include expression/abstract_expression.h }运行 Bison 生成解析器bison -d -v -o yacc.tab.c yacc.y flex -o lex.yy.c lex.l gcc -c -o yacc.tab.o yacc.tab.c gcc -c -o lex.yy.o lex.yy.c # 此时生成 yacc.tab.o 和 lex.yy.o后续链接进库回到根目录执行构建mkdir build cd build cmake .. -DCMAKE_BUILD_TYPEDebug make -j4成功后build/rucbase即为可执行 REPL。运行./rucbase输入CREATE TABLE t1(id INT, name VARCHAR(20));应返回OK—— 这是你亲手编译的数据库第一次响应 SQL。3. 理解其存储引擎B 树索引如何支撑点查与范围扫描RucBase 的storage/index/b_plus_tree_index.cpp是全项目最密集的算法现场。它不使用 STL 容器所有节点内存由BufferPoolManager分配且每个Page对应磁盘上一个 4KB 块。理解它是读懂整个系统 IO 行为的关键。3.1 B 树节点结构为什么叶子节点存 value非叶节点只存 key查看b_plus_tree_page.h核心定义如下// 非叶节点只存 (key, page_id) 对用于路由 struct InternalPage { page_id_t page_id_; // 当前页 ID int size_; // 当前键数量 int max_size_; // 最大键数量由 order 决定 std::arraypage_id_t, INTERNAL_PAGE_SIZE page_ids_; // 子页 ID 数组 std::arrayKeyType, INTERNAL_PAGE_SIZE keys_; // 分割键数组 }; // 叶子节点存 (key, value) 对value 是 RID记录 ID struct LeafPage { page_id_t page_id_; int size_; int max_size_; std::arrayKeyType, LEAF_PAGE_SIZE keys_; std::arrayRID, LEAF_PAGE_SIZE values_; // 注意这里存的是 RID不是实际 tuple 数据 page_id_t next_page_id_; // 叶子链表指针支持范围扫描 };逻辑说明RIDRecord ID是(page_id, slot_num)二元组指向TableHeap中的实际 tuple。这种分离设计让索引树极轻量——叶子页只存 8 字节 RID而非整行数据极大提升缓存命中率。当你执行SELECT * FROM t1 WHERE id 100B 树定位到叶子页后再通过RID去TableHeap中 fetch tuple这是典型的Index Nested Loop Join思路。3.2 插入流程分裂如何保证原子性谁负责刷盘Insert()方法分三步递归查找插入位置从根页开始根据 key 比较决定走哪个子页直到叶子页叶子页插入若未满直接插入并更新size_若满则触发Split()分裂传播Split()创建新叶子页将原页一半键值迁入并向上返回(new_key, new_page_id)给父节点插入——关键点在于分裂操作本身不刷盘仅修改 Buffer Pool 中的 Page 内存镜像。真正刷盘发生在BufferPoolManager::UnpinPage()时当某页被标记为is_dirtytrue且被驱逐出缓冲池DiskManager::WritePage()才将其写回磁盘。这意味着单条 INSERT 事务中B 树修改全程在内存无同步 IO但若进程崩溃未刷盘的页修改将丢失——这正是 RucBase默认不开启 WAL的代价也是它定位为教学系统而非生产系统的核心原因。3.3 范围扫描next_page_id 如何构建有序链表叶子页的next_page_id_在Split()时被显式维护新建叶子页leaf_new的next_page_id_设为原页leaf_old-next_page_id_原页leaf_old-next_page_id_更新为leaf_new-page_id_这样所有叶子页形成单向链表。执行SELECT * FROM t1 WHERE id BETWEEN 10 AND 100时B 树定位到 key10 的叶子页从此页开始沿next_page_id_链表顺序遍历对每个页内 key 做10 100过滤不重新走树查找避免重复导航开销。这是 B 树区别于 B 树的核心优势范围查询性能稳定与数据分布无关。4. 事务与并发控制两阶段锁2PL如何落地为 LockManagerRucBase 的事务模块是理解 ACID 中 “I”Isolation的最佳沙盒。它实现严格的Strict Two-Phase LockingStrict 2PL即锁在事务结束COMMIT/ABORT时才释放彻底避免脏读、不可重复读与幻读。4.1 锁粒度与锁类型为什么只支持 RECORD 和 TABLE 级别查看transaction/lock_manager.h锁类型定义精简enum class LockMode { SHARED, EXCLUSIVE }; enum class LockType { RECORD, TABLE }; // 注意无 PAGE 级别锁 struct LockRequest { txn_id_t txn_id_; LockMode lock_mode_; LockType lock_type_; table_oid_t oid_; // 表 IDTABLE 锁用 RID rid_; // 记录 IDRECORD 锁用 };参数说明table_oid_t是表在Catalog中的唯一整数 IDRID即前述(page_id, slot_num)。RucBase 放弃 PAGE 级锁因其实现复杂度高需处理页分裂导致的锁升级而 RECORD 级锁已足够演示死锁检测与可串行化调度。4.2 加锁流程LockManager 如何协调多个事务竞争以SELECT * FROM t1 WHERE id 5 FOR UPDATE为例显式加 X 锁ExecutionEngine调用LockManager::LockRow(txn, LockMode::EXCLUSIVE, table_oid, rid)LockManager检查lock_table_哈希表RID → std::listLockRequest中该rid_是否已被其他事务持 S/X 锁若冲突如已有 S 锁当前事务进入等待队列waiting_queue_并挂起线程若无冲突创建LockRequest插入lock_table_标记txn-GetSharedLockSet()-insert(rid)关键设计LockManager不持有任何锁的“所有权”它只是仲裁者。锁的实际生效依赖ExecutionExecutor在访问TableHeap前主动调用LockRow()—— 这是显式锁协议而非自动加锁。4.3 死锁检测基于等待图Wait-For Graph的周期判定RucBase 实现了一个轻量级死锁检测器每 10 秒扫描一次waiting_queue_构建等待图图节点 事务 IDtxn_id_t边T1 → T2T1等待T2持有的锁检测算法为 DFS 遍历找环。一旦发现环如T1→T2→T1选择环中txn_id最小的事务作为牺牲者victim调用TransactionManager::Abort(victim)回滚其所有修改并释放其持有的锁。血泪经验初学者常忽略FOR UPDATE的显式加锁直接SELECT后UPDATE导致更新时才发现锁冲突。RucBase 的严格 2PL 强迫你思考每一步的锁需求——这正是它教学价值所在。5. 避坑指南编译、运行与调试中 4 个高频翻车点RucBase 源码虽清晰但因其“去框架化”设计新手极易在细节处卡住。以下是我在带某高校数据库课程实验时学生提交的 137 份编译日志中统计出的最高频问题按现象→原因→解决给出可立即执行的方案。5.1 现象undefined reference to yylex—— 编译链接阶段报错原因yacc.tab.o生成后未将其加入rucbase_lib的源文件列表导致yylex()符号缺失。原始build_parser.sh生成的lex.yy.o未被 CMake 包含。解决编辑src/CMakeLists.txt在add_library列表末尾追加add_library(rucbase_lib STATIC # ... 原有文件 parser/yacc.tab.o parser/lex.yy.o )并确保parser/目录下已存在这两个.o文件若无按 2.3 节重新生成。5.2 现象Segmentation fault (core dumped)在CREATE TABLE后首次INSERT原因DiskManager初始化时db_file_name_被设为test.db但BufferPoolManager默认页数pool_size100而test.db文件初始为空。首次NewPage()时DiskManager::AllocatePage()返回INVALID_PAGE_ID后续PinPage()对无效页 ID 解引用崩溃。解决在main.cpp初始化DiskManager后强制预分配一页auto disk_manager std::make_uniqueDiskManager(test.db); auto bpm std::make_uniqueBufferPoolManager(100, disk_manager.get()); // 关键预分配第 0 页作为 catalog root page_id_t dummy_page_id; disk_manager-AllocatePage(dummy_page_id); // 此调用确保 test.db 文件被创建并写入 header5.3 现象SELECT * FROM t1返回空结果但INSERT明确返回OK原因TableHeap的InsertTuple()成功但Catalog未将表t1的table_oid与heap_page_id关联。execution/seq_scan_executor.cpp中Init()方法调用catalog_-GetTable()获取表信息时因catalog_未初始化table_heap_字段返回空指针。解决检查catalog/catalog.cpp中CreateTable()方法确保在table_heap_ std::make_uniqueTableHeap(...)后立即将table_heap_-GetFirstPageId()写入catalog_table_的heap_page_id列。补丁代码// 在 CreateTable() 函数末尾添加 auto meta_page catalog_table_-GetTupleMeta(0); auto meta_tuple catalog_table_-GetTuple(0); meta_tuple.SetValue(CATALOG_TABLE_COL_HEAP_PAGE_ID, Value(INTEGER, table_heap_-GetFirstPageId())); catalog_table_-UpdateTuple(meta_tuple, RID(0, 0), nullptr);5.4 现象多线程INSERT时B 树出现size_ max_size_断言失败原因BPlusTreeIndex::Insert()未对根页加锁多个线程同时Split()导致竞态。RucBase 的LockManager默认不保护索引内部结构需手动加table_oid级 X 锁。解决在execution/insert_executor.cpp的Execute()方法中在index_-InsertEntry()前显式申请表级锁// 在 InsertExecutor::Execute() 中tuple 插入 TableHeap 后 if (!exec_ctx_-GetLockManager()-LockTable(exec_ctx_-GetTransaction(), LockMode::EXCLUSIVE, table_info_-oid_)) { throw Exception(Lock table failed); } // 再插入索引 index_info_-index_-InsertEntry(key, rid, exec_ctx_-GetTransaction());注意此操作会降低并发度但保证了索引一致性——教学系统中宁可慢不可错。6. 进阶验证用 GDB 单步追踪一条 SQL 的完整生命周期当你能稳定运行rucbase下一步就是把它变成你的“数据库显微镜”。我习惯用 GDB 跟踪一条最简单的INSERT INTO t1 VALUES(1, a);观察从字符输入到磁盘落盘的每一步。这不是炫技而是建立对数据库内核的直觉。6.1 设置断点聚焦 4 个关键跃迁点在build/目录下启动 GDBgdb ./rucbase (gdb) b parser/yacc.tab.c:1234 # 假设这是 yyparse() 中 INSERT 语句规约完成点 (gdb) b execution/insert_executor.cpp:45 # Init() 开始处 (gdb) b storage/table_heap.cpp:89 # InsertTuple() 内存分配点 (gdb) b storage/disk_manager.cpp:210 # WritePage() 刷盘点 (gdb) r输入 SQL 后GDB 将在 4 个位置停住。重点关注每次停住时的变量yacc.tab.c停住时$1语义值应为InsertStatement*检查values_是否正确解析为Tupleinsert_executor.cpp停住时table_info_-oid_应为非零整数tuple_.GetFieldValue(0)应为1table_heap.cpp停住时page-GetFreeSpaceRemaining()应 tuple sizeslot_num应为有效索引disk_manager.cpp停住时page_id应等于table_heap_-GetFirstPageId()data指针应包含刚插入的 tuple 二进制。6.2 关键参数表GDB 中必查的 5 个变量及其业务含义变量名所在文件业务含义正常值示例异常提示stmt-values_[0].GetValue(0)parser/yacc.tab.cINSERT 语句第一个值idValue(INTEGER, 1)若为NULL说明词法分析失败table_info_-oid_execution/insert_executor.cpp表在 Catalog 中的唯一 ID101若为0GetTable()未找到表page-GetSlot(0)-rid_storage/table_heap.cpp第 0 个槽位的 RIDRID(100, 0)slot_num0但page_id异常说明页分配错误disk_manager_-GetFile().size()storage/disk_manager.cpp磁盘文件当前大小40961页若仍为0WritePage()未执行txn-GetSharedLockSet()-size()transaction/transaction.h事务当前持有锁数1TABLE 锁若为0锁未申请隔离性失效6.3 我的调试习惯用p/x查看内存布局比print更可靠GDB 中print可能因重载运算符显示不全而p/x十六进制打印直击本质。例如在table_heap.cpp断点处(gdb) p/x *(char*)page-GetData()32将打印页头 32 字节前 4 字节是page_id接着 4 字节是lsn再 4 字节是prev_page_id……这让你亲眼确认页头是否被正确初始化。当INSERT后SELECT返回空我第一反应就是p/x检查page-GetData()中的 tuple 是否真实写入——很多 bug 就藏在memcpy的偏移量计算里。最后说一句RucBase 的价值不在于它多快或多稳而在于它把数据库从“黑匣子”还原为“透明流水线”。我带过的 A同学最初连page_id和slot_num的区别都混淆但坚持用 GDB 跟完 3 条不同 SQL 后他能指着b_plus_tree_index.cpp说“这里如果去掉next_page_id_范围查询就退化成 N 次随机 IO”。那一刻他知道的不再是 API而是权衡。希望帮到你。本文还有配套的精品资源点击获取
