跳跃表(SkipList)

跳跃表是一种基于有序链表的拓展，简称跳表。

下面正式开始了哦，跟着思路来，非常简单理解:

给定一个有序链表：

1->2->3->5->6->7->8

跳表的思想就是利用了类似索引的思想，提取出链表中的部分关键节点，然后再用二分查找。

上面的有序链表，把奇数作为关键节点提取出来：

上面只是介绍了基本思想，其实还可以继续优化，看到这别担心，难度不会增加，也非常好理解:

既然上面提取了一层节点作为索引，那是不是也可以进一步提取？

有了2级索引后，插入的节点可以先和2级索引比较，确定大体范围然后再和1级索引比较最后再回到原链表，找到并插入对应的位置。

节点多的时候还可以进一步提取，保证每一层是上一昌启层节点的一半。提取的极限是同一层只有两个节点的时候，因为一个节点比较没有意义。

到这里，多层链表结构就提取完了，这就是跳跃表。

当大量新节点通过逐层比较插入到链表中后，上层节点就会显得不够用，这就需要从新节点中“提拔”一部分节点到上一层，问题就是“提拔”谁呢(如何选择索引)？

跳表设计者采用了“抛硬币”的方法，随机决定新节点是否提拔。因为跳表的添加和删除的节点是不可预测的，很难用算法保证跳表的索引分布始终均匀。虽然抛硬币的方式不能保证绝对均匀，但大体上是趋于均匀的。

比如说，9插入到链表后，开始分析蔽神：

跳跃表插入 *** 作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。

删除的时候只要在索引耐并如层找到要删除的节点，然后删除每一层相同的节点即可。如果某一层删到只剩下一个，那么整层都可以删掉。比如删除5:

跳跃表删除 *** 作的时间复杂度是O（logN）。

跳表维持结构平衡的成本较低，完全靠随机。二叉查找树在多次插入和删除后需要重新保持自平衡。

Redis的五种数据类型之一Sorted-set(zset)这种有序集合，正是对于跳跃表的改进和应用。

还有Java中的ConcurrentSkipListMap和ConcurrentSkipListSet内部都是用跳表的数据结构。

我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。

跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查 *** 作。

当我们要在该单链表中查找某个数据的时候需要的时间复杂度为O(n).

怎么提高查询效率呢？如果我们给该单链表加一级索引，将会改善查询效率。

如图所示，当我们每隔一个节点就提取出来一个元素到上一层，把这一层称作索引，其中的down指针指向原始链表。

当我们查找元素16的时候，单链表需要比较10次，而加过索引的两级链表只需要比较7次。当数据量增大到一定程度的时候，效率将会有显著的提升。

如果我们再加多几级索引的话，效率将会进一步提升。 这种链表加多级索引的结构，就叫做跳表 。

与二分查找类似，跳跃表能够在 O(㏒n)的时间复杂度之下完成查找，与红黑树等数据结构查找的时间复杂度相同，但是相比之下，跳跃表能够更好的支持并发 *** 作，而且实现这样的结构比红黑树等数据结构要简单、直观许多。

跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美：查找、删除、添加等 *** 作都可以在对数期望时间下完成。跳跃表体现了“ 空间换时间 ”的思想,

从本质上来说，跳跃表是在单链表的基础上在选取部分结点添加索引，这些索引在逻辑关系上构成了一个新的线性表，并且索引的层数可以叠加，生成二级索引、三级索引、多级索引，以实现对结点的跳跃查找的功能。

与二分查找类似，跳跃表能够在 O(㏒n)的时间复杂度之下完成查找，与粗好红黑树等数据结构查找的时间复杂度相同，但是相比之下，跳跃表能够更好的支持并发 *** 作，而且实现这样的结构比红黑树等数据结构要简单、直观许多。

但是现在问题来了，上文我举的例子是一个很完美的跳跃表，它严格地按照二分法的思想建立了捷径。从理论上讲，单个跳跃表的层数按照严格二分的条件建立，层数就应该是 ㏒n 层(以2为底，n 为结点个数),但是在实际 *** 作中，我们的数据会刚刚好是 2 的 n 次方吗？如果不是这么刚好的数据，没办法严格地二分，我要怎么开辟捷径呢？如果我对这个跳跃表进行插入或删除 *** 作，破坏了严格地二分结构，又该怎么办？如果我们要强行解决这些问题，那就又要引入一大堆七七八八又难以实现的规则了，只伏凳铅怕这么做比建一棵树更为困难了。

既然我们没有办法很好地严格二分，也没有很好缺好的规则去描述这些问题的处理方式，那么我们就不使用严格二分的方法就行了啊，不要一条绝路走到黑嘛！分析一下我们的目的，我们希望的事情是让查找 *** 作的效率提升，如果我只开辟一条捷径，效率也确确实实是提升了的，如果能继续开辟捷径，如果最后我们能达到严格地二分，效率就会被提升，那也就是说我们并不是为了要实现二分，而是通过不断地努力去尽量地实现二分。

我们无法直接证明这个事实，但是我们可以通过“频率的稳定性”得到启发，提出了概率的定义，进而确定了事件的概率。从我举的例子里，我们不仅得到了启发，更是找到了解决问题的方法。也就是说，我们找到某种方式来实现捷径的开辟，这种方式在统计学的角度来说，可以往严格二分的情况趋近，在理论上实现 O(㏒n) 的时间复杂度。

跳跃表只需要从最上层开始遍历，由于每一层的链表都是有序的，因此当查找的“键”不存在于某一层中的时候，只需要在比查找目标的“键”要大的结点向下一次跳跃即可，重复 *** 作，直至跳跃到最底层的链表。

1、先从顶层开始遍历,与16进行对比小，进入下一层。

2、与4进行比较,比4大,当前结点置为4结点，与16进行比较,进入下一层。

3、 与8进行比较,没有比8大,切换为当前结点4。

4、将节点4的下一个节点8和当前值进行比较,相同,取出。

1、函数实现向跳跃表中插入一个“键”为 key，“值”为 value 的结点。由于我们进行插入 *** 作时，插入结点的层数先要确定因此需要进行抛硬币实验确定占有层数。

2、由于新结点根据占有的层数不同，它的后继可能有多个结点，因此需要用一个指针通过“键”进行试探，找到对应的“键”的所有后继结点，在创建结点之后依次修改结点每一层的后继，不要忘了给结点判空。在插入 *** 作时，“键”可能已经存在，此时可以直接覆盖“值”就行了，也可以让用户决定，可以适当发挥。

 寻找节点的位置，获取到插入节点的前一个节点,

3、与链表的 *** 作执行相同的节点 *** 作,地址替换。

模拟插入 *** 作

首先我们需要用一个试探指针找到需要插入的结点的前驱，即用红色的框框出来的结点。需要注意的是，由于当前的跳跃表只有 2 层，而新结点被 3 层占有，因此新结点在第 3 层的前驱就是头结点。

接下来的 *** 作与单链表相同，只是需要同时对每一层都 *** 作。如图所示，红色箭头表示结点之间需要切断的逻辑联系，蓝色的箭头表示插入 *** 作新建立的联系。

插入的最终效果应该是如图所示的。

由于需要删除的结点在每一层的前驱的后继都会因删除 *** 作而改变，所以和插入 *** 作相同，需要一个试探指针找到删除结点在每一层的前驱的后继，并拷贝。接着需要修改删除结点在每一层的前驱的后继为删除结点在每一层的后继，保证跳跃表的每一层的逻辑顺序仍然是能够正确描述。

1、根据删除的值找到当前值在跳表中的前驱结点 head  4 

2、判断结点4的后驱结点的值是否为8，不是，直接跳出。当前值在跳表中不存在。

3、循环遍历每一层,执行地址变更。当前结点可能在其他层不存在结点，因此在变更的时候要判断是当前层是否存在该结点。

// 跳表中存储的是正整数，并且存储的数据是不重复的

public class SkipListTest {

//最大索引层数

    private static  int MAX_LEVEL =16

//头节点

    private Node head

//索引的层级数,默认为1

    private int  levelCount =1

private Random random

class Node{

//结点值

      private int value

//当前节点的所有后驱节点。1-maxlevel 层。

      private Node[]nodes =new Node[MAX_LEVEL]

//当前节点的层数

      private  int maxLevel

public Node(int value,int maxLevel) {

this.value = value

this.maxLevel = maxLevel

}

}

public Node get(int value){

//1、从最高层开始遍历

      Node cur =head

for (int i =levelCount-1i >=0 i--) {

//找到比该值小的那个结点

          while (cur.nodes[i]!=null &&cur.nodes[i].value <value){

cur = cur.nodes[i]

}

//开始寻找下一层,直到找到最后一层

      }

if(cur.nodes[0]!=null&&cur.nodes[0].value == value){

return cur.nodes[0]

}

return null

}

public void insert(int number){

//1、获取要插入的索引层数量

      int level = randomLevel()

//2、创建新节点

      Node newNode =new Node(number,level)

//3、获取每一层的前驱结点

      Node update[] =new Node[level]

//遍历索引层

      Node c =head

for (int i =level-1i >=0 i--) {

while (c.nodes[i]!=null&&c.nodes[i].value

c = c.nodes[i]

}

update[i] = c

}

//4、更新每一层的索引结构

      for (int i =0i

//当前结点的后驱结点

          newNode.nodes[i] =update[i].nodes[i]

//当前结点的前驱

          update[i].nodes[i] =newNode.nodes[i]

}

//5、更新索引层

      if(levelCount

levelCount =level

}

}

public void delete(int value){

//1、获取每一层比当前值小的前一个结点

      Node[]update =new Node[levelCount]

Node p =head

for(int i =levelCount -1i >=0--i){

while(p.nodes[i] !=null &&p.nodes[i].value <value){

p = p.nodes[i]

}

update[i] = p

}

//2、如果最后一层的结点的与当前值相同,进入变更指针 *** 作。

      if(p.nodes[0] !=null &&p.nodes[0].value == value){

for(int i =levelCount -1i >=0--i){

//从最高层开始变更,如果值相等才进行变更

              if(update[i].nodes[i] !=null &&update[i].nodes[i].value == value){

update[i].nodes[i] =update[i].nodes[i].nodes[i]

}

}

}

}

// 随机函数

    private int randomLevel(){

int level =1

for(int i =1i

if(random.nextInt() %2 ==1){

level++

}

}

return level

}

}

hbase的核心数据结构为LSM树。

LSM树分为内存部分和磁盘部分。

内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，由于考虑并发性能，HBase选择了表现更优秀的跳跃表。

磁盘部渣扒分是由一个个独立的文件组成败梁困，每一个文件又是由一个个数据块组成。对于数据存储在磁盘上的数据库系统来说，磁盘寻道以及数据读取都是非常耗时的 *** 作（简称IO耗时）。为了避免不必要的IO耗时，可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（察念BloomFilter）。

LSM树介绍：

LSM树是一种磁盘数据的索引结构。LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入 *** 作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写）。

一个LSM树的索引内存部分是一个ConcurrentSkipListMap，Key是rowkey、column family、qualifier、type以及timestamp， Value是字节数组。随着数据不断写入MemStore，一旦内存超过阈值会将数据flush到磁盘，生产HFile；多个小HFile文件会compact成一个大HFile。

---