“写优化”的数据结构(3):small-splittable-tree
如果你感到buffered b-tree 或者 x–y tree还是有点复杂,这里还有简单的。
如果不走tree-like派系,那就走短、平、快的small-splittable-tree的路子,甚至可以玩small-splittable-list。
短就是每个tree单元要小。
平就是tree高度要低。
快就是分裂起来要快(compaction)。
这里的tree可以是b-tree或其他的tree结构都没问题,但在分裂起来,一定要快,不能hang住写线程。
如果你嫌tree结构有高度,还是复杂,那可以来简单的small-splittable-list,也就是所有数据插入完毕,最终是个顺序的list,这个list由多个segment构成,任何两个segment之间不会有区间重叠。
write
--------
每个segment反映到磁盘就是一个文件,比如1.SSL。
这个SSL文件由2部分组成:header和blocks。
header记录区间信息,比如: <pivot1, blockid1> ... <pivotn, blockidn>,用于数据归属block查找。
block里存放的是key-value数据(追加写),每个block大小是固定的(比如256KB),当block满了,就分裂成2个block,当一个SSL里的block都满了(个数等于 SSL-size/block-size),则对这个SSL进行分裂,这个分裂过程也是很快的,没有数据merge过程。
read
------
首先根据key定位到你属于哪个SSL,然后根据header定位到你属于哪个block,这样就搞定了。
small-splittable-list基本就是在往AOF靠拢,但是读起来是很快的。
这种数据结构的缺点就是page cache利用率不高,共享部分太少了,如果是tree,从root到某些inner-node的路径是可共享的,只好做记录级缓存了,kernel帮不了你。
“写优化”的数据结构(4)
http://www.douban.com/note/270008445/
BohuTANG@2013.4
如果不走tree-like派系,那就走短、平、快的small-splittable-tree的路子,甚至可以玩small-splittable-list。
短就是每个tree单元要小。
平就是tree高度要低。
快就是分裂起来要快(compaction)。
这里的tree可以是b-tree或其他的tree结构都没问题,但在分裂起来,一定要快,不能hang住写线程。
如果你嫌tree结构有高度,还是复杂,那可以来简单的small-splittable-list,也就是所有数据插入完毕,最终是个顺序的list,这个list由多个segment构成,任何两个segment之间不会有区间重叠。
write
--------
每个segment反映到磁盘就是一个文件,比如1.SSL。
这个SSL文件由2部分组成:header和blocks。
header记录区间信息,比如: <pivot1, blockid1> ... <pivotn, blockidn>,用于数据归属block查找。
block里存放的是key-value数据(追加写),每个block大小是固定的(比如256KB),当block满了,就分裂成2个block,当一个SSL里的block都满了(个数等于 SSL-size/block-size),则对这个SSL进行分裂,这个分裂过程也是很快的,没有数据merge过程。
read
------
首先根据key定位到你属于哪个SSL,然后根据header定位到你属于哪个block,这样就搞定了。
small-splittable-list基本就是在往AOF靠拢,但是读起来是很快的。
这种数据结构的缺点就是page cache利用率不高,共享部分太少了,如果是tree,从root到某些inner-node的路径是可共享的,只好做记录级缓存了,kernel帮不了你。
“写优化”的数据结构(4)
http://www.douban.com/note/270008445/
BohuTANG@2013.4
热门话题 · · · · · · ( 去话题广场 )
- 收集春天的季节性快乐时刻 734.3万次浏览
- 译者生存实录 新话题 · 271次浏览
- 春天的影像诗 1.9万次浏览
- 我在春天的随手读 1644次浏览
- 生活中哪些是绝对不能被精简掉的物件? 41.3万次浏览
- 那些超级英雄教会我的事 3.2万次浏览