CMU 15

编程入门 行业动态 更新时间:2024-10-27 05:36:23

<a href=https://www.elefans.com/category/jswz/34/1679980.html style=CMU 15"/>

CMU 15

0.写在前面

GitHub同步更新
Lab2的地址:/
本文主要总结一下在写Lab2遇到的几个问题,然后是Task的解决思路(不公开代码,如果有问题可以留言)。
对应lab2-check point 1.
Task #2.a - B+Tree Data Structure (Insertion & Point Search)

1.Task #1 - B+Tree Pages

  1. B+Tree Parent Page
  2. B+Tree Internal Page
  3. B+Tree Leaf Page

B+ tree pages一共分为2种,内部节点(Internal Page)和叶子节点(Leaf Page)。
Parent Page的这两个节点的父类,这么做的目的是内部节点和叶子结点在处理添加和删除操作还是有区别的(比如在插入算法中叶子结点需要维护双向链表,而内部节点不需要)。Parent Page中是内部节点和叶子结点共有的方法和属性(page_type,lsn,size,max_size,parent_page_id,page_id)。

Internal Page:内部页面不存储任何真实数据,而是存储有序的m个键条目和m+1个子指针(又名 page_id)。由于指针的个数不等于键的个数,所以第一个键被设置为无效,查找方法应该总是从第二个键开始。

Leaf Page:叶子页存储有序的m个键条目(key)和m个值条目(value)。 这里ValueType是由数据库决定的,比如recordId。

2.Task #2.a - B+Tree Data Structure (Insertion & Point Search)

这个任务是完成B+Tree的插入和点查询操作(暂时不需要考虑锁)。
B+Tree插入算法:
1.如果当前为空树,创建叶子结点,同时也是根节点。
2.否则寻找插入的的叶子结点

  • 2.1不分裂(少于m-1,直接插入)
  • 2.2分裂 split(产生一个1新的节点)

3.Task #2.b - B+Tree Data Structure (Deletion)

这个任务是完成B+Tree的删除操作(暂时不需要考虑锁)。
B+Tree删除算法:

4.Task #4 - Concurrent Index

Lock和latch的区别:

对于b+ tree中latch的考虑:
Search:从根页面开始,抓住子页面上的读取(R)latch,然后在您登陆子页面后立即释放父页面上的latch。
Insert:从根页面开始,抓住子页面的写(W)锁存器。一旦孩子被锁定,检查它是否安全,如果孩子是安全的(node_size< max-1),则释放祖先的所有锁。
Delete:从根页面开始,抓住子页面的写(W)锁存器。一旦孩子被锁定,检查它是否安全,在这种情况下,至少半满。(注意:对于根页面,我们需要用不同的标准检查)如果孩子是安全的,释放所有祖先的锁。

5.Debug

cd build
make b_plus_tree_print_test
./test/b_plus_tree_print_test

可以利用print_test来查看b+tree的情况,在Debug上帮助非常明显,一开始在B+tree的插入操作的时候一直遇到Segment Fault.找了半天的错误,发现在按顺序插入<1,2,3,4,5>的时候会发生这种情况。

在Split的时候要考虑清楚究竟哪个节点Increase。

Lab2终于做完啦!Lab3冲冲冲!

参考:.html
.html
.html

更多推荐

CMU 15

本文发布于:2024-03-09 13:33:38,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1725104.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:CMU

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!