CMU15-445 lab02(Part 2)

B+TREE LEAF PAGE

Leaf Page存储一个有序的m键条目和m值条目。在你的实现中，值应该仅为64位的record_id，用于定位实际元组存储的位置，参见在src/include/common/RID.h下定义的RID类。叶子页与内部页在键/值对的数量上有相同的限制，并且应该遵循相同的合并、重分发和拆分操作。

必须在指定文件中实现内页。只允许修改头文件(src/include/storage/page/b_plus_tree_leaf_page.h)及其对应的源文件。

要点:即使叶子页和内部页包含相同类型的键，它们也可能有不同类型的值，因此叶子页和内部页的max_size可能不同。

类基本函数

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Init(page_id_t page_id, page_id_t parent_id, int max_size) {
  SetPageType(IndexPageType::LEAF_PAGE);
  SetPageId(page_id);
  SetParentPageId(parent_id);
  SetSize(0);
  SetMaxSize(max_size);
  SetNextPageId(INVALID_PAGE_ID);
}
/**
 * Helper methods to set/get next page id
 */
INDEX_TEMPLATE_ARGUMENTS
page_id_t B_PLUS_TREE_LEAF_PAGE_TYPE::GetNextPageId() const { return next_page_id_; }

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::SetNextPageId(page_id_t next_page_id) { next_page_id_ = next_page_id; }

KeyIndex()函数

• 查找leaf page的array中第一个>=key的下标。
• 这里用y总的整数二分模板（左边界），且要注意key比array中所有key都要小的情况。

INDEX_TEMPLATE_ARGUMENTS
int B_PLUS_TREE_LEAF_PAGE_TYPE::KeyIndex(const KeyType &key, const KeyComparator &comparator) const {
  int l = 0;
  int r = GetSize() - 1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (comparator(KeyAt(mid), key) >= 0) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  if (comparator(KeyAt(l), key) < 0) {
    return GetSize();
  }
  return l;
}

Set and Get

INDEX_TEMPLATE_ARGUMENTS
KeyType B_PLUS_TREE_LEAF_PAGE_TYPE::KeyAt(int index) const {
  // replace with your own code
  return array[index].first;
}

/*
 * Helper method to find and return the key & value pair associated with input
 * "index"(a.k.a array offset)
 */
INDEX_TEMPLATE_ARGUMENTS
const MappingType &B_PLUS_TREE_LEAF_PAGE_TYPE::GetItem(int index) {
  // replace with your own code
  return array[index];
}

Insert函数

• 先查找第一个>=key的的下标。
• 判断是否重复。
• 不重复则数组下标>=insert_index的元素整体后移1位。
• [insert_index, size - 1] –> [insert_index + 1, size]
• 最后进行插入操作。

INDEX_TEMPLATE_ARGUMENTS
int B_PLUS_TREE_LEAF_PAGE_TYPE::Insert(const KeyType &key, const ValueType &value, const KeyComparator &comparator) {
  int insert_index = KeyIndex(key, comparator);

  if (comparator(KeyAt(insert_index), key) == 0) {
    return GetSize();
  }

  for (int i = GetSize(); i > insert_index; i--) {
    array[i] = array[i - 1];
  }
  array[insert_index] = MappingType{key, value};

  IncreaseSize(1);
  return GetSize();
}

MoveHalfTo函数

• MoveHalfTo()将this page的从array+start_index开始的move_num个元素复制到recipient page的array尾部。
• CopyNFrom()[items,items+size)复制到该page的array最后一个之后的空间。
• 注意叶子结点的操作较为简单，无需更新子节点的父指针。

/*
 * Remove half of key & value pairs from this page to "recipient" page
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::MoveHalfTo(BPlusTreeLeafPage *recipient) {
  int start_index = GetMinSize();
  int move_num = GetSize() - start_index;
  recipient->CopyNFrom(array + start_index, move_num);
  IncreaseSize(-move_num);
}

/*
 * Copy starting from items, and copy {size} number of elements into me.
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::CopyNFrom(MappingType *items, int size) {
  std::copy(items, items + size, array + GetSize());
  IncreaseSize(size);
}

Lookup函数

• 得到leaf page中key对应的value（传出参数），返回key是否在leaf page中存在。
• 首先用KeyIndex()查找第一个>=key的的下标。
• 若=key的下标不存在（只有>key的下标），返回false。

INDEX_TEMPLATE_ARGUMENTS
bool B_PLUS_TREE_LEAF_PAGE_TYPE::Lookup(const KeyType &key, ValueType *value, const KeyComparator &comparator) const {
  int target_index = KeyIndex(key, comparator);                                  // 查找第一个>=key的的下标
  if (target_index == GetSize() || comparator(key, KeyAt(target_index)) != 0) {  // =key的下标不存在（只有>key的下标）
    return false;
  }
  *value = array[target_index].second;
  return true;

RemoveAndDeleteRecord函数

• 首先用KeyIndex()查找第一个>=key的的下标。
• 若=key的下标不存在（只有>key的下标），返回Getsize()。
• 将target_index后的子数组往前移动一位，覆盖当前值。

INDEX_TEMPLATE_ARGUMENTS
int B_PLUS_TREE_LEAF_PAGE_TYPE::RemoveAndDeleteRecord(const KeyType &key, const KeyComparator &comparator) {
  int target_index = KeyIndex(key, comparator);                                  // 查找第一个>=key的的下标
  if (target_index == GetSize() || comparator(key, KeyAt(target_index)) != 0) {  // =key的下标不存在（只有>key的下标）
    return GetSize();
  }
  IncreaseSize(-1);
  for (int i = target_index; i < GetSize(); i++) {
    array[i] = array[i + 1];
  }
  return GetSize();
}

其他函数操作

• 内部节点的思路大同小异，就不过多赘述了（注意叶子节点无需更新子节点的父指针）。

/*****************************************************************************
 * MERGE
 *****************************************************************************/
/*
 * Remove all of key & value pairs from this page to "recipient" page. Don't forget
 * to update the next_page id in the sibling page
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::MoveAllTo(BPlusTreeLeafPage *recipient) {
  recipient->CopyNFrom(array, GetSize());
  SetSize(0);
}

/*****************************************************************************
 * REDISTRIBUTE
 *****************************************************************************/
/*
 * Remove the first key & value pair from this page to "recipient" page.
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::MoveFirstToEndOf(BPlusTreeLeafPage *recipient) {
  recipient->CopyLastFrom(array[0]);
  IncreaseSize(-1);
  for (int i = 0; i < GetSize(); i++) {
    array[i] = array[i + 1];
  }
}

/*
 * Copy the item into the end of my item list. (Append item to my array)
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::CopyLastFrom(const MappingType &item) {
  array[GetSize()] = item;
  IncreaseSize(1);
}

/*
 * Remove the last key & value pair from this page to "recipient" page.
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::MoveLastToFrontOf(BPlusTreeLeafPage *recipient) {
  recipient->CopyFirstFrom(array[GetSize() - 1]);
  IncreaseSize(-1);
}

/*
 * Insert item at the front of my items. Move items accordingly.
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::CopyFirstFrom(const MappingType &item) {
  for (int i = GetSize(); i >= 0; i--) {
    array[i + 1] = array[i];
  }
  array[0] = item;
  IncreaseSize(1);
}