HBase的一个列簇（Column Family）本质上就是一棵LSM树（Log-Structured Merge-Tree）。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。 一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，这里由于考虑并发性能，HBase选择了表现更优秀的跳跃表。 磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。
对于数据存储在磁盘上的数据库系统来说，磁盘寻道以及数据读取都是非常耗时的操作（简称IO耗时）。因此，为了避免不必要的IO耗时，
可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（Bloom Filter）。
跳跃表
跳跃表（SkipList）是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(logN)。与红黑树以及其他的二分查找树相比， 跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。正因为这些优点，跳跃表广泛使用于KV数据库中， 诸如Redis、LevelDB、HBase都把跳跃表作为一种维护有序数据集合的基础数据结构。
众所周知，链表这种数据结构的查询复杂度为O(N)，这里N是链表中元素的个数。在已经找到要删除元素的情况下，再执行链表的删除操作其实非常高效， 只需把待删除元素前一个元素的next指针指向待删除元素的后一个元素即可，复杂度为O(1)。
但问题是，链表的查询复杂度太高，因为链表在查询的时候，需要逐个元素地查找。如果链表在查找的时候，能够避免依次查找元素， 那么查找复杂度将降低。而跳跃表就是利用这一思想，在链表之上额外存储了一些节点的索引信息，达到避免依次查找元素的目的， 从而将查询复杂度优化为O(logN)。将查询复杂度优化之后，自然也优化了插入和删除的复杂度。
