https://github.com/SirLYC/BPTree
引自维基百科
B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
B+树有一个重要的参数叫阶(m)，决定了一颗B+树每一个节点存储关键子的个数。
每一个节点都会按顺序存储一组关键字，对于非根节点，其关键字树s >= (m + 1) /2。对于叶子节点，其结构中存储指向值的指针，与关键字对应，同时还有一个next指针，指向下一个兄弟叶子节点，因此找到最左叶子节点后可以按关键字顺序遍历；对于非叶子节点，存有s个指向子节点的指针。
B+树通过插入时分裂，删除时向兄弟节点借关键字或合并兄弟节点实现平衡，所有的叶子节点都在同一层。查询、插入、删除效率都是Log(N)。
template<typename K, typename V, class Comp = DefaultCompare<K>>
class BPTree {
private:
....
public:
// constructors and destructors
....
/**
* deserialize from a file
*/
static std::shared_ptr<BPTree<K, V, Comp>> deserialize(const std::string &path, Comp comp);
void put(const K &key, const V &value);
void remove(K &key);
/**
* @return NULL if not exists else a pointer to the value
*/
V *get(const K &key);
bool containsKey(const K &key);
unsigned int getOrder();
unsigned int getSize();
/**
* iterate order by key
* @param func call func(const K& key, const V& value) for each. func returns true means iteration ends
*/
template<typename BiApply>
void foreach(BiApply func);
template<typename BiApply>
void foreachReverse(BiApply func);
/**
* iterate order by key with index (starts from 0)
* @param func call func(int index, const K& key, const V& value) for each. func returns true means iteration ends
*/
template<typename BiApplyIndex>
void foreachIndex(BiApplyIndex func);
template<typename BiApplyIndex>
void foreachIndexReverse(BiApplyIndex func);
void serialize(std::string &path);
/**
* clear the tree
* note that all values allocated will be freed
*/
void clear();
};
Node：B+树的索引节点
主要数据结构如下：
struct Node {
// parent
// if root, parentPtr == NULL
Node *parentPtr = NULL;
// flag
bool leaf;
List<K> keys;
/*-------leaf--------*/
Node *previous = NULL;
Node *next = NULL;
List<V> values;
/*-------index-------*/
List<Node *> childNodePtrs;
// constructor
...
};List：使用定长数组实现的List，比起std::vector<T>功能更简单，效率更高；内存会在移除一定数量元素后减小。
- 文件后缀为bpt
- 所有数据在文件中为小端序
- 头部格式：
| 偏移(byte) | 大小(byte) | 内容 |
|---|---|---|
| 0 | 5 | 固定内容，LYCBP，魔数（magic number） |
| 5 | 1 | sizeof(short)，用来检测文件与本机器是否兼容 |
| 6 | 1 | sizoef(unsigned int) |
| 7 | 1 | sizoef(long) |
| 8 | 4 | sizoefK，每个key占字节数，反序列化时与模板参数不同时抛出异常 |
| 12 | 4 | sizeofV，每个value占字节数 |
| 16 | 4 | order，int类型，B+树的阶 |
| 20 | 4 | initCap，unsigned int类型，每个节点预分配大小 |
| 24 | 4 | size，unsigned int类型，元素个数 |
- 如果size不为0，头部结束后就是根节点，节点有同一的格式，节点前面通用格式：
| 偏移(相对于节点起始，byte) | 大小(byte) | 内容 |
|---|---|---|
| 0 | 1 | leaf，bool类型，标识节点是否为叶子节点 |
| 1 | 4 | kSize，unsigned int类型，该节点拥有的关键字数量 |
| 5 | kSize * sizeofK | 按顺序存储关键字 |
- 对于叶子节点
| 偏移(相对于节点起始，byte) | 大小(byte) | 内容 |
|---|---|---|
| 5 + kSize * sizeofK | kSize*sizeofK | 按顺序存储值 |
- 对于非叶子节点
| 偏移(相对于节点起始，byte) | 大小(byte) | 内容 |
|---|---|---|
| 5 + kSize * sizeofK | kSize * 8 | long类型，按顺序存储字节点在文件中的偏移 |
- 最初的实现是使用vector，测下来性能不是特别理想；
- 基于节点内关键字有序的特点，查找时使用二分查找；
- 存储子节点应该存储指向节点的指针。因为涉及分裂、合并操作，需要复制列表，如果存储的是结构，复制会造成递归复制，效率低，且不易控制内存；
- 因为
root节点没有最少关键字限制，在删除节点操作完成后，需要检查一下root子节点数量，如果为1，直接将root的字节点设置为root，否则删除子节点后可能会造成root的关键字、子节点丢失。 - 每一次插入、删除节点最后一个关键字后需要向上更新parent。
- 分裂、合并操作时对于叶子节点next和previous指针要更新。
测试环境：
测试环境
文件main.cpp有如下宏，1表示开启测试：
// 测试List性能（和vector对比）
#define TEST_LIST 0
// 测试B+树功能正确性
#define TEST_FUNC 0
// 测试B+树的速度（增删查改）
#define TEST_SPEED 0
// 测试B+树的堆使用及内存泄漏（build后使用工具测试）
#define TEST_MEM 0
// 测试B+树的序列化与反序列化
#define TEST_SERIAL 0
- 数据量：10^5
- 增、删数据，断言对应位置是否如预期（功能测试）
- 尾部插入测试（预分配和不预分配）
- 头部插入测试
- 头删除测试
- 尾删除测试
- rangeRemove测试
测试运行结果：
List测试
表格：
| List(ms) | vector(ms) | |
|---|---|---|
| 尾部插入 | 1.506 | 4.724 |
| 尾部插入（预分配空间） | 1.201 | 2.765 |
| 头部插入 | 834.804 | 906.981 |
| 移除一半元素（头部） | 619.493 | 805.379 |
| 移除一半元素（尾部） | 1.444 | 7.523 |
| rangeRemove（一半） | 0.065 | 0.558 |
柱状图：
List测试柱状图
- 数据量：10^5
- 数据插入后断言插入数据存在
- 去除一半数据，断言去除数据不存在，未去除数据存在
- 重新插入所有数据，断言所有数据都存在（测试删除是否破坏结构）
- clear()后断言之前数据都不存在
- 插入全部数据后，测试遍历方法（key顺序测试）
- 拷贝后更改原树，断言新树不受影响
- 测试非基本类型
- 数据量：10^8、10^7、10^6
- B+树阶为 log(TEST_SIZE)^2
- 循环插入数据
- 循环访问所有数据
- 循环移除数据
测试运行结果：
B+树速度测试结果
表格：
| bp tree(ms) | stl map(ms) | |
|---|---|---|
| 插入(10^8) | 192808.064 | 325621.333 |
| 访问(10^8) | 163102.022 | 280150.403 |
| 移除(10^8) | 213982.406 | 366576.836 |
| 插入(10^7) | 11825.821 | 22213.139 |
| 访问(10^7) | 10190.870 | 18137.073 |
| 移除(10^7) | 15130.015 | 22133.154 |
| 插入(10^6) | 1057.291 | 1624.615 |
| 访问(10^6) | 888.186 | 1155.504 |
| 移除(10^6) | 1099.584 | 1495.433 |
柱状图：
B+树速度测试柱状图
- 数据量：10^6
- 阶：20
- 添加数据后移除数据
- 循环5次，添加后调用clear()
- 工具：Xcode Instruments
测试运行结果：
B+树内存测试结果
- 数据量：10^6~0
测试运行结果：
B+树序列化测试结果
表格：
| 数据量 | 序列化(ms) | 反序列化(ms) | 文件大小(bytes) |
|---|---|---|---|
| 0 | 0.116 | 0.039 | 28 |
| 1 | 0.168 | 0.035 | 41 |
| 10 | 0.172 | 0.040 | 113 |
| 10^2 | 0.276 | 0.071 | 986 |
| 10^3 | 1.152 | 0.499 | 9750 |
| 10^4 | 6.628 | 4.304 | 97594 |
| 10^5 | 67.031 | 43.413 | 976255 |
| 10^6 | 624.086 | 384.177 | 9262916 |