hbase 读书笔记——数据结构

跳跃表

跳跃表广泛使用于KV数据库中，诸如Redis、LevelDB、HBase都把跳跃表作为一种维护有序数据集合的基础数据结构。
性质1一个节点落在第k层的概率为pk-1。
性质2一个最底层链表有n个元素的跳跃表，总共元素个数，其中k为跳跃表的高度。
性质3跳跃表的高度为O(logn)。
性质4跳跃表的查询时间复杂度为O(logN)。
性质5跳跃表的插入/删除时间复杂度为O(logN)。

LSM

LSM树本质上和B+树一样，是一种磁盘数据的索引结构。但和B+树不同的是，LSM树的索引对写入请求更友好。
LSM树的索引一般由两部分组成，一部分是内存部分，一部分是磁盘部分。内存部分一般采用跳跃表来维护一个有序的KeyValue集合。磁盘部分一般由多个内部KeyValue有序的文件组成。

LSM中存储的是多个KeyValue组成的集合，每一个KeyValue一般都会用一个字节数组来表示。

• 性质：
• Key的二进制内容。
• 一个表示版本号的64位long值，在HBase中对应timestamp；这个版本号通常表示数据的写入先后顺序，版本号越大的数据，越优先被用户读取。甚至会设计一定的策略，将那些版本号较小的数据过期淘汰（HBase中有TTL策略）。
• LSM树中存放的并非数据本身，而是操作记录。这对应了LSM树（Log-Structured Merge-Tree）中Log的含义，即操作日志。

2.多路归并

image.png

3. LSM树的索引结构
   内存部分和磁盘部分

• 内存部分是一个ConcurrentSkipListMap，Key就是前面所说的Key部分，Value是一个字节数组。数据写入时，直接写入MemStore中。
  随着不断写入，一旦内存占用超过一定的阈值时，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘上。
• 内存部分导出形成一个有序数据文件的过程称为f lush。为了避免flush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放。这样，就可以通过两个MemStore来实现稳定的写入性能。

image.png

布隆过滤器

实现一个基于磁盘和内存的哈希索引当然可以解决这个问题。而另一种低成本的方式就是借助布隆过滤器（Bloom Filter）来实现。
HBase的Get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省大量磁盘IO。