CMU15445 B+Tree

发布时间 2023-07-19 16:06:29作者: shinidetiehanhan

首先,上一个 task buffer pool 和这里的 b+tree 具体实现肯定不一样,关于具体的存储的层次也不一样;

在 buffer pool 里,数据以 page 为单位,在 b+tree 中,每个索引结点而言,存储了很多的 key-value,每个 value 对应一个子节点(子节点是用 page_id 来标识),需要从 key 找对应的 page_id,这里 page_id 就对应的是下一个子节点所对应的 page。

插入

空树是一种特殊情况,树中只有一个叶子结点时也是特殊情况,直到这个唯一的叶子结点分裂,导致索引节点的产生,这时候情况才比较 general。

ref

  1. https://cloud.tencent.com/developer/article/1461421