leveldb是一个高速的kv数据库,他有很高的写入速度。这是牺牲读取速度为代价的,可是正式这种写入方式造成了level这种数据结构。
kv数据库本来就很简单,一般都不支持更新。所以主要的三种操作为set,get,delete。leveldb再把delete转换成set于是变成了两个操作,一个读一个写。
leveldb的写入只有两步,1.log文件的时序写入,2.内存中的按照key顺序插入。log保证了数据可恢复,插到内存里面的数据根本算不上是数据,应该说是结构良好的写入记录。这些记录到达一定量之后会写入到硬盘,这就是level0的由来。随着记录越来越多,level0上的数据也越来越多,同一个字段可能存在多条记录,这时level就会把level0中的若干个文件和level1中的一个文件合并,合并的时候当然会把同一字段的多条记录转换成一条,或者删掉,如同一次提炼。level1消除了level0的冗余,已经有点数据库的味道了,leveln文件数量增加到一定程度就会进行一次合并进入leveln+1,下一层的数据量是上一层的10倍,并且层数越小越新鲜。这看着有点变种线段树的感觉了。
读取也和线段树非常像,顺序是内存,level0,leveln,按这个顺序总能读到最新纪录,而n的规模是log(数据量)所以也不会很高。
这样简单的思路创造出来高效率,非常优美。