"写优化"的数据结构(3)：small-splittable-tree
如果你感到buffered b-tree 或者 x�Cy 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帮不了你。
Read full article from "写优化"的数据结构(3)：small-splittable-tree
No comments:
Post a Comment