簡介這份資源是面向計(jì)算機(jī)專業(yè)學(xué)生與數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)學(xué)習(xí)者的RucBase關(guān)系數(shù)據(jù)庫管理系統(tǒng)C源碼工程參考CMU15445的BusTub與Stanford CS346的Redbase設(shè)計(jì)適合作為《數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)》課程實(shí)驗(yàn)框架幫助理解并動(dòng)手實(shí)現(xiàn)數(shù)據(jù)庫核心模塊。包內(nèi)共185個(gè)文件以58個(gè)h頭文件、34個(gè)cpp源文件、35個(gè)txt說明、20個(gè)sql腳本為主另含少量Python腳本、Markdown文檔與圖片壓縮包約1.36MB目錄結(jié)構(gòu)清晰便于按模塊檢索。內(nèi)容覆蓋數(shù)據(jù)庫與表管理、索引創(chuàng)建刪除、事務(wù)提交終止、鎖管理器實(shí)現(xiàn)的共享鎖與排他鎖、日志記錄與恢復(fù)、SQL語義分析與執(zhí)行計(jì)劃生成以及緩沖池與磁盤管理器的頁面讀寫替換策略并附有B樹并發(fā)與刪除測試、緩沖池管理器測試等用例。已有56人學(xué)習(xí)適合需要完整實(shí)驗(yàn)框架、源碼參考與測試樣例的讀者深入研讀。1. 從一份 C 源碼包說起RucBase 到底能跑出什么如果你正在搜「C 數(shù)據(jù)庫管理系統(tǒng)源碼」大概率會(huì)撞見兩類東西一類是動(dòng)輒幾十萬行的工業(yè)級項(xiàng)目clone 下來連編譯都過不去另一類是只有幾百行的玩具跑完SELECT 1就沒了下文。RucBase 卡在中間——它是一個(gè)教學(xué)向的 RDBMS 原型參考了 CMU 15-445 的 BusTub 和 Stanford CS346 的 Redbase把數(shù)據(jù)庫內(nèi)核拆成存儲(chǔ)、索引、查詢、事務(wù)、日志幾個(gè)可獨(dú)立動(dòng)手的模塊。這份源碼包里能看到y(tǒng)acc.tab.c、lex.yy.c這類詞法語法分析產(chǎn)物也有ix_index_handle.cpp、b_plus_tree_concurrent_test.cpp、buffer_pool_manager_test.cpp這些索引與緩沖池的實(shí)現(xiàn)和測試文件說明它不是一個(gè)空殼框架而是帶著可編譯、可跑測試的完整鏈路。適合誰正在做數(shù)據(jù)庫課程設(shè)計(jì)的學(xué)生、想補(bǔ)數(shù)據(jù)庫內(nèi)核實(shí)操的后端工程師、以及需要一份能改能調(diào)的 C 項(xiàng)目練手的人。它不承諾生產(chǎn)級性能但能讓你把「B 樹怎么并發(fā)、緩沖池怎么替換、SQL 怎么變成執(zhí)行計(jì)劃」這些黑匣子親手拆一遍。2. 把源碼跑起來從 yacc/lex 到第一個(gè)可執(zhí)行測試2.1 先看清目錄里有什么再?zèng)Q定編譯順序拿到壓縮包解壓后別急著make。先花兩分鐘掃一遍文件構(gòu)成能省掉后面半小時(shí)的鏈接報(bào)錯(cuò)。這份源碼里幾類文件承擔(dān)不同職責(zé)文件/目錄作用編譯階段yacc.tab.c/yacc.tab.cpp語法分析器由 yacc/bison 生成先于業(yè)務(wù)代碼lex.yy.c/lex.yy.cpp詞法分析器由 lex/flex 生成先于業(yè)務(wù)代碼ix_index_handle.cpp索引句柄B 樹對外接口業(yè)務(wù)層b_plus_tree_concurrent_test.cpp并發(fā) B 樹測試測試層buffer_pool_manager_test.cpp緩沖池替換策略測試測試層disk_manager.cpp磁盤頁讀寫存儲(chǔ)層planner.cpp查詢計(jì)劃生成查詢層常見做法是詞法語法文件先由工具生成 C/C 源再和業(yè)務(wù).cpp一起交給編譯器。如果你直接改yacc.tab.c而不改.y源文件下次重新生成就會(huì)被覆蓋——這是新手最容易翻車的地方。2.2 環(huán)境配置編譯器、構(gòu)建工具和依賴RucBase 是 C 項(xiàng)目對工具鏈版本有要求。我一般會(huì)先確認(rèn)三件事編譯器支持 C17、CMake 版本不低于 3.10、系統(tǒng)里有 flex 和 bison。下面這套命令在 Ubuntu 22.04 上驗(yàn)證過其他發(fā)行版把包管理器換掉即可。# 安裝編譯工具鏈與詞法語法分析器 sudo apt update sudo apt install -y build-essential cmake flex bison # 確認(rèn)版本C17 是硬門檻 g --version # 期望 9.0 cmake --version # 期望 3.10 flex --version bison --version邏輯說明build-essential提供 g 和 makecmake負(fù)責(zé)生成構(gòu)建文件flex/bison用來從.l/.y重新生成詞法語法分析器。參數(shù)上唯一要盯的是 g 版本低于 9 會(huì)在std::filesystem和結(jié)構(gòu)化綁定上直接報(bào)錯(cuò)。如果你在 Windows 上常見做法是用 WSL2 或 MSYS2不要硬扛 MSVC——這份源碼的構(gòu)建腳本默認(rèn)按類 Unix 環(huán)境寫。2.3 編譯與運(yùn)行第一個(gè)測試環(huán)境就緒后標(biāo)準(zhǔn)流程是建 build 目錄、cmake 生成、make 編譯。不要在原目錄里直接 cmake產(chǎn)物和源碼混在一起清理時(shí)很痛苦。# 在項(xiàng)目根目錄下創(chuàng)建獨(dú)立構(gòu)建目錄 mkdir -p build cd build # 生成構(gòu)建文件Debug 模式便于調(diào)試 cmake -DCMAKE_BUILD_TYPEDebug .. # 編譯-j 后面跟 CPU 核心數(shù)加快速度 make -j$(nproc)邏輯說明CMAKE_BUILD_TYPEDebug會(huì)帶上-g和關(guān)閉優(yōu)化方便你用 gdb 跟棧如果只想跑測試看結(jié)果可以換成Release。make -j$(nproc)用滿所有核心但第一次編譯建議先不加-j讓報(bào)錯(cuò)順序清晰定位缺失依賴更快。編譯完成后測試可執(zhí)行文件通常在build/test/或build/bin/下。先跑緩沖池測試它依賴最少# 運(yùn)行緩沖池管理器測試 ./test/buffer_pool_manager_test # 運(yùn)行并發(fā) B 樹測試 ./test/b_plus_tree_concurrent_test如果buffer_pool_manager_test全綠說明存儲(chǔ)層和頁管理沒問題b_plus_tree_concurrent_test通過說明索引層的鎖和并發(fā)控制邏輯是通的。這兩個(gè)測試是判斷「這份源碼是否完整可用」的最快信號。2.4 用 SQL 走一遍完整鏈路測試跑通只證明模塊能獨(dú)立工作真正要驗(yàn)證的是 SQL 從輸入到執(zhí)行計(jì)劃的整條鏈路。RucBase 自帶交互式 shell啟動(dòng)方式一般是# 啟動(dòng)數(shù)據(jù)庫 shell具體路徑以編譯產(chǎn)物為準(zhǔn) ./bin/rucbase進(jìn)入后可以執(zhí)行建庫建表、插入、查詢-- 創(chuàng)建數(shù)據(jù)庫并切換 CREATE DATABASE testdb; USE testdb; -- 建表帶主鍵和索引 CREATE TABLE student (id INT PRIMARY KEY, name VARCHAR(32), score INT); CREATE INDEX idx_score ON student(score); -- 插入數(shù)據(jù) INSERT INTO student VALUES (1, alice, 90); INSERT INTO student VALUES (2, bob, 85); -- 查詢觀察是否走索引 SELECT * FROM student WHERE score 86;邏輯說明CREATE INDEX會(huì)觸發(fā)ix_index_handle.cpp里的 B 樹插入邏輯SELECT ... WHERE score 86會(huì)經(jīng)過planner.cpp生成執(zhí)行計(jì)劃。如果你在輸出里看到計(jì)劃選擇了索引掃描而非全表掃描說明查詢優(yōu)化模塊是活的。參數(shù)上注意VARCHAR(32)的長度要和存儲(chǔ)頁大小匹配超長字符串會(huì)被截?cái)嗷驁?bào)錯(cuò)。3. 拆開 B 樹與緩沖池索引和存儲(chǔ)層怎么改、怎么驗(yàn)3.1 B 樹的并發(fā)控制鎖的粒度決定測試能不能過b_plus_tree_concurrent_test.cpp和b_plus_tree_delete_test.cpp是這份源碼里含金量最高的兩個(gè)測試文件。它們驗(yàn)證的不是「B 樹能不能插」而是「多線程同時(shí)插刪時(shí)樹結(jié)構(gòu)會(huì)不會(huì)崩」。B 樹的并發(fā)難點(diǎn)在于分裂和合并會(huì)修改父節(jié)點(diǎn)如果只鎖當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)可能被另一個(gè)線程同時(shí)改掉。常見做法是 crabbing 協(xié)議——加鎖時(shí)先鎖子節(jié)點(diǎn)再釋放父節(jié)點(diǎn)或者用 latch coupling 從根一路鎖到葉子。RucBase 的ix_index_handle.cpp里能看到對應(yīng)的鎖獲取和釋放邏輯。你改這塊代碼時(shí)要盯住三個(gè)點(diǎn)讀操作是否用了共享鎖寫操作用排他鎖節(jié)點(diǎn)分裂時(shí)父節(jié)點(diǎn)的鎖是否在子節(jié)點(diǎn)鎖獲取后才釋放刪除導(dǎo)致合并時(shí)是否處理了「兄弟節(jié)點(diǎn)也被鎖住」的死鎖場景。// 偽代碼示意B 樹插入時(shí)的 crabbing 加鎖順序 // 從根開始先鎖子再放父避免持有父鎖等待子鎖 auto child root; root-RLatch(); // 根節(jié)點(diǎn)加讀鎖 while (!child-IsLeaf()) { auto next child-Lookup(key); next-RLatch(); // 先鎖子節(jié)點(diǎn) child-RUnlatch(); // 再釋放父節(jié)點(diǎn) child next; } child-WLatch(); // 葉子節(jié)點(diǎn)加寫鎖準(zhǔn)備插入 // ... 執(zhí)行插入與可能的分裂 ... child-WUnlatch();邏輯說明這段不是讓你照抄而是說明加鎖順序。RLatch/WLatch是讀寫鎖Lookup根據(jù) key 找下一層。關(guān)鍵參數(shù)是鎖的持有時(shí)間——持有越短并發(fā)越高但太短會(huì)導(dǎo)致結(jié)構(gòu)不一致。跑b_plus_tree_concurrent_test時(shí)如果出現(xiàn)段錯(cuò)誤或斷言失敗九成是加鎖順序反了。3.2 緩沖池替換策略LRU-K 的 K 怎么選buffer_pool_manager_test.cpp驗(yàn)證的是頁面替換。RucBase 的緩沖池管理器負(fù)責(zé)把磁盤頁讀進(jìn)內(nèi)存幀滿了就按策略淘汰。教學(xué)項(xiàng)目里常見的是 LRU 或 LRU-KK 表示參考最近 K 次訪問。K 越大越能抵抗「掃描一遍大表把熱頁全沖掉」的問題但實(shí)現(xiàn)復(fù)雜度和內(nèi)存開銷也上去。改這塊代碼時(shí)參數(shù)選擇直接影響測試通過率參數(shù)含義常見取值影響KLRU-K 的歷史窗口2K1 退化成 LRUK 太大冷啟動(dòng)慢幀數(shù)緩沖池大小測試?yán)锿ǔ?10~50太小頻繁淘汰太大測不出策略差異淘汰閾值歷史訪問次數(shù)門檻2低于閾值優(yōu)先淘汰// 緩沖池取頁的核心邏輯示意 Page* BufferPoolManager::FetchPage(page_id_t page_id) { std::lock_guardstd::mutex lock(latch_); // 1. 先在頁表里找命中直接返回并更新訪問記錄 auto it page_table_.find(page_id); if (it ! page_table_.end()) { frame_id_t fid it-second; replacer_-RecordAccess(fid); // 更新 LRU-K 歷史 return pages_[fid]; } // 2. 未命中找一個(gè)空閑幀或淘汰一個(gè) victim frame_id_t fid; if (!free_list_.empty()) { fid free_list_.front(); free_list_.pop_front(); } else if (!replacer_-Evict(fid)) { return nullptr; // 所有幀都被釘住取頁失敗 } // 3. 把磁盤頁讀進(jìn)幀更新頁表 disk_manager_-ReadPage(page_id, pages_[fid].GetData()); page_table_[page_id] fid; replacer_-RecordAccess(fid); return pages_[fid]; }邏輯說明RecordAccess是替換策略的輸入Evict是輸出。參數(shù)上要特別注意「釘住」的頁不能被淘汰——如果測試?yán)锍霈F(xiàn)FetchPage返回nullptr先檢查是不是有頁忘了UnpinPage。這是血淚經(jīng)驗(yàn)緩沖池測試掛掉一半是替換策略寫錯(cuò)另一半是 pin 計(jì)數(shù)沒配對。3.3 磁盤管理器頁讀寫與持久化邊界disk_manager.cpp是存儲(chǔ)層最底下的那塊負(fù)責(zé)把頁寫到文件、從文件讀回來。它不復(fù)雜但邊界條件多文件偏移怎么算、頁號越界怎么處理、寫失敗要不要回滾。常見做法是每個(gè)頁固定大小比如 4KB頁號乘以頁大小就是文件偏移。// 磁盤頁讀寫示意 void DiskManager::WritePage(page_id_t page_id, const char* data) { // 頁號轉(zhuǎn)文件偏移頁大小固定 off_t offset static_castoff_t(page_id) * PAGE_SIZE; // 定位并寫入整頁 if (lseek(fd_, offset, SEEK_SET) -1) { throw std::runtime_error(lseek failed); } ssize_t n write(fd_, data, PAGE_SIZE); if (n ! PAGE_SIZE) { throw std::runtime_error(short write); } }邏輯說明PAGE_SIZE要和緩沖池、B 樹節(jié)點(diǎn)大小保持一致改一處就得全改。lseek的返回值必須檢查write的短寫也必須處理——這兩個(gè)是文件 IO 最常見的翻車點(diǎn)。如果你在測試?yán)锟吹綌?shù)據(jù)讀回來是亂碼先確認(rèn)寫的時(shí)候偏移算對了沒有。4. 查詢鏈路與事務(wù)日志planner 和恢復(fù)怎么串起來4.1 從 SQL 文本到執(zhí)行計(jì)劃planner 的輸入輸出planner.cpp處在查詢層的核心位置它接收語法分析后的抽象語法樹輸出可執(zhí)行的計(jì)劃樹。RucBase 作為教學(xué)原型計(jì)劃節(jié)點(diǎn)通常包括順序掃描、索引掃描、投影、過濾、連接這幾類。你要改優(yōu)化規(guī)則就在這一層動(dòng)手。一個(gè)典型的鏈路是lex.yy.c把 SQL 切成 tokenyacc.tab.c按語法規(guī)則組裝成 ASTplanner 遍歷 AST 生成計(jì)劃執(zhí)行器再遞歸執(zhí)行計(jì)劃節(jié)點(diǎn)。如果你發(fā)現(xiàn)某條 SQL 報(bào)「語法錯(cuò)誤」但 SQL 本身沒問題先去看.y文件里的語法規(guī)則是不是沒覆蓋這種寫法。// 計(jì)劃生成示意把 WHERE 條件轉(zhuǎn)成過濾節(jié)點(diǎn) std::unique_ptrAbstractPlanNode Planner::PlanSelect( const SelectStatement* stmt) { // 1. 先為 FROM 子句生成掃描節(jié)點(diǎn) auto scan PlanTableRef(stmt-from_); // 2. 如果有 WHERE包一層過濾 if (stmt-where_ ! nullptr) { auto filter std::make_uniqueFilterPlanNode( PlanExpression(stmt-where_), std::move(scan)); scan std::move(filter); } // 3. 最后套投影決定輸出哪些列 return std::make_uniqueProjectionPlanNode( stmt-select_, std::move(scan)); }邏輯說明PlanTableRef決定用全表掃描還是索引掃描PlanExpression把條件表達(dá)式轉(zhuǎn)成可求值的節(jié)點(diǎn)。參數(shù)上要注意投影和過濾的順序——先過濾再投影能減少中間數(shù)據(jù)量如果寫反了性能會(huì)差但結(jié)果正確測試不一定抓得出來。4.2 事務(wù)與鎖管理器行級鎖和表級鎖怎么配合RucBase 的并發(fā)控制通過鎖管理器實(shí)現(xiàn)支持行級和表級的共享鎖、排他鎖。事務(wù)開始、提交、終止對應(yīng)鎖的獲取和釋放。這塊最容易出的問題是鎖升級和死鎖一個(gè)事務(wù)先拿行鎖再要表鎖另一個(gè)反過來就死鎖了。常見做法是給鎖請求排個(gè)全序或者用死鎖檢測定期掃等待圖。教學(xué)項(xiàng)目里通常簡化成「按固定順序加鎖」。你寫事務(wù)測試時(shí)可以構(gòu)造兩個(gè)事務(wù)交叉訪問同一批行觀察是否有一個(gè)被回滾。-- 事務(wù)交叉訪問示意 -- 事務(wù) A BEGIN; UPDATE student SET score 91 WHERE id 1; -- 此時(shí)不提交事務(wù) B 嘗試更新同一行會(huì)阻塞或失敗邏輯說明BEGIN之后鎖才生效COMMIT或ABORT釋放。參數(shù)上注意隔離級別——RucBase 教學(xué)版通常只實(shí)現(xiàn)到可串行化或可重復(fù)讀不要假設(shè)它有完整的 MVCC。4.3 日志管理與恢復(fù)WAL 的順序不能亂日志管理支持記錄和恢復(fù)核心是 WAL預(yù)寫日志先寫日志再寫數(shù)據(jù)頁崩潰后才能重放。disk_manager.cpp寫頁之前日志必須已經(jīng)落盤。如果你改恢復(fù)邏輯要保證 redo 和 undo 的順序正確。日志類型作用恢復(fù)階段BEGIN標(biāo)記事務(wù)開始分析階段UPDATE記錄前像和后像redo/undoCOMMIT標(biāo)記事務(wù)提交分析階段ABORT標(biāo)記事務(wù)回滾undo邏輯說明分析階段確定哪些事務(wù)要 redo、哪些要 undoredo 階段重放已提交的修改undo 階段回滾未提交的修改。參數(shù)上注意 LSN日志序列號的單調(diào)遞增亂了就恢復(fù)錯(cuò)亂。5. 避坑與排查編譯、鏈接、運(yùn)行時(shí)的五類翻車現(xiàn)場5.1 現(xiàn)象undefined reference to yyparse或yylex原因詞法語法分析器的生成文件沒參與鏈接或者生成順序不對。yacc.tab.c和lex.yy.c是工具產(chǎn)物如果 CMakeLists 里只 glob 了.cpp就會(huì)漏掉它們。解決在 CMake 里顯式把生成文件加入源列表或者用add_custom_command在構(gòu)建前重新生成。確認(rèn)flex/bison已安裝且.l/.y源文件存在。5.2 現(xiàn)象編譯通過運(yùn)行測試時(shí)Segmentation fault原因B 樹并發(fā)測試?yán)锛渔i順序錯(cuò)誤或者緩沖池 pin 計(jì)數(shù)不配對導(dǎo)致頁被提前淘汰。也可能是空指針解引用——教學(xué)代碼里指針管理不嚴(yán)格。解決用 gdb 跑gdb ./test/b_plus_tree_concurrent_testrun后bt看棧。重點(diǎn)檢查ix_index_handle.cpp的鎖獲取釋放路徑以及buffer_pool_manager_test.cpp里UnpinPage是否和FetchPage/NewPage成對。5.3 現(xiàn)象buffer_pool_manager_test斷言失敗提示淘汰頁不對原因LRU-K 的RecordAccess沒在命中時(shí)調(diào)用或者Evict選 victim 時(shí)沒排除被 pin 住的幀。解決在FetchPage命中分支補(bǔ)上RecordAccess在Evict里檢查pin_count_ 0才允許淘汰。參數(shù)上確認(rèn) K 值和測試預(yù)期一致。5.4 現(xiàn)象SQL 執(zhí)行報(bào)「table not found」但表確實(shí)建了原因數(shù)據(jù)庫切換或元數(shù)據(jù)沒持久化。CREATE TABLE寫進(jìn)了系統(tǒng)表但USE沒切換對或者元數(shù)據(jù)頁沒落盤。解決先SHOW TABLES確認(rèn)當(dāng)前庫檢查disk_manager.cpp的寫頁是否真的刷到文件。教學(xué)項(xiàng)目里元數(shù)據(jù)可能只在內(nèi)存重啟就丟這是設(shè)計(jì)邊界不是 bug。5.5 現(xiàn)象Windows 下編譯報(bào)fopen安全錯(cuò)誤原因MSVC 默認(rèn)把fopen標(biāo)為不安全要求用fopen_s。這份源碼按類 Unix 寫直接上 MSVC 會(huì)撞。解決要么加_CRT_SECURE_NO_WARNINGS宏要么換 WSL2/MSYS2 用 g。我一般直接上 WSL2省得和平臺差異糾纏。6. 進(jìn)階玩法給 RucBase 加一條自定義 SQL 函數(shù)跑通測試只是起點(diǎn)真正能驗(yàn)證你理解了鏈路的方式是加一條自己的 SQL 函數(shù)從詞法、語法、計(jì)劃到執(zhí)行全走一遍。我拿「求平方」舉例SELECT square(score) FROM student。第一步在詞法文件里加關(guān)鍵字或函數(shù)名識別。如果square當(dāng)普通標(biāo)識符處理就跳過這步在語法里當(dāng)函數(shù)調(diào)用解析。第二步在語法規(guī)則里加函數(shù)調(diào)用表達(dá)式。找到表達(dá)式相關(guān)的產(chǎn)生式加一條expr: ID ( expr )動(dòng)作里構(gòu)造函數(shù)調(diào)用節(jié)點(diǎn)。第三步在 planner 里把函數(shù)調(diào)用節(jié)點(diǎn)轉(zhuǎn)成計(jì)劃表達(dá)式。常見做法是加一個(gè)FunctionExpression執(zhí)行時(shí)根據(jù)函數(shù)名分發(fā)。// 函數(shù)表達(dá)式求值示意 Value FunctionExpression::Evaluate(const Tuple* tuple) const { // 先求參數(shù) Value arg child_-Evaluate(tuple); // 按函數(shù)名分發(fā) if (func_name_ square) { int v arg.GetAsInteger(); return Value(v * v); } throw std::runtime_error(unknown function: func_name_); }邏輯說明child_-Evaluate遞歸求參數(shù)func_name_決定行為。參數(shù)上注意類型檢查——square只接受整數(shù)傳字符串要報(bào)錯(cuò)而不是崩。加完后重新生成詞法語法文件、編譯、跑一條SELECT square(score) FROM student如果輸出是平方值說明整條鏈路你都打通了。驗(yàn)證方法上我習(xí)慣先跑原有測試確保沒改壞再加新測試覆蓋新函數(shù)。從那以后我每次改 RucBase 的解析或計(jì)劃層都強(qiáng)制先跑一遍buffer_pool_manager_test和b_plus_tree_concurrent_test確認(rèn)底層沒被波及再驗(yàn)證新功能。這個(gè)習(xí)慣幫我省過好幾次「改了上層崩了底層」的后悔藥。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取