Apache HBase内核深度研究

HBase相关算法与数据结构基础知识

跳跃表

暂时先不说跳跃表是什么，在Java里面有一个Map叫：ConcurrentSkipListMap，通过对HBase的源码跟踪，我们发现这些地方使用了它：

Apache HBase内核深度剖析

简单的列了几个，但是观察这几个类所在的模块就可以发现，HBase从客户端，到请求处理，到元数据再到文件存储贯穿HBase的整个生命周期中的各个重要环节，都能看到它的身影，Map那么多，为何偏偏HBase选择了这个?接下来我们仔细分析下。

在算法概念里面有一种数据结构叫跳跃表，顾名思义，之所以叫跳跃表就是因为在查找的时候可以快速的跳过部分列表，用来提升查找效率，跳跃表的查找效率可以和二叉树相比为O(log(N))，这个算法的实现在Java中的ConcurrentSkipListMap就是实现跳跃表的相关算法。

首先我们看一个有序的全量表：

Apache HBase内核深度剖析

(有序全量链表)

假设我们要从中找出 可以发现需要比较的次数(比较次数不是循环次数)为<3，5，8>共计16次，可以看到对这样一个有序链表进行查找比较的次数会非常多，那么有没有办法对这种查找做优化。当然是有的，对于这种查找耳熟能详从数据结构的基础课程开始大家就知道二叉树，折半查找，值查找都属于解决这类问题的方法，自然跳跃表也是解决这类问题的方法之一。

跳跃表的思路和如今大部分大数据组件像kylin对海量数据下的快速查找的解决思路非常相似，都是通过某种逻辑提前将部分数据做预处理，然后查找的时候进行快速匹配，典型的空间换时间，那么对于跳跃表来说，它的预处理的方式如下：

Apache HBase内核深度剖析

(跳跃表)

可以看到，跳跃表是按照层次构造的，最底层是一个全量有序链表，依次向上都是它的精简版，而在上层链表中节点的后续下一步的节点是以随机化的方式进行的，因此在上层链表中可以跳过部分列表，也叫跳跃表，特点如下：

链表层从上往下查找

跳跃表由很多层组成

每一层都是一个有序链表

最底层是全量有序链表

如果一个元素出现在上层的某个节点那么它一定会出现在下层的链表

每一个元素都有两个指针，一个指向当前链表的下一个元素，一个指向下一层链表的相同节点

假设根据前面的图表我们要查询G这个字母，那么在上面的跳跃表中经过的路径如下：

Apache HBase内核深度剖析

(跳跃表查找路径)

其中红色代表查找所走过的路径。

LSM树

前面讲到了跳跃表的原理，在HBase中较大规模的使用了跳跃表，就是为了增快其查找效率，除了跳跃表之外HBase还使用到了LSM树，LSM树本质上和B+相似，是一种存储在磁盘上的数据的索引格式，但是差异点在于LSM对写入非常高效，实现来说就是无论什么样的写入LSM都是当成一次顺序写入，这一点和HDFS的优点正好契合，HDFS不支持随机写，支持顺序写。LSM数据存储在两个地方，一个是磁盘上一个是内存中，内存中同样使用的跳跃表，内存中是多个有序的文件。

Apache HBase内核深度剖析

(跳跃表与HFile关系)

HBase对LSM的应用采用了如上的结构方式，对于HBase具体的存储文件的分析，在后面专门针对HBase的存储部分进行深入的分析。