C++手写DBMS内核：从B+树到TPC-C的完整实现路径-北京尧图网络

简介本资源是全国大学生计算机系统能力大赛数据库管理系统赛道的完整参赛项目面向系统软件方向本科生与数据库内核学习者聚焦关系型数据库从零实现的核心能力训练。项目基于RMDB框架构建支持TPC-C基准测试的全功能RDBMS覆盖存储引擎、查询优化器、事务管理等内核模块可作为数据库原理课程设计、系统能力实训及内核源码研读的高质量实践范例。压缩包共442个文件以121个C/C头文件h/hpp与102个C源文件cc/cpp构成主体代码层辅以47个Python脚本自动化测试与工具、30个Markdown文档设计说明与实验记录及5个PDF技术报告整体仅2.43MB结构紧凑、模块边界清晰。目前已有72人学习下载读者可直接获取完整可编译工程、TPC-C负载集成方案、Bazel/CMake双构建支持及关键组件如词法分析lex.yy.c、GTest单元测试用例的详细实现逻辑快速切入数据库系统开发实战。1. 为什么一个学生团队敢从零手写存储引擎、优化器和事务模块——这不是课程设计而是用 C 实现可跑 TPC-C 的完整 DBMS 内核你见过凌晨三点还在调 B 树页分裂逻辑的本科生吗我带过几届某高校数据库系统能力大赛参赛队最深的体会是当学生真正把BufferPoolManager的 pin_count 和 latch 顺序搞明白时ta 对 ACID 的理解已经远超照着《数据库系统概念》划重点的研究生。这个标题不是包装话术它指向一个真实存在的技术路径用纯 C不依赖 SQLite、LevelDB 或任何嵌入式引擎实现支持完整 SQL 解析、基于代价的查询优化、WAL 日志 ARIES 风格崩溃恢复、多版本并发控制MVCC的单机关系型数据库内核并通过 TPC-C 基准验证其 OLTP 能力。它不追求吞吐碾压 PostgreSQL但要求每个模块——从磁盘页读写、索引结构、执行算子到锁管理——都由参赛者亲手编码、调试、压测。适合两类人一是想撕开数据库黑匣子、拒绝“会用就行”的系统级学习者二是准备冲击系统能力大赛数据库赛道、需要可复现、可答辩、可现场 demo 的硬核项目方案者。本文不讲理论推导只讲怎么在 3 个月内把src/storage/page/table_page.h从空文件变成能扛住 100 并发订单插入的生产级结构。2. 从零构建存储引擎B 树索引与 WAL 日志的协同落地数据库内核的根基不在 SQL 解析器而在数据如何落盘、如何被快速定位、如何在崩溃后不丢。学生项目最容易翻车的地方就是把存储引擎当成“配角”结果优化器再 fancy一写入就 core dump。我们坚持一个原则先让单线程下的 insert/select 正确跑通再加并发最后上 WAL。跳过这步后面所有优化都是空中楼阁。2.1 表页与索引页的物理布局为什么必须手写 PageHeader很多团队直接套用现有内存池框架却忽略了一个致命细节页头PageHeader必须包含page_id_t、lsn_t、pin_count、is_dirty和next_free_offset这五个字段且顺序不能错。这是后续 WAL 日志解析、缓冲区淘汰、页面重用的契约基础。例如next_free_offset决定了新记录插入位置若未初始化或更新不同步会导致记录覆盖、页内碎片无法回收。// src/storage/page/page.h struct PageHeader { page_id_t page_id_; // 该页在磁盘上的唯一 ID lsn_t lsn_; // 最后一次修改该页的日志序列号WAL 关键 int32_t pin_count_; // 当前被多少个线程/事务 pin 住防止被换出 bool is_dirty_; // 是否被修改过决定刷盘时机 int32_t next_free_offset_; // 下一个可用字节偏移指向空闲区起始 };提示page_id_t必须是全局唯一整数如从 0 开始递增不能用指针地址或随机数。lsn_t在无 WAL 阶段可设为 0但结构体必须预留否则加 WAL 时要重构所有页结构血泪经验。2.2 B 树索引的最小可行实现只支持点查与范围扫描的 LeafNode学生常陷入“必须支持所有 B 树操作”的误区。实际参赛中只要能正确完成SELECT * FROM orders WHERE o_w_id ? AND o_d_id ? AND o_id ?的等值查找就满足 TPC-C 的主键查询需求。因此我们砍掉复杂的合并、借位逻辑聚焦于LeafNode的分裂与InternalNode的键提升。关键约束每个叶子节点固定存 64 条记录按 TPC-Corders表 128 字节/行估算内部节点存 128 个键节省空间。分裂时新节点取后半部分记录父节点插入新键右子节点最小键和新子节点 ID。// src/storage/index/b_plus_tree.cpp bool BPlusTree::Insert(const KeyType key, const ValueType value) { // 1. 从根开始查找沿途记录 path用于分裂后更新父节点 std::vectorPage * path; auto leaf FindLeaf(key, path); // 2. 尝试插入到 leaf若满则分裂 if (!leaf-Insert(key, value)) { auto new_leaf SplitLeaf(leaf); // 3. 向上回溯将 new_leaf 的最小键和 ID 插入父节点 InsertIntoParent(path, leaf, new_leaf); } return true; } Page *BPlusTree::SplitLeaf(Page *leaf) { auto new_leaf buffer_pool_manager_-NewPage(); // 申请新页 // 将 leaf 后半记录 memcpy 到 new_leaf int split_point leaf-GetSize() / 2; for (int i split_point; i leaf-GetSize(); i) { new_leaf-Insert(leaf-KeyAt(i), leaf-ValueAt(i)); } leaf-SetSize(split_point); // 截断原页 return new_leaf; }逻辑说明FindLeaf返回叶子页指针并通过path参数返回从根到叶子的路径含所有内部节点指针这是分裂后向上更新父节点的唯一依据。SplitLeaf不做键复制只移动数据避免二次遍历。InsertIntoParent是核心难点若父节点也满则递归分裂直到根节点——此时需新建根树高1。参数说明GetSize()返回当前页有效记录数KeyAt(i)和ValueAt(i)是安全访问接口内部检查边界buffer_pool_manager_-NewPage()是缓冲区管理器接口返回可写的干净页。3. 查询优化器落地从语法树到物理计划的三步剪枝TPC-C 的 SQL 模板高度结构化9 个固定事务SQL 模式极少这让学生优化器不必追求通用性而应聚焦确定性、可解释、易调试。我们放弃基于规则的复杂重写如子查询上拉、视图合并采用“三步剪枝法”语法树 → 逻辑计划 → 物理计划每步只做必要转换且全程保留原始 SQL 注释方便答辩时逐行溯源。3.1 语法树到逻辑计划只做投影下推与谓词下推SELECT o_id, o_carrier_id FROM orders WHERE o_w_id 1 AND o_d_id 2这类查询逻辑计划只需两步谓词下推WHERE条件直接附加到TableScan算子而非在顶层Filter投影下推只从磁盘读取o_id和o_carrier_id两列跳过其他 12 列。// src/optimizer/logical_plan_builder.cpp std::unique_ptrLogicalOperator BuildPlan(const ASTNode ast) { if (ast.type SELECT_STMT) { auto table_scan std::make_uniqueLogicalTableScan(ast.table_name); // 谓词下推将 WHERE 条件转为 ScanPredicate if (ast.where_condition) { table_scan-predicate_ BuildPredicate(ast.where_condition); } // 投影下推只请求需要的列 table_scan-output_columns_ ast.select_columns; // 若有 GROUP BY 或 ORDER BY才添加对应算子 if (!ast.group_by_columns.empty()) { auto group_by std::make_uniqueLogicalGroupBy(); group_by-children_.push_back(std::move(table_scan)); return group_by; } return table_scan; } return nullptr; }逻辑说明BuildPredicate将 AST 中的o_w_id 1解析为ColumnRef(o_w_id) Constant(1)结构供后续选择索引时匹配。output_columns_直接传给TableScan驱动存储层只读指定列需在TablePage::GetTuple中实现列裁剪。3.2 逻辑计划到物理计划基于代价的索引选择仅主键TPC-C 所有表均以(w_id, d_id, id)为复合主键。因此物理优化器只需判断 WHERE 条件是否覆盖最左前缀WHERE w_id ?→ 用主键索引范围扫描WHERE w_id ? AND d_id ?→ 用主键索引范围扫描WHERE d_id ?→ 全表扫描无索引可用不实现二级索引、不考虑 join 顺序TPC-C 无多表 join极大降低复杂度。// src/optimizer/physical_planner.cpp std::unique_ptrPhysicalOperator ChooseIndexScan( const std::string table_name, const std::vectorstd::pairstd::string, Value predicates) { // 检查 predicates 是否包含 w_id主键第一列 bool has_w_id false; for (const auto p : predicates) { if (p.first w_id) { has_w_id true; break; } } if (has_w_id) { return std::make_uniquePhysicalIndexScan(table_name, predicates); } return std::make_uniquePhysicalTableScan(table_name); }参数说明predicates是从BuildPredicate提取的列值对向量格式为{w_id, 1}, {d_id, 2}PhysicalIndexScan内部调用BPlusTree::Search定位叶子页再遍历匹配d_id和idPhysicalTableScan则顺序读取所有页。4. 事务与并发控制MVCC 两阶段锁2PL的轻量级融合实现TPC-C 要求严格一致性如 NewOrder 事务中库存扣减与订单插入的原子性但学生项目无法承担 full MVCC 的垃圾回收开销。我们的解法是用 2PL 保证写冲突串行化用 MVCC 快照隔离读操作二者共用同一版本链。这比纯 2PL 减少读写阻塞比纯 MVCC 降低 GC 复杂度是大赛场景下的黄金折中。4.1 版本链结构TupleHeader 里藏三个时间戳每个元组Tuple头部扩展TupleHeader存create_tx_id_、delete_tx_id_和prev_version_offset_// src/storage/tuple/tuple.h struct TupleHeader { txn_id_t create_tx_id_; // 创建该版本的事务 ID txn_id_t delete_tx_id_; // 删除该版本的事务 ID0 表示未删 int32_t prev_version_offset_; // 指向前一版本在页内的偏移负数表示无效 }; class Tuple { TupleHeader header_; char data_[]; };逻辑说明create_tx_id_和delete_tx_id_构成可见性判断基础prev_version_offset_形成单向链表新版本总在旧版本之后分配空间页内追加避免链表断裂。事务开始时记录当前max_committed_tx_id_作为快照读取时沿链表向上找第一个满足create_tx_id_ snapshot (delete_tx_id_ 0 || delete_tx_id_ snapshot)的版本。4.2 两阶段锁协议2PL的极简实现只锁主键页TPC-C 所有写操作必通过主键定位如UPDATE stock SET s_quantity ? WHERE s_w_id ? AND s_i_id ?因此锁管理器只需维护page_id_t到std::shared_mutex的映射而非行级锁。事务执行时加锁阶段对涉及的所有主键页通过 B 树查找路径获得调用lock_manager_-LockShared(page_id)或LockExclusive(page_id)解锁阶段事务提交/回滚时统一释放所有已持锁。不实现意向锁IX/SIX因无嵌套事务不实现死锁检测用超时替代因 TPC-C 场景锁持有时间极短。// src/concurrency/lock_manager.cpp void LockManager::LockExclusive(txn_id_t txn_id, page_id_t page_id) { std::unique_lockstd::shared_mutex lock(mutex_); auto page_locks page_lock_table_[page_id]; // 若已有其他事务持有 X 锁等待 if (page_locks.exclusive_owner_ ! INVALID_TXN_ID) { page_locks.waiting_x_.push(txn_id); cv_.wait(lock, [this, page_id] { return page_lock_table_[page_id].exclusive_owner_ INVALID_TXN_ID; }); } page_locks.exclusive_owner_ txn_id; }参数说明page_lock_table_是std::unordered_mappage_id_t, PageLockPageLock包含exclusive_owner_当前 X 锁持有者、shared_owners_S 锁持有者集合、waiting_x_等待 X 锁的事务队列cv_是条件变量用于等待锁释放。5. 避坑指南TPC-C 压测中 5 个高频翻车点与血泪修复方案学生项目在 TPC-C 压测环节失败率超 70%多数源于对底层机制的“想当然”。以下是我们在三届比赛中反复验证的 5 个致命坑每条都附现场gdb截图级排查路径。5.1 现象TPC-Cnew_order事务在 50 并发时出现重复订单号o_id 冲突原因o_id生成未加锁多个事务同时读取warehouse.w_ytd后自增导致相同o_id写入。解决在WarehouseTable::GetNextOrderId()中对w_id对应的仓库页加LockExclusive读取w_ytd后立即w_ytd并MarkDirty()再释放锁。禁止在锁外修改。5.2 现象payment事务执行缓慢perf record -e cache-misses显示 L3 缓存缺失率 40%原因B 树内部节点未预加载每次查找都要buffer_pool_manager_-FetchPage()引发大量磁盘 I/O。解决在BPlusTree::Search开头对根节点及路径上所有内部节点调用buffer_pool_manager_-PinPage()确保其驻留内存查找结束后对非叶子节点调用UnpinPage(false)不刷盘。5.3 现象WAL 日志写入后进程崩溃重启stock表部分更新丢失原因WAL 日志写入log_buffer_后未fsync()到磁盘崩溃时缓冲区数据丢失。解决在LogManager::AppendLogRecord()末尾当log_buffer_.size() LOG_BUFFER_SIZE或事务提交时调用log_file_-Flush()内部执行fsync(fd)。注意LOG_BUFFER_SIZE设为 4KB与磁盘块对齐。5.4 现象order_status查询返回空结果但SELECT COUNT(*) FROM orders显示数据存在原因MVCC 可见性判断错误delete_tx_id_被误设为INVALID_TXN_ID应为 0导致已删除版本被误读。解决统一约定delete_tx_id_ 0表示“未删除”delete_tx_id_ INVALID_TXN_ID表示“该字段未初始化”在Tuple::Init()中强制header_.delete_tx_id_ 0。5.5 现象buffer_pool_manager_在高并发下频繁触发VictimPage()命中率低于 30%原因replacer_驱逐策略使用 LRU但未区分 pinned 页面导致正被事务使用的页被错误换出。解决改用ClockReplacer环形链表 use_bitPinPage()时置use_bit1UnpinPage()时仅减pin_countVictimPage()遍历时若use_bit1则置 0 并跳过否则驱逐。ClockReplacer在 100 并发下缓存命中率稳定在 85%。注意所有修复必须通过./test/buffer_pool_test和./test/transaction_test单元测试禁止仅靠 TPC-C 压测验证。6. TPC-C 基准验证从生成数据到解读 3 个核心指标的实操手册TPC-C 不是“跑个脚本看吞吐”而是通过 5 类事务NewOrder、Payment、OrderStatus、Delivery、StockLevel的混合负载验证系统在 ACID、可扩展性、稳定性三方面的硬实力。学生项目常止步于“能跑”但大赛答辩要求你能说清为什么我的 100 tpmC 是可靠的瓶颈在哪如何证明没作弊以下是我们验证全流程。6.1 数据生成用官方tpcc_build工具但必须校验 3 个关键约束TPC-C 规范强制要求warehouse表10 个仓库w_id从 1 到 10每个仓库w_ytd 300000.00district表每个仓库 10 个分区d_id从 1 到 10d_ytd 30000.00customer表每个分区 3000 个客户c_id从 1 到 3000c_balance -10.00。生成后必须执行 SQL 校验-- 校验 warehouse 总数与 ytd SELECT COUNT(*), SUM(w_ytd) FROM warehouse; -- 应返回10 | 3000000.00 -- 校验 district 分布 SELECT w_id, COUNT(*) FROM district GROUP BY w_id; -- 每个 w_id 应返回 10 -- 校验 customer 均匀性 SELECT d_w_id, d_id, COUNT(*) FROM customer c JOIN district d ON c.c_d_id d.d_id AND c.c_w_id d.d_w_id GROUP BY d_w_id, d_id; -- 每个 (d_w_id, d_id) 应返回 3000提示tpcc_build默认生成 1 仓数据需加-w 10参数若用自定义生成器必须输出tpcc_output目录下*.tbl文件并用LOAD DATA INFILE导入不可用INSERT循环太慢且易超时。6.2 压测执行tpcc_start的 4 个必调参数与日志解析我们固定使用tpcc_start非tpcc_worker命令如下./tpcc_start -h localhost -P 8080 -d tpcc_db -u root -p pass \ -w 10 -c 10 -r 10 -l 300 -f tpcc_report.log参数说明-w 1010 个仓库与数据一致-c 1010 个并发连接非线程数每个连接模拟一个终端-r 10预热 10 秒跳过冷启动抖动-l 300持续压测 300 秒5 分钟足够观察稳态-f输出详细日志含每秒事务计数tpmC和响应时间分布。关键日志字段解析tpcc_report.log字段含义合格线诊断意义tq新订单事务数NewOrder≥ 90% 总事务主力事务占比低说明索引失效或锁争用pq支付事务数Payment≥ 5% 总事务验证 UPDATE 性能偏低可能 WAL 写入慢90th pct latency (ms)90% 事务响应时间≤ 100 ms超过则需perf top查热点函数retries事务重试次数 0非零说明锁冲突严重需检查 2PL 实现6.3 指标解读tpmC、Price/tpmC 与稳定性三角验证大赛评分不只看峰值 tpmC更看重三者平衡tpmCTransactions per Minute C标准公式tpmC (NewOrder 成功数 × 60) / 测试秒数。我们目标10 仓下 ≥ 800 tpmC单机 C 实现合理上限Price/tpmC虽不真买硬件但需在报告中声明“假设部署于 16 核 32GB 云服务器年成本约 XXX 元”体现成本意识稳定性连续 3 次 300 秒压测tpmC 波动 ±5%且90th pct latency无毛刺用gnuplot绘制时间序列图。我们曾发现某次 tpmC 达 850但retries为 1290th latency在 200ms 波动——经查是StockLevel事务未加锁导致SELECT COUNT(*)与UPDATE冲突。修复后 tpmC 降至 790但retries0latency45ms最终得分更高。最后一句我带过的冠军队没有一个是在截止日前一周才开始写代码的。他们从 3 月就建好BufferPoolManager的单元测试骨架4 月跑通单线程INSERT/SELECT5 月加 WAL 和事务6 月集成 TPC-C。真正的竞争力从来不是最后炫技的 demo而是每一天git commit -m fix: btree split crash on full leaf的踏实。希望帮到你。本文还有配套的精品资源点击获取

C++手写DBMS内核：从B+树到TPC-C的完整实现路径

相关推荐

顺序、并行、辩论、会商：OpenMAIC 四种交互模式背后的编排逻辑

16G 显存党实测：量化版 H3 变体本地出片的完整路径

889张电力红外数据集：互感器检测与YOLO训练避坑指南

更多资讯

AI让数学再也回不去那个旧世界了。

Python Java PHP底层对比：内存并发性能全解析

P1185 绘制二叉树【洛谷算法习题】

一次性贴身服饰的三层洁净工艺：水洗、灭菌与面料抑菌的技术实现

BSP 调试#01：点亮 LED

高级表单能力

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？