首页

# Query

​ 查询部分较为简单，总体思路是：先获取头表 header_page，然后获取树根 root_page，再用树根不断变换成内结点，最后找到叶结点的相应位置。在每个结点内部只要写一个二分查找就行。

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Find(const InternalPage *page, const KeyType &key) -> int {
  int l = 0;
  int r = page->GetSize() - 1;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (comparator_(page->KeyAt(mid), key) != 1) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  if (r == -1 && comparator_(page->KeyAt(r), key) == 1) {
    r = 0;
  }

​ 上述是内结点二分的代码，和叶节点的二分有点区别，因为内结点第一个 key 是 invalid 的。大概结构的区别如下：

​ 贴一段教材中的单点查询流程：

​ 过程中只拿读锁，并且走到子结点就立即释放父结点的读锁。

# Insert

​ 插入新值较为麻烦，可能会有结点的分裂，需要递归向上层传递 key。按照步骤写就行，注意边界处理。写了分类内部结点、叶节点、乐观插入、悲观插入四个函数，其中分裂内部结点的代码如下：

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::SplitInternal(InternalPage *internal, const KeyType &key, page_id_t *new_id,
                                   page_id_t new_child_id) -> KeyType {
  //new_child_id 为下层分裂出的新结点 id, 即将 up_key 上传的页面
  bool put_left = false; // 放在左边还是右边
  int mid = internal->GetMaxSize() / 2;
  KeyType up_key = key;
  auto mid_key = internal->KeyAt(mid);
  // internal:  arr[0].key==invalid,val=first_child
  if (comparator_(mid_key, key) == -1) {
    up_key = comparator_(internal->KeyAt(mid + 1), key) == -1 ? internal->KeyAt(mid + 1) : key;
    mid++;
  } else {
    up_key = internal->KeyAt(mid);
    put_left = true;
  }
  page_id_t up_key_id = internal->ValueAt(mid);
  // 如果 up_key 不是从下层传上来的 key, 则该层删除 up_key
  if (comparator_(up_key, key) != 0) {
    for (int i = mid; i < internal->GetSize() - 1; i++) {
      internal->SetAt(i, internal->KeyAt(i + 1), internal->ValueAt(i + 1));
    }
    internal->IncreaseSize(-1);
  }
  auto new_internal_basic_guard = bpm_->NewPageGuarded(new_id);
  new_internal_basic_guard.SetDirty(true);
  new_internal_basic_guard.Drop();
  auto new_internal_guard = bpm_->FetchPageWrite(*new_id);
  auto new_internal = new_internal_guard.AsMut<InternalPage>();
  new_internal->Init(internal_max_size_);
  int internal_size = internal->GetSize();
  // 移动
  for (int i = mid, j = 1; i < internal_size; i++, j++) {
    new_internal->SetAt(j, internal->KeyAt(i), internal->ValueAt(i));
    new_internal->IncreaseSize(1);
    internal->IncreaseSize(-1);
  }
  // 实际 size 比孩子数量多 1, 因为第一个 key 为 invalid
  new_internal->IncreaseSize(1);
  if (comparator_(up_key, key) != 0) {
    // where to lay key
    auto put_in_internal = internal;
    if (!put_left) {
      put_in_internal = new_internal;
    }
    int idx = Find(put_in_internal, key);
    for (int i = put_in_internal->GetSize(); i > idx + 1; i--) {
      put_in_internal->SetAt(i, put_in_internal->KeyAt(i - 1), put_in_internal->ValueAt(i - 1));
    }
    put_in_internal->SetAt(idx + 1, key, new_child_id);
    // lay the key at right
    if (!put_left && put_in_internal->GetSize() == 0) {
      put_in_internal->SetSize(2);
    } else {
      put_in_internal->IncreaseSize(1);
    }
    // up_key!=key
    new_internal->SetAt(0, KeyType{}, up_key_id);
  } else {
    // up_key==key
    new_internal->SetAt(0, KeyType{}, new_child_id);
  }
  new_internal_guard.SetDirty(true);
  new_internal_guard.Drop();
  return up_key;// 向上传递插入的 key
}
​		附上一段 TEST2 的树结构，刚开始一直莫名其妙地没过。。。


​		


​		在插入时可以先乐观插入，一个结点获取下一个结点的读锁后就把父结点的读锁释放，到叶结点再拿写锁。如果中途发现结点要分类，则终止插入，进行悲观插入，向下找值的时候一路拿读锁（头页可以看根结点 kv 对数量直接判断会不会分裂，从而决定要不要先把锁放了），全部改完再将锁释放。


# Delete


删除是逻辑最繁琐的，涉及到结点合并，父结点和兄弟结点旋转等操作。


总体思路：


（1）从上至下找到要删除的值，记录走过的结点中的 key，找不到直接退出


（2）先将该值删除，判断是否小于 MinSize，若不小于则直接退出


（3）结点剩余 key 数量过少，若有左兄弟且左兄弟 key 数量大于 MinSize，先从左兄弟借一个，否则判断右兄弟从右兄弟借一个


（4）如果左右兄弟均不可借，若有左兄弟则将当前结点和左兄弟融合，否则和右兄弟融合


（5）若发生融合，父节点要对应变化，内结点可能合并，递归处理内结点：若当前结点和左兄弟融合，先将对应的父结点的走过的 key 下放到左兄弟末尾，然后将当前结点第一个值放到父结点刚下放的 key 处（可能为空），然后将当前结点剩余的所有值移动到左兄弟；若当前节点和右兄弟融合，先将对应的父结点走过的 key 的后一个下放到当前节点末尾，然后将右兄弟第一个结点放到父结点刚下放的 key 处，然后将右兄弟剩余的所有值移动到当前结点


贴一段融合内部结点和其左兄弟的代码：


// merge internal
		// merge into left
        if (parent_index > 0) {
          auto left_id = parent_internal->ValueAt(parent_index - 1);
          auto left_guard = bpm_->FetchPageWrite(left_id);
          auto left_internal = left_guard.template AsMut<InternalPage>();
          left_internal->SetAt(left_internal->GetSize(), parent_internal->KeyAt(parent_index),
                               cur_internal->ValueAt(0));
          left_internal->IncreaseSize(1);
          // move current to left internal sib
          for (int i = left_internal->GetSize(), j = 1; j < cur_internal->GetSize(); i++, j++) {
            left_internal->SetAt(i, cur_internal->KeyAt(j), cur_internal->ValueAt(j));
            left_internal->IncreaseSize(1);
          }
          // delete parent_index
          for (int i = parent_index; i < parent_internal->GetSize() - 1; i++) {
            parent_internal->SetAt(i, parent_internal->KeyAt(i + 1), parent_internal->ValueAt(i + 1));
          }
          parent_internal->IncreaseSize(-1);
		 // release lock
          cur_guard.SetDirty(false);
          cur_guard.Drop();
          left_guard.SetDirty(true);
          left_guard.Drop();
          cur_guard = std::move(parent_guard);
          cur_internal = parent_internal;
        } else {
        	//merge into right
        	//...
        }
# Iterator


较为简单，IndexIterator 类中添加的成员变量如下：




重载运算符只要沿着叶结点不断向右移动即可，判断一下边界。重载 == 和！= 注意不要自递归了…


# Concurrent Index


策略：


（1）查询时只获取读锁，使用后立即释放


（2）插入时先乐观插入，查找值只获取读锁，使用后立即释放，到叶结点再获取写锁，若发现结点分裂再悲观插入，一路获取写锁，中途判断某结点一定不会分裂则将其和其祖先的锁全都释放


（3）删除时先乐观删除，只获取读锁，使用后立即释放，到叶结点再获取写锁，若发现结点融合，再重新插入一遍，此时一直获取写锁，中途同样可以判断会不会融合释放一定数量的锁。


# Test


// 除了并发控制的测试都过了，一直提示有内存泄露问题


2023.9.14 update // 调试了一周了，并发还是过不了，不想改近 2000 行的 b + 树屎山代码了，换个 fall2022 版本重新写一遍吧，怀疑是 page_guard 没衔接好，但 page_guard 却能通过在线测试。。。


2023.9.16 update // 反复腾跳之后还是继续写 spring2023 吧，居然调通了，最后发现问题在 lru-k？？？但是它能过在线测试，明明只加了一把大锁这也能出并发问题？！






  


   


    

  
    
      
    
    更新于