> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# 落盘的b+树
- URL: https://blog.hacking.pub/2019/10/08/luo-pan-de-b-shu/
- Published: 2019-10-08T13:28:24.000Z
- Updated: 2019-10-08T13:34:16.000Z
- Author: chainhelen

#### 参考内容

项目地址: [bptree](https://github.com/chainhelen/bptree?ref=blog.hacking.pub)

代码参考：主要参考了两个版本[bplustree](https://github.com/begeekmyfriend/bplustree?ref=blog.hacking.pub)和go的内存版本[bptree](https://github.com/collinglass/bptree?ref=blog.hacking.pub) 

定义参考：对于b+树的定义有太多了，主要参考了[b+树总结](https://www.jianshu.com/p/71700a464e97?ref=blog.hacking.pub)

#### 实现细节

1. 可以提前申请一些节点(leaf和node)结构的内存池，避免大量内存申请和释放
2. 每个磁盘块（系统和磁盘交互的最小逻辑单位）都是一个节点所占空间大小（会有浪费），需要序列化写入文件
3. 因为是递归操作，所以每一个函数当出现将某块磁盘节点映射成内存节点，都应该在函数结束前某个时机（可能其他调用了其他递归函数也进行了映射，造成数据覆盖）刷盘
4. 文件开始位置并不一定是根节点，因为节点会不断增加和删减，所以在读取文件时候需要`check root`
5. 还有一些事务性问题，比方当前节点已经刷盘，但是延伸更新父亲节点刷盘失败，这种情况暂时没有考虑

#### b+树优势

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

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

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

#### 基本逻辑

**写入节点逻辑**  
![bplustree.png](https://blog.hacking.pub/qiniu/%E8%90%BD%E7%9B%98%E7%9A%84b%2B%E6%A0%91/bplustree.png)

**删除节点逻辑**  
![bplustree.delete.png](https://blog.hacking.pub/qiniu/%E8%90%BD%E7%9B%98%E7%9A%84b%2B%E6%A0%91/bplustree.delete.png) 

> drawio原始文件下载 [bplustree.drawio](http://img.hacking.pub/%E8%90%BD%E7%9B%98%E7%9A%84b+%E6%A0%91/bplustree.drawio?ref=blog.hacking.pub)，[bplustree.delete.drawio](http://img.hacking.pub/%E8%90%BD%E7%9B%98%E7%9A%84b+%E6%A0%91/bplustree.delete.drawio?ref=blog.hacking.pub)