CMU 15-445 Project 2: B+tree

实现一个并发安全的B+树

本次 project 中,我们需要为 DBMS 实现索引。索引负责快速检索数据,而无需搜索数据库表中的每一行,为快速随机查找和高效访问有序记录提供了基础。

索引使用B+树动态索引结构。B+树是一种平衡树,分为内部页面(B+Tree Internal Page)和叶页面(B+Tree Leaf Page),其中内部页面不储存实际数据,只为为搜索数据提供路由,叶页面包含实际的数据条目。由于树结构是动态增长和收缩的,因此需要处理拆分和合并的逻辑。这里需要区分B+树的页面与缓冲池中管理的页面,前者包含于后者,前者(B+Tree Page)是后者(Page)数据结构中的 data_ 域,在编写代码时通常这么处理二者之间的关系。

    Page *page = buffer_pool_manager_->FetchPage(page_id);
    BPlusTreePage *node = reinterpret_cast<BPlusTreePage *>(page->GetData());
Built with Hugo
Theme Stack designed by Jimmy