B+ Tree

基本概念

• 非页节点有\(\lceil n/2\rceil \sim n\)个子节点，叶节点有\(\lceil(n-1)/2\rceil \sim n-1\)个值。
• 支持操作：增删查改（具体见ADS中B+树的各种操作），复杂度为\(\log{N}\)

Bottom up B+ tree Build

对于一个序列，若要将其构建成B+树，需要经过以下流程

• 对序列进行排序
• 对序列进行划分（根据B+树的支持块大小进行划分）比如对于支持n=5的B+树，排序长度为13的序列，则划分为4+4+3+2(最后两块不能是4+1，因为\(1<\lceil (4-1)/2\rceil\))
• 构建完最底层之后，再从下至上构建
• 写入磁盘（seek一次，然后顺序写入）

合并B+树

如果要合并两个B+树，流程如下

• 从磁盘中读取B+树的叶子节点（seek一次，然后顺序读出，因为叶子节点是连续存储的）
• 合并有序序列
• 重复Bottom up B+ tree build的操作