Concurrency Control

在这个项目中，你将通过实现乐观多版本并发控制（MVOCC）来为BusTub添加事务支持。

Timestamps

Timestamp Allocation

当一个事务开始时，它将被分配一个读时间戳，这是最近提交的事务的提交时间戳。在事务提交时，它将被分配一个单调递增的提交时间戳。读时间戳确定事务可以读取哪些数据，而提交时间戳确定事务的序列化顺序。

Query Execution

在这次项目中，将实现允许 BusTub 执行查询的组件。具体是创建执行 SQL 查询的运算符执行程序，并实施优化器规则来转换查询计划。

BusTub的架构如下：

Buffer Pool

这个project是要在存储管理器中实现一个buffer pool，即缓冲池。缓冲池其实就是一块大的内存区域主内存，负责与磁盘之间来回移动物理页。它使得DBMS支持大于系统可用内存的数据库。缓冲池的操作对系统中的其他部分应该是透明的。例如，系统使用唯一标识符page_id_t想缓冲池请求页面的时候，系统不知道该页面是否位于已经在内存中，或者是需要从磁盘检索。

Extendible Hash Index

在此编程项目中，将使用可扩展哈希的变体作为哈希方案，在数据库系统中实现磁盘支持的哈希索引。

下图显示了一个可扩展哈希表，其中header页最大深度为 2，directory页最大深度为 2，存储bucket页最多包含两个条目。值被省略，并且键的哈希值显示在bucket页面中，而不是键本身。

Trie

trie 实现的是键值存储，字符串键可以映射到任何类型值。键的值存储在改键的最后一个字符的终端节点。例如将（“ab”， 1） 和 （“ac”， “val”） 插入到 trie 中。