Lab 1 页面组织与缓存管理

基础功能

寻找记录插入的页面

寻找页面见 src/table/table.cpp 中的 Table::InsertRecord().

同时记录当前页面的 page_id 与前一页的 prev_page_id, 并遍历表的页面, 如果页面有足够的空间, 通过 BufferPool::GetPage() 获取页面, 并且调用成员函数TablePage::InsertRecord() 插入记录, 返回 rid; 如果没有足够空间, 则通过 BufferPool::NewPage() 创建新页面, 插入记录并返回 rid.

页面内部记录管理

插入记录见 src/table/table_page.cpp - TablePage::InsertRecord().

插入记录时先维护 lower 和 upper 指针, 根据当前页面存储的记录数设置 slots 数组. 通过 Record::SerializeTo() 将 record 写入 page_data_, 并将页面标记为 dirty.

删除记录见 src/table/table_page.cpp - TablePage::DeleteRecord().

使用 Record::DeserializeHeaderFrom() 函数读取记录头, 将 slot_id 对应的 record 标记为删除, 最后使用 Record::SerializeHeaderTo() 将记录头写回 page_data_, 并将页面标记为 dirty.

记录读取策略

读取记录见 src/table/table_scan.cpp - TableScan::GetNextRecord().

While 循环中遍历所有 page 的所有 slot, 并通过 BufferPool::GetPage() 获取相应页面, 通过 TablePage::GetRecord() 读取一条记录. 记录不附带删除标记则直接返回, 否则通过 continue 跳过该次循环.
TablePage::GetRecord() 通过 Record::DeserializeFrom() 读取记录数据, 同时需要通过 record->SetRid(rid) 设置记录对应的 rid.

LRU 缓存替换算法实现

缓存替换算法见 src/storage/lru_buffer_strategy.cpp.

为 LRUBufferStrategy 新增成员变量 std::list<*size_t*> lru_list_. LRUBufferStrategy::Access() 用于更新页面访问记录, 将访问的页面移到链表头部; LRUBufferStrategy::Evict() 在缓存不足时选择最近最少使用的页面, 默认为链表尾部的页面.

高级功能

垃圾回收

设计思路

DatabaseEngine::Vacuum() 对指定的 Table 调用 Table::VacuumRecord(), 其遍历页面, 对每个页面调用 TablePage::VacuumRecord().

TablePage::VacuumRecord() 创建新页面 shared_ptr<TablePage>, 遍历原页面的所有 record, 将未被标记为删除的 record 插入新页面, 最后拷贝新页面的信息到原页面, 实现单页内的垃圾回收.

效果: 将原页面中有效的记录迁移到新页面, page_data_ 不再包含死数据, 可用空间扩大.

新增代码描述

函数 src/database/database_engine.cpp - DatabaseEngine::Vacuum():

判断对所有表还是对特定的表执行 vacuum 操作, 调用 Table 对象的 VacuumRecord() 方法.

函数 src/table/table.cpp - Table::VacuumRecord():

遍历页面, 对每个页面调用 TablePage 对象的 VacuumRecord() 方法.

函数 src/table/table_page.cpp - TablePage::VacuumRecord():

创建新页面 new_page, 使用 Init() 方法初始化, 反序列化遍历原页面中的所有记录, 将所有未删除的记录插入新页面中, 最后将新页面信息拷贝到原页面中, 并输出 vacuum 操作前后的页面信息.

效果展示

测试用例位于 test/lab1/60-vacuum.test, 在单页面内插入 6 条记录, 并删除 3 条记录, 使用 vacuum test_vacuum 回收死数据, 输出 vacuum 前后的页面信息.

> make debug && make lab1/60

空闲空间管理

设计思路

将页面空闲空间组织为满二叉树, 使用 Table::bool pages_[TABLE_PAGE_SIZE] 记录页面是否被创建, 使用 Table::FreeSpaceTree fsm_tree_ 记录页面空闲空间.

FreeSpaceTree 的叶子节点记录每个页面的空闲空间大小, 内部节点记录其子节点的最大值, 这样根节点就表示所有页面中的最大空闲空间.

insert 记录时, 从 FreeSpaceTree 根节点开始二分查找空闲空间足够的叶子节点, 插入记录后从该叶子节点向上依次更新其所有父节点的空闲空间大小; 对表格进行 vacuum 操作后, 将 FreeSpaceTree 的所有叶子节点更新为对应的空闲空间, 并重新建树, 逐层更新内部节点.

效果: 插入记录后无需使用原链表遍历的方式寻找页面, 可以使用树结构收获二分查找的效率.

新增代码描述

常量 src/common/constants.h:

新增 FSMTree 的最大节点数, 表格最大页面数 (为测试效率设为 1 << 3, 生产中可根据需要进行页面数设置).
```
static constexpr size_t FS_TREE_SIZE = (1 << 3) - 1;
static constexpr size_t TB_PAGE_SIZE = (FS_TREE_SIZE + 1) / 2;
```

类 src/table/free_space_tree.h - class FreeSpaceNode: