MySQL内核月报 2014.08-TokuDB· 数据结构·Fractal-Trees与LSM-Trees对比-阿里云开发者社区

开发者社区> 阿里云数据库> 正文

MySQL内核月报 2014.08-TokuDB· 数据结构·Fractal-Trees与LSM-Trees对比

简介:

最近,TokuDB的创始人Dr. Bradley Kuzmaul发表了一篇文章: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing,从write amplification(WAMP), read amplification(RAMP), and space amplification三个方面对B-Trees,LSM-Trees(LSM)以及Fractal-Trees(FT)进行了详细的分析和对比。

Dr. Bradley Kuzmaul的结果是(页13):
Lsmft.png


从结果来看:


不过,RAMP这块的分析有个小问题:
LSM(leveled)在实现上(比如LevelDB),可以通过meta-info打"锚点"的方式,把RAMP(range)降低甚至做到跟FT一样,如果是point queries的RAMP,则可以通过Bloom filter来降低。

具体的推导过程请阅读原作,下面简单分析下FT的RAMP为啥比LSM的要低。
FT的读方式比较"特殊",由于每个节点都有个message buffer,当有读请求时,需要把inner node的message buffer数据(部分)推(apply)到leaf node,最后只在leaf node上做二分查找,所以RAMP基本就是树的高度。

另外,在数据流向上(compaction过程中数据走向),LSM强调"level"(横向),从level-L根据规则选取部分数据merge到level-(L+1),如果选取数据的策略不好,会抢占磁盘带宽,容易引起性能抖动,而FT强调"root-to-leaf"(纵向),数据从root有序的逐层merge到leaf节点,每条数据的merge路径是很明确的。


版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
阿里云数据库
使用钉钉扫一扫加入圈子
+ 订阅

帮用户承担一切数据库风险,给您何止是安心!

官方博客
链接