背景

前文介绍了 k-d树 和 k-d-b树 今天再来这个b-k-d树已经几乎没啥可以参考的资料了
只能硬啃两篇文章了
一个是：medium
一个是发明者的论文

挺好的，人还是要耐着性子读一些难啃的东西

开始介绍

关键点

这个b-k-d树是基于k-d-b树再做的改进，整体的结构是个森林。。（多个k-d-b树）

前文介绍，k-d-b树在做静态查询的时候效果特别好，但是动态插入就不好了。

为了解决这种问题，作者研究了这种炸天的算法，用一个森林来做。。

仔仔细细地看插入算法：

在内存中有一个完全二叉树作为buffer，size=M。外部存储（硬盘）里保存的第i棵树，要么是空的，要么是2^i * M 这么大

1、每次插入的时候，如果buffer没满，那就直接在内存里插入

2、如果内存没满，return；如果满了，找到第一个空的树，将前面所有做merge！

举个例子！

像上面这个图，内存M满了

• 第0棵树，size=2^0 * M = M
• 第1棵树，size=2^1 * M = 2M
• 第2棵树，空的，这时候merge的话，就正好是 M+M+2M = 2^2 * M = 4M

秒啊，数学之美

虽然没全搞懂，但是搞懂到这儿就已经有很开心的感觉，得到了正反馈，后面有机会继续研究吧！学无止境！耐住性子好好读文章，终究会读懂的，不要害怕，不要着急，奥利给！