LSM-tree
应用于LevelDB
可以支持put,delete,get,batch
存储节点有两种:内存中叫MemTable,磁盘中叫SSTable
当内存的(Mem)存满以后,会转移到SST0,SST存在很多级别一般大的是小的10倍,
如果某一个级别满了,会合并到下一级
SST中有很多block,每个block有很多kv,最后一个额外的block记录每个block的第一个key以及其他参数,例如超时时间等
所有级别中只有0级的SST的key不是递增的,因为是直接由MemTable转移过来的
其他级的SST的key都是递增的,因为每次低级的满了,都会压缩进来
每个SST内部最后一个block还会存储Bloom filter,可以大幅度减少很多不必要的查询
查询出的结果有两种:一定不存在,和可能存在(支持这类操作的还有SuRF)
RockDB
是LevelDB的升级版,可以多线程,范围查找key等等