跳表(skiplist)

hbase的数据是按rowkey有序排列的，需要对新添加的数据进行排序，新添加的数据在内存中会使用java.concurrent.ConcurrentSkiplistMap构建memstore，最终持久化为hfile存到磁盘。

为什么使用skiplist，一方面因为高效，插入操作的时间复杂度为logn，另一方面在写磁盘的时候，从头至尾遍历一遍链表顺序写入磁盘即可。

LSM树 (log structured merge tree)

这里运用的是归并排序的思想，只不过子问题的最底层的数据存在了磁盘上。

Hbase将随机的写入行为，通过在内存中生成的包含部分数据的memstore，最终顺序写入有序数据文件到磁盘，将随机写入转化为了顺序写入。

而数据的可靠性保证，是通过记录写入操作的hlog文件，在异常时进行恢复来保证的，写磁盘的过程也是顺序写，速度很快。

最终的查询过程，乐意类比归并排序的过程，在一个表对应的多个hfile，分别查询想要的结果，再将这些结果进行归并，获取最终想要的结果。

布隆过滤器(bloomfilter)

hbase对数据的读取，是基于block的，查询某个rowkey时，布隆过滤器会告诉我们这个rowkey可能在这个block，或者一定不在这个block。当一定不在时就可以跳过block的读取，节约了时间和IO，当可能存在时再读取到内存执行查找操作。