Bustub中表的设计

Bustub中的Table

首先，我们先来看一下Bustub数据库中表的设计的结构图：

首先，Bustub 有一个 Catalog。Catalog 提供了一系列 API，例如 CreateTable()、GetTable() 等等。Catalog 维护了几张 hashmap，保存了 table id 和 table name 到 table info 的映射关系。table id 由 Catalog 在新建 table 时自动分配，table name 则由用户指定。

这里的 table info 包含了一张 table 的 metadata，有 schema、name、id 和指向 table heap 的指针。系统的其他部分想要访问一张 table 时，先使用 name 或 id 从 Catalog 得到 table info，再访问 table info 中的 table heap。

table heap 是管理 table 数据的结构，包含 InsertTuple()、MarkDelete() 一系列 table 相关操作。table heap 本身并不直接存储 tuple 数据，tuple 数据都存放在 table page 中。table heap 可能由多个 table page 组成，仅保存其第一个 table page 的 page id。需要访问某个 table page 时，通过 page id 经由 buffer pool 访问。

table page 是实际存储 table 数据的结构，父类是 page。相较于 page，table page 多了一些新的方法。table page 在 data 的开头存放了 next page id、prev page id 等信息，将多个 table page 连成一个双向链表，便于整张 table 的遍历操作。当需要新增 tuple 时，table heap 会找到当前属于自己的最后一张 table page，尝试插入，若最后一张 table page 已满，则新建一张 table page 插入 tuple。table page 低地址存放 header，tuple 从高地址也就是 table page 尾部开始插入。

tuple 对应数据表中的一行数据。每个 tuple 都由 RID 唯一标识。RID 由 page id + slot num 构成。tuple 由 value 组成，value 的个数和类型由 table info 中的 schema 指定。

value 则是某个字段具体的值，value 本身还保存了类型信息。

Tuple

上面给出了一条Tuple 的结构，如果我们想解析一条Tuple ，例如知道Tuple 的每一个Value ，包括类型，我们就需要另外一个叫做Schema 的类了。所以说Tuple 需要和Schema 配合使用。

Schema 定义好了一个表的表模式，即一个table由哪些列组成的，列的名称，占用的大小等。Tuple 中有一些列是由Varchar组成的字符串，由于这些字符串长度的不确定，我们又该如何在Tuple中进行存储呢？

我们可以先计算Schema中固定的长度，也就是比如一些int、bool等类型的column，这些存储的位置都可以固定下来，并且可以用这些加起来得到schema的长度，而对于变长的字符串，我们留一个offset ，再在整个shema 固定部分的长度后面加进去。这也就是Column 中函数IsInlined()的作用，就是判断data_的 column->GetOffset()处 存储的是真实的Value，还是二级的offset。这样就解决了Varchar的可边长问题：

我们再来看一下Tuple 的结构，data_ 字符数组就是这样组织的，主要还是看代码

Tuple除了data_来存储各个column外，还有

bool allocated_{false};  // is allocated?
RID rid_{};              // if pointing to the table heap, the rid is valid
uint32_t size_{0};

这三个成员。

TablePage

bustub中存储table表的页叫做TablePage ，它的结构如下：

/**
 * Slotted page format:
 *  ---------------------------------------------------------
 *  | HEADER | ... FREE SPACE ... | ... INSERTED TUPLES ... |
 *  ---------------------------------------------------------
 *                                ^
 *                                free space pointer
 *
 *  Header format (size in bytes):
 *  ----------------------------------------------------------------------------
 *  | PageId (4)| LSN (4)| PrevPageId (4)| NextPageId (4)| FreeSpacePointer(4) |
 *  ----------------------------------------------------------------------------
 *  ----------------------------------------------------------------
 *  | TupleCount (4) | Tuple_1 offset (4) | Tuple_1 size (4) | ... |
 *  ----------------------------------------------------------------
 */

下面就是TablePage的结构，前面有24个字节的头部，分别存储了Page的基本信息以及FreeSpacePointer和TupleCount，通过这两个就可以实现对TablePage的解析。每一个offset就是Page中Tuple的data_在页的起始位置的偏移，至于RID就是offset size数组的下标。

在Bustub中是如何删除某一条Tuple的呢，首先先对Tuple进行删除的标记，也就是调用MarkDelete函数。

事务首先调用MarkDelete，然后如果提交成功，使用ApplyDelete函数从物理上删除。如果事务异常终止了则调用RollbackDelete函数再把每个tuple的size的第32位1给抹去。

auto TableHeap::MarkDelete(const RID &rid, Transaction *txn)

这个函数做一些判断后调用SetTupleSize。这个标志就相当于把tuple_size的第32位置1，根据这一位判断是否是需要被Delete的。同样UnsetDeletedFlag函数就是获取设为Delete标志位前tuple的长度。

SetTupleSize(slot_num, SetDeletedFlag(tuple_size));

// DELETE_MASK  (0b)  100000.....000(31个0)
static constexpr uint64_t DELETE_MASK = (1U << (8 * sizeof(uint32_t) - 1));
static auto SetDeletedFlag(uint32_t tuple_size) -> uint32_t {
    return static_cast<uint32_t>(tuple_size | DELETE_MASK);
}
static auto UnsetDeletedFlag(uint32_t tuple_size) -> uint32_t {
    return static_cast<uint32_t>(tuple_size & (~DELETE_MASK));
}

ApplyDelete

接下来我们可以直接看ApplyDelete函数，这个函数是把tuple的内容从TablePage中进行物理删除。

这个函数的行为是把rid这个tuple给删除了，首先利用UnsetDeletedFlag函数得到原来的tuple_size，然后把使用memmove函数直接把需要删除的tuple给覆盖掉。然后再把移动了的tuple(offset小于被删除tuple的offset)的偏移加上删除tuple的tuple_size。还需要把相应位置的offset和size都置为0。

void TablePage::ApplyDelete(const RID &rid, Transaction *txn, LogManager *log_manager) {
  uint32_t slot_num = rid.GetSlotNum();
  BUSTUB_ASSERT(slot_num < GetTupleCount(), "Cannot have more slots than tuples.");

  uint32_t tuple_offset = GetTupleOffsetAtSlot(slot_num);
  uint32_t tuple_size = GetTupleSize(slot_num);
  // Check if this is a delete operation, i.e. commit a delete.
  if (IsDeleted(tuple_size)) {
    tuple_size = UnsetDeletedFlag(tuple_size);
  }
    
  // Otherwise we are rolling back an insert.
  uint32_t free_space_pointer = GetFreeSpacePointer();
  BUSTUB_ASSERT(tuple_offset >= free_space_pointer, "Free space appears before tuples.");

  memmove(GetData() + free_space_pointer + tuple_size, GetData() + free_space_pointer,
          tuple_offset - free_space_pointer);
  SetFreeSpacePointer(free_space_pointer + tuple_size);
  SetTupleSize(slot_num, 0);
  SetTupleOffsetAtSlot(slot_num, 0);

  // Update all tuple offsets.
  for (uint32_t i = 0; i < GetTupleCount(); ++i) {
    uint32_t tuple_offset_i = GetTupleOffsetAtSlot(i);
    if (GetTupleSize(i) != 0 && tuple_offset_i < tuple_offset) {
      SetTupleOffsetAtSlot(i, tuple_offset_i + tuple_size);
    }
  }
}

InsertTuple

InsertTuple函数负责把tuple中的data_部分插入到TablePage中，再把插入的位置记录在指针rid中。

首先判断是否插入得下，如果没有足够的空间插入就返回false。

然后开始遍历所有的tuple(从0到TupleCount()，这里的i就是RID中的slot_num)，。如果某个tuple的size为0，说明这个位置是空闲的(之前ApplyDelete的时候offset和size数组在page中的的位置并没有改变，删除了只是把它们都置为0。

然后我们把FreeSpacePointer减去tuple.size_，并把tuple.data_搬运到这个位置上，最后设置rid，rid->Set(GetTablePageId(), i)。

auto TablePage::InsertTuple(const Tuple &tuple, RID *rid, Transaction *txn, LockManager *lock_manager,
                            LogManager *log_manager) -> bool {
  BUSTUB_ASSERT(tuple.size_ > 0, "Cannot have empty tuples.");
  // If there is not enough space, then return false.
  if (GetFreeSpaceRemaining() < tuple.size_ + SIZE_TUPLE) {
    return false;
  }

  // Try to find a free slot to reuse.
  uint32_t i;
  for (i = 0; i < GetTupleCount(); i++) {
    // If the slot is empty, i.e. its tuple has size 0,
    if (GetTupleSize(i) == 0) {
      // Then we break out of the loop at index i.
      break;
    }
  }

  // If there was no free slot left, and we cannot claim it from the free space, then we give up.
  if (i == GetTupleCount() && GetFreeSpaceRemaining() < tuple.size_ + SIZE_TUPLE) {
    return false;
  }

  // Otherwise we claim available free space..
  SetFreeSpacePointer(GetFreeSpacePointer() - tuple.size_);
  memcpy(GetData() + GetFreeSpacePointer(), tuple.data_, tuple.size_);

  // Set the tuple.
  SetTupleOffsetAtSlot(i, GetFreeSpacePointer());
  SetTupleSize(i, tuple.size_);

  rid->Set(GetTablePageId(), i);
  if (i == GetTupleCount()) {
    SetTupleCount(GetTupleCount() + 1);
  }

  return true;
}