Hash 索引机制
Hash索引机制支持增删改及随机读写操作，复杂度是O（1），对查询非常友好。但总所周知Hash是无序的，如果需要有序的数据，那么它便无能无力
B+树
它是一颗横跨内存与磁盘的树，树的子节点可以精确的找到某一个值。但数据在逻辑上是连续的，物理上是不连续的。
比如：有可能1，2在树上靠的非常近，但当需要从磁盘读取数据，说不定一个在一端，磁盘需要扫描一圈才能走到下一个值
所以它对初期读取数据是非常友好，但当数据越来越多时，可能读取性能就会下降。主要原因就数据在磁盘上不是顺序写入的，而是随机写入。
LSM树
日志结构合并数据
- 将数据分为内存和磁盘两部分，两部分可视为小树与大树
- 内存中的小树不断的和磁盘中的大树合并
- 利用内存的读写高效性将数据排序，然后再刷进磁盘就做到顺序写入
特点
- 写放大，写入冗余的多版本数据
- 读放大，读取时需要扫描多版本的数据
- 对写友好，牺牲了读取的性能，读取的性能靠内存的命中率
优化方法
- bloomfilter过滤器—过滤掉冗余的文件，如Hbase中的StoreFile
- 定时合并文件
BloomFilter
- 首先扫描数据的时候通过图中的Meta Index,Intermediate Index，Leaf Index（当没有bloom时）就能判断数据在不在这HFile中。
- 当开启boomFilter后，就会在第三级的索引时使用boomFilter来判断。否则找到那个数据块也是需要二分法扫描的
原理：
-
一个bit 数组，1表示通过存在，0表示不存在
-
多个hash函数
不准确：
可能存在两个rowkey三个hash函数计算的hash的值，可能刚好覆盖的六个位置。
然后当第三个不存在的rowkey计算的三个hash值是前两个rowkey的其中三个位置拼凑的
什么意思：如上图，Z 这个数据的hash结果是在两个蓝色块和一个黄色(姑且叫黄色吧)块
所以bloomfilter过滤器是有不准确率的，bit数组越大，减少hash冲突，不准确率越低。
BloomFilter的结果表示：不存在那么一定不不存在，存在还是需要二分法扫描
HBase中的Bloomfilter的类型及使用
ROW：根据KeyValue中的row来过滤storefile。
举例：假设有2个storefile文件sf1和sf2，
sf1包含kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v）
sf2包含kv3（r3 cf:q1 v）、kv4（r4 cf:q1 v）
如果设置了CF属性中的bloomfilter为ROW，那么get(r1)时就会过滤sf1，get(r3)就会过滤sf2
ROWCOL：根据KeyValue中的row+qualifier来过滤storefile。
举例：假设有2个storefile文件sf1和sf2，
sf1包含kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v）
sf2包含kv3（r1 cf:q2 v）、kv4（r2 cf:q2 v）
如果设置了CF属性中的bloomfilter为ROW，
无论get(r1,q1)还是get(r1,q2)，都会读取sf1+sf2；
而如果设置了CF属性中的bloomfilter为ROWCOL，那么get(r1,q1)就会过滤sf2，get(r1,q2)就会过滤sf1
ROWCOL一定比ROW效果好么？
答案：不一定
a、ROWCOL只对指定列（Qualifier）的随机读（Get）有效,如果应用中的随机读get，只含row，而没有指定读哪个qualifier，那么设置ROWCOL是没有效果的，这种场景就应该使用ROW。
b、如果随机读中指定的列（Qualifier）的数目大于等于2，在0.90版本中ROWCOL是无效的，而在0.92版本以后，HBASE-2794对这一情景作了优化，是有效的（通过KeyValueScanner#seekExactly）
c、如果同一row多个列的数据在应用上是同一时间put的，那么ROW与ROWCOL的效果近似相同，而ROWCOL只对指定了列的随机读才会有效，所以设置为ROW更佳。
引用：https://zhuanlan.zhihu.com/p/135371171