落盘的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.drawiobplustree.delete.drawio