skyitachi's blogBTree Leaf Node分裂问题 2020-12-19

BTree Leaf Node分裂问题记录

这两天在做BTree的实现的时候被一个问题困住了，就是BPlusTreeInternalPage的分裂问题

cmu15445中，BPlusTreeInternalPage 只提供了一个MoveHalfTo的操作，这在我看来是不够用的

  • 先看下bustub的api
1
2
3
4
5
6
7
void MoveAllTo(BPlusTreeInternalPage *recipient, const KeyType &middle_key, BufferPoolManager *buffer_pool_manager);
void MoveHalfTo(BPlusTreeInternalPage *recipient, BufferPoolManager *buffer_pool_manager);
void MoveFirstToEndOf(BPlusTreeInternalPage *recipient, const KeyType &middle_key,
                        BufferPoolManager *buffer_pool_manager);
void MoveLastToFrontOf(BPlusTreeInternalPage *recipient, const KeyType &middle_key,
                         BufferPoolManager *buffer_pool_manager);

  • 而我在yedis中写的btree 中internalnode会把midkey提到parent上以保持btree的特性
1
BTreeNodePage* index_split(BufferPoolManager*, BTreeNodePage* parent, int child_idx);

解释下两种api的作用

  1. bustub 分裂之后

image-20201219221942147

bustub中第一个key都是无效的，所以能保证ki > (k in pi)

这种分裂乍看起来第二页多了一个key，后续在这个page上insert,让我感觉有点不对劲，事实上只要忽略第一个key就好了，本例子中直接忽略k2

  1. yedis的分裂

    image-20201219222511014

我会主动把mid-key剔除出去（要插入到parent中），这样看起来就干净有点了，事实上两者没什么区别。

这只是一个思维上的转变，bustub的抽象更好些，yedis中的操作api都是太零散了，继续加油

▲