详解Hbase底层的数据结构——LSMT( 二 ) _Hbase

如果文件中的数据量过大，我们需要另外建立一个索引文件，存储不同的key值对应的offset ，方便我们在读取文件的时候快速查找到我们想要查找的文件。索引文件即上图当中左边部分。

需要注意， SSTable是不可修改的，我们只会用新的SSTable去覆盖旧的，而不会再原本的基础上修改。因为修改会涉及随机读写，这是我们不希望的。

LSM的增删改查
理解了SSTable之后，我们来看下基本的LSM实现原理。

其实最基本的LSM原理非常简单，本质上就是在SSTable的基础上增加了一个Memtable ， Memtable顾名思义就是存放在内存当中的表结构。当然也不一定是表结构，也可以是树结构，这并不影响，总之是一个可以快速增删改查的数据结构，比如红黑树、SkipList都行。其次我们还需要一个log文件，和数据库当中的log一样，记录数据发生的变化。方便系统故障或者是数据丢失的时候进行找回，所以整体的架构如下：

文章插图

查找
我们先来看查找的情况，当我们需要查找一个元素的时候，我们会先查找Memtable 。原因也很好理解，它就在内存当中，不需要额外读取文件，如果Memtable当中没有找到，我们再一个一个查找SSTable ，由于SSTable当中的数据也是顺序存储的，所以我们可以使用二分查找，整个查找的速度也会非常快。

但是有一点，由于SSTable的数量可能会很多，而且我们必须要顺序查找，所以当SSTable数量很大的时候，也会影响查找的速度。为了解决这个问题，我们可以引入布隆过滤器进行优化。我们对每一个SSTable建立一个布隆过滤器，可以快速地判断元素是否在某一个SSTable当中。布隆过滤器判断元素不存在是一定准确的，而判断存在可能会有一个很小的几率失误，但这个失误率是可以控制的，我们可以设置合理的参数，使得失误率足够低。

加上了布隆过滤器之后的查找操作是这样的：

文章插图

上图的星星表示布隆过滤器，也就是说我们先通过布隆过滤器判断元素是否存在之后，再进行查找。

布隆过滤器在之前的文章当中曾经和大家介绍过，有遗忘或者是新关注的同学可以点击下方链接回顾一下。
大数据算法——布隆过滤器

增删改
除了查找之外的其他操作都发生在Memtable当中，比如当我们要增加一个元素的时候，我们直接增加在Memtable ，而不是写入文件。这也保证了增加的速度可以做到非常快。

除此之外，修改和删除也一样，如果需要修改的元素刚好在Memtable当中，没什么好说的我们直接进行修改。那如果不在Memtable当中，如果我们要先查找到再去修改免不了需要进行磁盘读写，这会消耗大量资源。所以我们还是在Memtable当中进行操作，我们会插入这个元素，标记成修改或者是删除。

所以我们可以把增删改这三个操作都看成是添加，但是这就带来了一个问题，这么操作会导致很快Memtable当中就积累了大量数据，而我们的内存资源也是有限的，显然不能无限拓张。为了解决这个问题，我们需要定期将Memtable当中的内容存储到磁盘，存储成一个SSTable 。这也是SSTable的来源， SSTable当中的数据不是凭空出现的，而是LSM落盘产生的。

文章插图

同样，由于我们不断地落盘同样也会导致SSTable的数量增加，前面我们也已经分析过了， SSTable的数量增加会影响我们查找的效率，所以我们不能放任它无限增加。再加上我们还存储了许多修改和删除的信息，我们需要把这些信息落实。为了达成这点，我们需要定期将所有的SSTable合并，在合并的过程当中我们完成数据的删除以及修改工作。换句话说，之前的删除、修改操作只是被记录了下来，直到合并的时候才真正执行。