学大数据必懂系列之SkipList

通俗解释：SKipList 翻译为中文就是 跳跃表，SkipList是一种数据结构，用于快速的查找数据的位置，本质上了来讲是一个List链表。

SkipList的作用和使用

在实际的开发过程中，我们经常会遇到查询指定数据的场景，而常用的数据查找的方式无外乎是以下几种：

• 数组查找，通常对于有序数据我们可以直接采用二分查找的方式来降低时间复杂度，缺点就是在于插入和删除的时候，需要将数据整体的迁移倒腾以下。
• 二叉查找树，使用二叉查找算法，可以做到快速的进行插入和删除操作，但是需要维护整个树的结构，否则会变成一个线性的链表
• 平衡二叉树，算是二叉查找树的改良版本，引入了平衡的概念，能够保证二叉树总是平衡的。
• 跳表，跳表可以用于大数据量的高效插入和删除操作，从时间复杂度上来讲基本和平衡二叉树差不多，但是跳表相比二叉树来讲更占用空间，属于通过空间换取时间的一种数据结构。

通过下面一张图我们来了解一下SkipList的结构：

通过上面的结构图我们可以很直观的看出来，整个SkipList的数据结构是怎么样的，最小层是数据链表，存放的是由链表结构组成的所有数据，同时基于原始链表抽出了第一层所有，节点数是原始链表的一半，那么这样我们在查询数据的时候，时间复杂度就会减少了一半，同时呢，基于第一层索引，又抽出了第二层更为稀疏的索引，节点数是第一层的一半。那么通过这种多层索引的数据查询会进一步地提升。

SkipList在大数据组件中的应用

上面提到SKipList是一种高效的用于数据查询的稀疏索引结构，那么在大数据组件里面我们可以想到Kafka底层的数据存储是通过index、segment、file来存储具体数据的，那么在kafka中index就是一种稀疏索引的存储结构，另外在hbase中 rowkey的存储也是一种稀疏索引的结构进行存储的，特别是在这种KV类型的数据库中，基本上都会用到SkipList这种数据结构。

在HBase MemStore内部的数据存储就是使用的SKipList,hbase的数据是按rowkey有序排列的，需要对新添加的数据进行排序，新添加的数据会使用java.concurrent.ConcurrentSkiplistMap构建memstore，最终持久化为hfile存到磁盘.

在数据读取时，会先从memtore中进行查找，查找的时候使用的就是按照skiplist的结构进行的检索，如果memtore中不存在的话，则会在hfile中查找，hfile本身数据也是一种skiplist的结构进行有序存储的。

【学大数据必懂系列】是专注于大数据组件底层技术的原理和实现，使我们更深入的理解大数据组件的内部实现，以及它能够高性能的承载大数据量的核心因素。欢迎关注、点赞、收藏。

下面预告：

学大数据必懂系列之LSM(Log Struct Merge Tree)