https://blog.csdn.net/weixin_40954192/article/details/106942029
LSM 存储引擎是在 B+树的基础上衍生过来的，目的就是为了在读和写之间，提高写的性能。所以，LSM 树的弊端也由此可见，对读并不是很友好，所以，针对 LSM 树，有后续 compact，布隆过滤器，blockCache 等优化方式。来弥补对读的查询。
LSM 树的索引一般由 2 部分构成，一部分是内存部分，一部分是磁盘部分。内存部分采用跳跃表来维护一个有序的 KV 集合,也就是 memstore.随着内存不断数据写入，一旦内存占用超过一定的阈值，就把内存部分数据进行导出（这里的 flush 操作实则是通过两个跳跃表来完成的），形成一个有序的数据文件，存储在磁盘上，磁盘部分则是对应的 hFile。
keyValue 存储格式
LSM 树中存储的是多个 keyValue 组成的集合。每一个 KeyValue 由一个字节数组来表示。如图
LSM 索引结构
在 hbase 实现中，memstore 的数据达到某个级别的阈值之后，都会进行 flush 到 disk 中，形成一个 file。（前提为了怕 memstore 内存数据丢失，会先将数据写入到所属 regionServer 的 WAL 预写日志中）这个 file 的存储也就是一个小的 B+树，因为 hbase 一般是部署在 hdfs 上，hdfs 不支持对文件的 update 操作，而且最终随着磁盘文件越来越多，对读的影响很大。所以内存 flush 到磁盘上的小树，定期也会合并成一个大树。来增强读操作的性能，整体上 hbase 就是用了 lsm tree 的思路。
多路归并
为了优化读取操作的性能，hbase 会进行两种类型的 compact。
一种是 major Compact，是将所有的 HFile 一次性多路归并成一个文件。这种方式的好处是，合并之后只有一个文件，这样读取的性能肯定是最高的。但它的问题是合并所有的文件可能需要很长的时间并消耗大量的 IO 贷款，所以 major Compact 不宜使用太频繁，适合周期性的跑。或者我们手动设置在闲时合并。
另一种是 minor Compact，即选中少数几个 Hfile，将他们多路归并成一个文件。这种方式的有点是可以进行局部的 Compact，通过少量的 IO 减少文件个数，提高读取操作的性能。适合较高频率的跑。但它的缺点是只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。
多路归并原理
比如现在我们有 K 个文件，其中第 i 个文件内存存储有 N 个正整数（这些整数在文件内按照从小到大的顺序排序）
多路归并的算法原理就是对每个文件设计一个指针，取出 K 个指针中数值最小的一个（对应的 K 个文件），然后把最小的那个指针后移，接着继续找 K 个指针中数值最小的一个，继续后移指针…直到文件全部读完为止。如图
针对读取操作，还涉及到了布隆过滤器。
布隆过滤器是由一个长度为 N 的 01 数组组成的。首先将数组 array 每个元素初始设为 0，对集合 A 中的每个元素 w，做 K 次哈希，第 i 次哈希值对 N 取模得到一个 index(i).即 index(i) = Hash_i（w） % N,将 array 数组中的 array[index(i)] 置为 1.最终变为一个这些元素为 1 的 01 数组。
正是由于布隆过滤器只需占用极小的空间，便可给出 “可能存在” 和 “肯定不存在”的存在性判断。因此可以提前过滤掉很多不必要的数据块，从而节省了大量的磁盘 IO。hbase 的 get 操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省了大量磁盘 IO。
如果在表中设置了 Bloomfilter，那么 HBase 会在生成 StoreFile 时包含一份 bloomfilter 结构的数据，称其为 MetaBlock；MetaBlock 与 DataBlock（真实的 KeyValue 数据）一起由 LRUBlockCache 维护。所以，开启 bloomfilter 会有一定的存储及内存 cache 开销。
布隆过滤器的 3 中类型：
- none，关闭布隆过滤器功能
- row，按照 rowkey 计算布隆过滤器的二进制串并存储。get 查询时，必须带 rowkey.
- rowcol，按照 rowkey+family+qualifier 这 3 个字段拼出 byte[]来计算布隆过滤器值并存储。如果查询时，get 可以指定到这 3 个字段，则肯定可以通过布隆过滤器提高性能。
任何类型的 get（基于 rowkey 或 row+col）Bloom Filter 的优化都能生效，关键是 get 的类型要匹配 Bloom Filter 的类型
基于 row 的 scan 是没办法走 Bloom Filter 的。因为Bloom Filter是需要事先知道过滤项的。对于顺序 scan 是没有事先办法知道 rowkey 的。而 get 是指明了 rowkey 所以可以用 Bloom Filter，scan 指明 column 同理。
一般意义上的 scan 操作，是没法使用布隆过滤器提升性能的，因为布隆过滤器的 key 不确定。但是 row+col+qualify 的 scan 可以借助布隆过滤器去掉不存在此 qualify 的 storefile，也算是不错的优化了，而且指明 qualify 也能减少流量，因此 scan 尽量指明 qualify
关于BlockCache的内容较多，在后续文章补充。
