存储结构
B+树
B+树是RDBMS常用的底层存储架构
B+树表示为一个动态的,多层并含有上下界的索引,同时也会维护每一段(页)所包含的主键数目
B+数的特性使其能通过主键进行高效的查找,插入和删除,在此不再赘述
LSM树
LSM树(log structured merge tree)则是另一种组织形式
LSM的核心思路是在假定内存足够大的情况下,数据尽量驻留内存.等待积累到足够多时.再使用归并排序将数据合并
LSM的主要步骤如下
- 输入数据首先会被存储在内存日志文件中,这些数据在内存日志中有结构(键值对)有组织(始终保持有序).如果数据发生变化也会首先更新到内存日志中
- 随着内存日志的增长,最终会将这些有序键值对溢写到一个文件中,并同时在创建一个新的文件
这个存储文件 - 多次溢写后形成多个存储文件,后台线程会将这些存储文件聚合为一个大存储文件
- 查询首先查找内存日志,然后再查找存储文件(也就是内存与磁盘对用户透明)
- 删除首先视为一种特殊的标记更改(标记数据查询时跳过,然后在聚合阶段实际删除)
B+树 VS LSM树
LSM 与 BTree 最大的差异就是在读和写性能的取舍
B+树的优势在于读性能优异.因为可以始终借助类似二分查找的范围查找来定位数据
B+数的劣势在于写入,B+的写入是单条写入的,并且每一次写入都是一个B+寻址过程(首先在B+中定位数据,再插入数据)
LSM树是一种放弃部分读能力来换取最大的写入能力,LSM的本意就是结构化合并树的意思
LSM呈现一种批量写入特征(无论是内存日志积累,还是溢写合并,LCM没有单条操作).
LSM的劣势主要体现在,LSM的本质是N个有序小树,这样在查找时,虽然在小树内部可以依据二分查找提速,但因为无法确定所在树存在.小树之间是需要遍历
LSM的常用优化
- 布隆过滤桶
依靠布隆过滤桶,可以快速知道某个小树内是否含有数据.(当然布隆过滤桶的特性导致,说不在肯定不在,说在但不一定在) - 小树合并
小树继续合并,最终成为一棵大树,这样就能使用二分查找了.这也是HBase的最终选择