首页 > 代码库 > 存储引擎-Buffer tree

存储引擎-Buffer tree

Buffer-tree 也称为COLA,即cache-oblivious,可以不需要知道具体内存大小和一个块的大小,使用一套逻辑进行处理,因此内存大小可知,内存可能被临时占用去做其它事情。

Buffer-tree典型的实现是TokuDB,在里面被称为Fractal-tree

其算法的基本过程为:

技术分享

  1. 假定有如上图所示的空数据集合。可以认为树的高度为logN,每行要么为空要不为满,具保持是有序的。
  2. 如果再写入一个值“3”,将会写入每一行。

  3. 如果再写入一个值“11”,因为第一行已经写满,所以将“3”取出,和“11”排序,尝试写入第二行。又因为第二行也定满了,所以将第二行取出,对“3”,“11”,“5”,“10”进行排序,写入第四行。结果如下图所示。

技术分享

 

从上面操作过程可知,Buffer-treeLSM的思想类似,每次将数据从上一层取出,与外部数据进行归并后写入新的队列中。这对SAS磁盘非常友好,对磁盘的写入性能有很大的提升。

 

为了提高查询速度,在合并的时候,上层需要持有下层数据的指针。因此最后的结构如下图:

技术分享

 

 

关于B-treeAppend-fileBuffer-tree三种读写方式的算法复杂度为:

 

 

技术分享

举例说明损耗:

对于100W 128字节。N = 2^30log(N) = 30

磁盘中1MB数据块有8192个数据,B = 8192logB = 13

技术分享

 

 

结论:Buffer-treeIO的使用远远小于B树。

 

 

存储引擎-Buffer tree