MIT6.830 Lab 5: B+ Tree Index

6.830 Lab 5: B+ Tree Index

lab5主要是实现B+树索引，主要有查询、插入、删除等功能，查询主要根据B+树的特性去递归查找即可，插入要考虑节点的分裂（节点tuples满的时候），删除要考虑节点内元素的重新分配（当一个页面比较空，相邻页面比较满的时候），兄弟节点的合并（当相邻两个页面的元素都比较空的时候）
B+树的页面节点类型主要有四种：
1.根节点页面：一个B+树的根节点，在SimpleDB中实现为BTreeRootPtrPage.java;
2.内部节点页面：除去根节点和叶子节点外的节点，在SimpleDB中实现为BTreeInternalPage，每个BTreeInternalPage由一个一个的entry组成；
3.叶子节点页面：存储tuple的叶子节点，在SimpleDB中实现为BTreeLeafPage；
4.头部节点页面：用于记录整个B+树中的一个

MIT6.830 Lab 5: B+ Tree Index最先出现在Python成神之路。