落盘的b+树

参考内容

项目地址: bptree

代码参考：主要参考了两个版本bplustree和go的内存版本bptree　　

定义参考：对于b+树的定义有太多了，主要参考了b+树总结

实现细节

1. 可以提前申请一些节点(leaf和node)结构的内存池，避免大量内存申请和释放
2. 每个磁盘块（系统和磁盘交互的最小逻辑单位）都是一个节点所占空间大小（会有浪费），需要序列化写入文件
3. 因为是递归操作，所以每一个函数当出现将某块磁盘节点映射成内存节点，都应该在函数结束前某个时机（可能其他调用了其他递归函数也进行了映射，造成数据覆盖）刷盘

4. 文件开始位置并不一定是根节点，因为节点会不断增加和删减，所以在读取文件时候需要check root　　

5. 还有一些事务性问题，比方当前节点已经刷盘，但是延伸更新父亲节点刷盘失败，这种情况暂时没有考虑　　

b+树优势

操作系统无论是读操作，还是写操作，都是以block为单位进行的，当以block作为node的存储时，可以充分利用系统与磁盘交互方式节省交互次数　　　　

相比较b树而言，b+树在查询时候性能更稳定（必须到根节点才能得出结果，mysql之类的做了缓存可能不太一样），而且对于命中的索引能进行范围查询

b+树的形状更偏向于宽矮的方式，所以深度比较浅，对于能大量减少对于磁盘的读写次数（相比较红黑树）

基本逻辑

写入节点逻辑

删除节点逻辑
　

drawio原始文件下载 bplustree.drawio，bplustree.delete.drawio