记录数据库

Bustub项目结构（已完结）

发布于 • 作者: Ethan

引言

CMU 15445 数据库课程项目（Bustub）个人实现项目结构

课程整体结构（待持续确认）

course structure

项目整体结构

project structure

项目1：缓冲池管理器 Buffer Pool Manager

bpm

项目2：B+树 B+ Tree

项目2总览

overall

bpt

一、点查（READ_ONLY）

readonly

二、迭代扫描（Iterator ++）

iter

三、乐观插入（OPTIMISTIC_INSERT）与回退常规插入（REGULAR_INSERT）

optins

四、乐观删除（OPTIMISTIC_DELETE）与回退常规删除（REGULAR_DELETE）

optdel

访问整体策略

access

项目3：查询执行器

项目3总览

p3-struct

表达式

expression

Part 1：基础执行器/优化器

执行器：Update（Insert、Delete类似）

update

执行器：Sequential Scan

seq scan

执行器：Index Scan

index scan

优化器：顺序扫描优化至索引扫描

seqscan as indscan

Part 2: 聚合与连接执行器

聚合

agg class agg fsm

连接

嵌套循环连接

nlj class nlj fsm

嵌套索引连接

idx join class idx join fsm

Part 3: HashJoin 执行器和优化

中间结果存储页

int page

哈希连接

hash join class hash join fsm

NLJ至HashJoin优化

优化器识别 NLJ 并尝试重写为 Hash Join

nlj2hash

Part 4: 外部归并排序 + Limit 执行器 + 窗口函数

外部归并排序

ems class ems fsm

Limit执行器

limit class limit fsm

窗口函数执行器

wf class wf fsm

项目4：MVCC

Part 1：时间戳

时间戳管理相关类图

ts class

事务开始、提交、abort逻辑

begin seq commit seq abort seq

水位创建

wm create

Part 2：存储格式与顺序扫描

相关类图

sf class

顺序扫描MVCC版本

seq scan mvcc

收集Undolog逻辑

collect undologs

Part 3：MVCC执行器

MVCC执行器相关类图

mvcc exec class

MVCC插入、更新、删除执行器

mvcc insert

mvcc update delete

Stop the world GC

mvcc gc

MVCC abort逻辑

mvcc abort

Part 4：主键索引

MVCC索引核心类图

mvcc index class

主键索引插入（并发冲突 + TAINTED）

mvcc index insert

Insert 命中 Deleted Tuple

mvcc index insert to delete

Delete Executor（索引不删除）

mvcc index delete

Update Executor（非主键更新）

mvcc index update non-primary

主键更新（Delete + Insert）

mvcc index primary update

MVCC Index Scan

mvcc index scan

Serializable Commit（OCC Backward Validation

mvcc ser verify

结果

P1

bpm_result

P2

bpt result

QPS（无优化） bpt qps

P3

qexec result

P4

mvcc result

探索主题

阅读C++计算机架构k8s数据库分布式风格网络Go记录算法编译器编程范式统计操作系统MLAIRust设计