Log-Structured Merge Tree 日志结构合并树
下班闲来无事看了下这种树的结构,这种树的结构还是比较简单的,leveldb的存储结构用的就是这种。
简言之就是 将数据划分为多份,每一份存储一部分数据。
每一份数据都是有序的,这样来一个数据进行查询的时候对每一部分可以进行二分查找,速度可以快很多。
真正存储的时候每一部分数据是不进行二分查找的,而是有一个类似于bitmap的结构记录着里面有哪些数据,这样查询的速度又可以增加很多。
由于数据量在增加,所以各个小部分的树之间有可能存在合并重新排序,所以这种结构被称为Log-Structured Merge。