利用 Lab 1 中的页面管理实现基于 B+ 树的索引算法。

数据结构

B+树页面的 UML 如下：

classDiagram
	class BPlusTreeHeaderPage {
		page_id_t root_page_id_
	}
	class BPlusTreePage {
		page_type_t page_type_
		int size_
		int max_size_
	}
	class BPlusTreeInternalPage {
		k_v_pair_t array_[]
	}
	class BPlusTreeLeafPage {
		page_id_t next_page_id_
		k_v_pair_t array_[]
	}
	
	BPlusTreePage <|-- BPlusTreeInternalPage
	BPlusTreePage <|-- BPlusTreeLeafPage

每个页面的大小为 4 kB。BPlusTreePage 包含了索引页的属性信息，每个属性占用 4 字节，共计 12 字节，剩下的部分为存储键值对的空间。 BPlusTreeInternalPage 保存索引内部节点，因此键值对中的值类型为 page_id_t。BPlusLeafPage 中的值则是完整的行（对于聚集索引而言）。

通过 reinterpret_cast，我们可以将由 BufferPoolManager 中获得的页面数据转换为对应类型的页。

单点查找

对于 BPlusTreeInternalPage ，其中指针的数量比键少 1 个，我们规定 key[0] 为非法的，查询时通过二分查找找到待查询键值所在的子页面（page_id = value[i] where k[i-1] ≤ key < k[i]），并继续递归直到子页面。在查找前如果发现页面上数据较少（由SEARCH_THRESHOLD 指定），则使用循环来线性查找。

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::LookUp(const KeyType &key, const KeyComparator &comparator) const -> ValueType {
  auto current_size = GetSize();
  BUSTUB_ASSERT(current_size > 1, "internal page size should be greater than 1");
  // Linear search
  if (current_size < SEARCH_THRESHOLD) {
    for (auto i = 0; i < current_size - 1; i++) {
      if (comparator(key, KeyAt(i + 1)) < 0) {
        return ValueAt(i);
      }
    }
    return ValueAt(current_size - 1);
  }
  // Binary search
  int left = 0;
  int right = current_size;
  while (left + 1 < right) {
    auto mid = (left + right) / 2;
    auto compare_result = comparator(key, KeyAt(mid));
    if (compare_result == 0) {
      return ValueAt(mid);
    }
    if (compare_result < 0) {
      right = mid;
    } else {
      left = mid;
    }
  }
  return ValueAt(left);
}

到达叶子节点后，根据大小进行线性查找或调用 std::lower_bound 即可。

插入

插入的基本逻辑

叶子节点的插入十分简单，只需要根据键值找到对应的叶子节点后插入即可。如果此叶子节点已满，则新建一个页面并将另一半剪切到上面。注意维护叶子节点的 next_page_id_ 字段，同时向其父亲节点以首个数据主键为值，插入新增的页面的 id。

内部节点同理，遇到需要分裂的情况时，将新的页面上提，直到根节点。遇到根节点分裂时更新 BPlusTreeHeaderPage 中保存的根节点编号。

顺序插入优化

上面简单的插入方式会带来一个问题，在 bustub 的 B+ 树索引中，要求不能有重复的键，按照上面的顺序插入会导致空间利用率很低，例如当阶数取 3 时，依次插入 1-7 共 7 个键，得到下面的 B+ 树：

所有左侧的叶子节点均浪费了一半空间。因此我们需要引入“旋转”操作。一次旋转操作将待分裂节点的首个元素（或者末尾元素）移动到未满的左（或者右）兄弟节点上