CMU15445Lab2BPlusTree

整体结构

image-20230823152942660

父页面的内部结构

  • 内部结构固定24B

内部页面（索引页面）

除了有header，还有data字段

数据存储在KV键值对上，这里要小于4K大小

image-20230823153332361

value都是指针 指向另一个页面

b+树的叶子页面

  • 相比于非叶子页面，页面头多了一个字段NextPageId b+树的特点

树查找 getValue

核心流程

  • 从根节点开始查找
    • 内部节点中：使用二分查找，找到大于等于key的value指针PageId，通过PageId获取到新的节点，如果是内部节点则继续这个步骤，如果是叶子节点则执行对应的查找规则。
    • 叶子节点中：使用二分查找，找到恰好等于key的value获取RID

节点分为 internal page 和 leaf page，每个 page 上的 key 有序排列。当拿到一个 key 需要查找对应的 value 时，首先需要经由 internal page 递归地向下查找，最终找到 key 所在的 leaf page。这个过程可以简化为一个函数 Findleaf()。

  • Findleaf() 从 root page 开始查找。在查找到 leaf page 时直接返回，否则根据 key 在当前 internal page 中找到对应的 child page id，递归调用 Findleaf。根据 key 查找对应 child id 时，由于 key 是有序的，可以直接进行二分搜索。15-445 Lecture 中也介绍了一些其他的方法，比如用 SIMD 并行比较，插值法等等。在这里二分搜索就可以了。

internal page 中储存 key 和 child page id，那么在拿到 page id 后如何获得对应的 page 指针？用 Project 1 中实现的 buffer pool。

1
Page *page = buffer_pool_manager_->FetchPage(page_id);

  • 找到 leaf page 后，同样是二分查找 key，找到对应的 record id。

  • 要注意unpin操作

    我们在拿到 page id 后，调用 buffer pool 的 FetchPage() 函数来获取对应的 page 指针。要注意的是，在使用完 page 之后，需要将 page unpin 掉，否则最终会导致 buffer pool 中的所有 page 都被 pin 住，无法从 disk 读取其他的 page。

树插入

主要流程

  • 目标：插入key和value到B+树上
  • 整体步骤
    • 从根节点开始
      • 如果是空树，新建一个根节点，直接插入到根节点。
      • 如果不是空树，根据查询的流程找到key对应的叶子页面。
        • 如果叶子，没有满（size < n - 1）则直接插入，结束。
        • 如果叶子，满了。
          • 将原来的数据和新插入的数据，平均分成两份，新建一个页面存放另一半数据。
          • 将另一半中最小的key标记为K’，将这个K’插入到父节点中。
  • 插入父节点步骤
    • 如果分裂的节点L是根节点，则创建一个新根，且只有1个key，就是传入的K’
    • 如果分裂的节点L是普通节点，则插入K’和对应的PageId到当前节点中。
      • 插入后内部节点容量没满：
        • 结束。
      • 插入后内部节点容量满了：
        • 分裂成两个页面，新页面的最小值K’’插入到父节点，递归执行。

说的比较简单，反正可以去网上看一下怎么搞

树删除

流程图

image-20230824144546732

主要步骤

  1. 根据查找流程找到key对应的叶子页面。
  2. 从这个叶子页面删除对应的Key和Value。
  3. 如果删除的节点是根且只有一个孩子，则让它的孩子变成新的根，删除自身。
  4. 如果删除后页面中KV数量太少，则需要合并或者重分配。
    1. 直接合并。如果相邻节点能放得下两个节点的数据，则直接放。
      1. 需要区分叶子和非叶子
        1. 删除自身节点。
        2. 删除父节点指向自身的指针。
    2. 重分配。如果放不下，则进行数据重分配。从左邻居的末尾获取一个元素放到自身的头部。
      1. 如果是叶子：直接放。更新父节点。
      2. 如果是非叶子。把父节点降下来再放。更新父节点。

索引迭代器

目的

为了高效地检索所有的叶子页，基本思路是组织成一个单链表

思路

  • 指定迭代器起点，通过自增移动当前的下标，依次获取对应的结果，每次返回的是一个KV键值对

  • 操作对象 叶子页面page，当前下标index，缓冲池bpm_

    • index为page页内偏移
    • 叶子页面有一个指向右兄弟的指针，存储的是Pageid，要取pageId对应的叶子页面需要用到缓冲池

注意点

  • 自增可能会移动到右兄弟的页面
  • 移动到新页面后，index_从零开始
  • 注意加锁解锁

并发索引

实现思路

  • 查找
    • 只需要加读锁
    • 从根往叶子加读锁
    • 先获取到孩子节点的锁，再释放自身的锁。
  • 插入/删除
    • 悲观锁思想：认为会有冲突，所以事先加写锁。
    • 从根往叶子加写锁
    • 确保当前位置安全再释放，安全的意思是子树即使发生分裂或者合并依然不会对上层造成影响，就释放该及其祖先节点的锁。
    • 插入/删除完成后，释放剩余的写锁。
  • 插入对于安全的定义：
    • 当前节点没满
  • 删除对于安全定义：
    • 根：删除后，根还有至少一个有效的KV
    • 非根：删除后不会引起跟其他节点合并，这个节点要超过半满的状态