982
“写优化”的数据结构(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帮不了你。
小结
做“写优化”的数据结构读不一定慢的。
比如在写的过程中，你已经走了root-node1-node2…-nodex这条path，可认为它已在page cache里，当你读的时候，root无需从磁盘读取，node1也无需从磁盘，这样“读”就揩“写”的油。反过来，“写”也可以揩”读“的油，所以即使在读写混合的时候，仍可互利。
如果node大小为4MB（leaf节点可设置的更大些），一个高度为6的tree就是TB级了，这样leaf节点是很少被touch到的，所以在page cache里的基本都是inner node，很爽了 
如果你“嫌弃”page cache的机制，可以尝试自己的cache + Direct IO (cascadb用的AIO）这条路。
期待更多的引擎来尝试下buffered tree!
BTW:大块写在SSD上的好处就是Write amplification（https://en.wikipedia.org/wiki/Write_amplification）的降低。
最后更新：2017-04-03 07:57:05