分形树Fractal tree介绍——具体如何结合TokuDB还没有太懂,先记住其和LSM都是一样的适合写密集

简介:

在目前的Mysql数据库中,使用最广泛的是innodb存储引擎。innodb确实是个很不错的存储引擎,就连高性能Mysql里都说了,如果不是有什么很特别的要求,innodb就是最好的选择。当然,这偏文章讲的是TokuDB,不是innodb,相比innodb,TokuDB有着自己的特点。

转自:http://www.kryptosx.info/archives/931.html

BTree和Fractal tree的比较:

目前无论是SQL Server,还是MySQL的innodb,都是用的B+Tree(SQL Server用的是标准的B-Tree)的索引结构。从理论上来说,这个结构在查询过程中应该是不会慢的,此类基于比较的数据结构查询复平均杂度都是logn。B类树就是对于这个进行了优化,让它更适应磁盘,降低树的深度。

随机IO几乎是令所有DBA谈虎色变的一个问题,当数据量小的时候,所有数据都能到内存中那就没有这个问题(其实这个时候也就没有必要用B-Tree的这种块结构了),但是一旦数据量大于内存的话这个问题就出现了。其实从本质来说,k-v存储要解决的问题就是这么一个:尽可能快得写入,以及尽可能快的读取。

这也是设计数据结构时考虑最多的问题,在分析解决方法之前,我们讨论几个极端。走一个极端的话,如果我每次写数据都顺序写,那么对Insert来说的话是最快的,但是每次Query就需要Scan一遍整个表。那么如果我想获取最佳的读性能,那么方法就是像B-Tree那样全部排个序呗。但是因为B-Tree有那样的随机IO,这样我们有没有办法得到顺序写的写性能,

所以,TokuDB中使用了一个称之为Fractal tree(分形树)的索引结构来解决随机IO的问题。它主要是能让随机IO变成顺序IO。

Structure Inserts Point Queries Range Queries
B-Tree Horrible Good Good (young)
Append Wonderful Horrible Horrible
Fractal Tree Good Good Good

Fractal tree(分形树)简介

我们假设有这样一种集合的结构,相邻行空间加倍。每一行要么全满要么全空,全满行的数据都是排好序的。

数据插入:

tokudb1

以上图的数据存储状态为例,如果再写一个值的时候,会写在第一行,比如写了3,这个时候第一行是空的,所以就放到第一行。

再写一个值11的时候,因为第一行已经写满了,所以将3取出来,和11做排序,尝试写第二行。

又因为第二行也满了,所以将第二行的5和10也取出,对3,11,5,10进行排序。写入第三行。

最后的结果:

tokudb2

总体来看:

tokudb3

可以看出,这个数据结构能保证数据块都是满的。如果前面都满了,就会一层层合并下去,直到找到可以写入的块。

没明白的:

插入复杂度为O(log(N)/B),B是一个块存储的数据行数,N是数据量。但是我只想到O(N/B)的复杂度。据说是进行了优化得到的,不过没看懂。

提一下:BTree的复杂度为O(log(N)/log(B)),这是树的深度。B其实就是树的度,树的度越大,深度越低,成对数关系。

总结下Fractal Tree结构特点

  • 由多个有序的数组构成,大小呈指数级增长
  • 数组要么全空,要么全满
  •  数据插入到最小的数组,如果空间不够就将数据进行Merge

查询性能:

如果不进行优化,查询性能并不好。我们需要扫描每一层,最坏情况下IO次数达 log2N。

为了提高查找的性能,TokuDB在每个数据上加了一个forwardpointer,指向下一行中第一个比它大的数据的位置(这个叫做Fractional Cascading)。平均地看,上一级的每个数都把下一级搜索范围限制到了常数个,所以磁盘IO的次数最差应该为O(logN)。

tokudb5

 

 

看到的另一种优化办法:

tokudb4

 总结:

TokuDB主要的优点在于把随机的IO转换成顺序的IO写入。因此获得很好的写入速度,也因为这个,有很好的数据压缩效果。但如果是顺序写入,性能不如BTree。

因此,它适用于存档,大量随机插入的场景。















本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6245167.html,如需转载请自行联系原作者

相关文章
|
6月前
|
存储 算法
树(Tree) - 概念与基础
树(Tree) - 概念与基础
113 2
|
5天前
|
存储 缓存 数据库
数据库索引采用B+树不采用B树的原因
B+树相较于B树,在数据存储、磁盘读写、查询效率及范围查询方面更具优势。数据仅存于叶子节点,便于高效遍历和区间查询;内部节点不含数据,提高缓存命中率;查询路径固定,效率稳定;特别适合数据库索引使用。
18 1
|
存储 数据库 索引
为什么索引底层用b+树不用b树
为什么索引底层用b+树不用b树
86 0
|
6月前
|
存储 大数据 OLTP
将LSM-Tree与非易失内存(NVM)相结合的设计与实现
将LSM-Tree与非易失内存(NVM)相结合的设计与实现
108 1
|
存储 算法 NoSQL
InnoDB为什么采用B+树作为索引模型
InnoDB为什么采用B+树作为索引模型
107 0
|
存储 NoSQL 关系型数据库
《数据密集型型系统设计》LSM-Tree VS BTree
本文为《数据密集型应用系统设计》的读书笔记第一部分第三章的笔记整理,也是个人认为的这本书第一部分最重要的内容。本文将会针对目前数据库系统两个主要阵营进行展开,分别是采用日志型存储结构高速读写的LSM-Tree和面向OLTP的事务数据库BTree两种数据结构对比。
209 0
|
存储 关系型数据库 MySQL
Innodb引擎中B+树一般有几层?能容纳多少数据量?
Innodb引擎中B+树一般有几层?能容纳多少数据量?
1163 0
Innodb引擎中B+树一般有几层?能容纳多少数据量?
|
算法
数据结构和算法(树Tree)
树 概述: 树: 是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。 树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。 二叉树: 是一种更为典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。 树的遍历 前序遍历 前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。 中序遍历 中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。 我们可以通过中序遍历得到一个递增的有序序列 后序遍历 后序遍历是先遍历左子树,然后遍历右子树,最后访
194 0
|
存储 SQL NoSQL
《数据密集型型系统设计》LSM-Tree VS BTree(上)
《数据密集型型系统设计》LSM-Tree VS BTree(上)
175 0