CMU15445 Lab 2 B+TREE

2020fall lab2

时间

2022.02.026 - 2022.03.01

实验说明

• B+ Tree内部节点指引搜索，叶子节点能够指向实际的数据entry

• B+ Tree的正确性依赖与Buffer Pool的实现

• CHECKPOINT #1

  • TASK #1 - B+TREE PAGES：需要实现三个B+ Tree的Page class：
    • B+ Tree Parent Page：不论是internal page 还是 leaf page，它们都继承于parent class，也就是它是个大父类，它只保留子类们所共有的信息：
    • B+Tree Internal Page：，internal page不存真实数据，(对于m-way迭的B+ Tree)但是它会存储m个key与m + 1个孩子指针(在这里是page_id)， 对于这句话的解释是？，假设一个internal node中有三个child pointer，那么这时需要三个key，但是会有一个key是无效的，比如这里(猜测child pointer 与 key应该是存成了一个pair)
    • B+Tree Leaf Page：一个Leaf Page有m个key与m个value entries，使用RID class来存储value entry，(这里存的是rid，那么lab2中的B+Tree是非聚簇索引)，每个leaf/internal page对应与Buffer Pool中的Page(也就是Frane)对象中的data_成员变量不过Sibling Pointers存在哪里？
  • TASK #2.A - B+TREE DATA STRUCTURE (INSERTION & POINT SEARCH)：lab2中的B+ Tree并不存在重复的key，如果要插入重复的key，不执行并且返回false这句话啥意思？,每次插入，如果导致了root_node分裂，那么需要用一个新的page去存储新的root_node,那么root_page_id也就会改变

• CHECKPOINT #2

  • TASK #2.B - B+TREE DATA STRUCTURE (DELETION)
  • TASK #3 - INDEX ITERATOR
    • 把leaf pages组织成linked list，并从单一方向遍历它们
    • iterator需要实现
  • TASK #4 - CONCURRENT INDEX
    • 将使用latch crabbing实现并发
    • 需要实现的是未优化的latch crabbing，也就是不需要使用到悲观锁与乐观锁

实验要求与提示

• 不能够像之前lab一样只是简单的，在每个操作的开始加锁，每个操作结束解锁，需要正确的实现latch crabbing
• 释放read-write latch的函数已经实现
• 对于trasaction的处理？FindLeafPage函数原来没有返回值，所以需要添加？
• latch是加在Page上的

陷阱(!!!)

• 这个lab不需要实现leaf node scan，对于一个leaf page不能够从sibling获取一个latch时，需要抛出std::exception
• 必须的先释放latch,在unpin一个页
• 必须要实现top to down地获取锁
• 这个root_page_id到底是啥？

实现

TASK #1 - B+TREE PAGES

B+Tree Parent Page

测试

遇到的问题