Hbase数据结构与算法

Hbase的一个列族本质上是一棵LSM树（Log Structured Merge Tree）。LSM树分为内存和磁盘部分。内存部分是一个维护有序数据集合的数据结构。hbase选择了跳表。磁盘部分是由一个个独立文件组成，每一个文件都是一个数据块。对于数据存储在磁盘上的系统来说，磁盘寻道以及数据读取都是非常耗时的操作。因此，为了避免不必要的IO耗时。因此在次盘中存储一些额外的二进制数据，这些数据用来判断制定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器

跳表

跳表插入/删除/查找的时间复杂度是O(logN)

LSM树

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

KeyValue存储格式

一般来说，LSM存储的事多个keyvalue组成的集合，每一个keyvalue一般会用一个字节数组表示。字节数组主要分为以下几个部分：

• keyLen，valueLen,rowkeyLen 表示占用的字节长度
• rowkeybytes：占用rowkeylen个字节，用来存储rowkey的二进制内容
• familyLen：占用1字节，用来存储family二进制内容。
• qualifierBytes。存储qualifier内容
• timestamp
• type

多路归并

Ni*logK

LSM树的索引结构

内存部分：ConcurrentSkipListMap，key就是前面所说的key部分，value是一个字节数组。数据写入时，直接写入Memstore中。随着不断写入，一旦内存超过一定的阈值，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘上。
随着写入增加，内存数据会不断的刷新到磁盘上，最终磁盘上数据文件会越来越多。如果数据有读取操作，将需要将大量文件进行归并，之后才能读取所需要的数据。因为需要讲那些key相同的数据全局综合起来，最终选择出合适的版本返回给用户。因此我们可以设置一定的策略将多个hfile进行多路规定，合并成一个文件，文件个数越少，读取性能越好。
合并分为minor compact 和major compact

布隆过滤器

array个数 = K * ｜A｜/ln2
布隆过滤器是由一个长度为N的 01array组成，首先将array每一个开始元素设置为0，做K次哈希，第i次哈希值对N取模得到一个index(i), 即index(i) = hash_i(w)%N.可以得到w可能存在于集合A中。w肯定不在集合A中。
hbase的get操作就是通过运用极低成本高效率的布隆过滤器过滤掉大量无效的数据块，节省磁盘IO