Redis 跳表（一种高性能的动态数据结构）

2021-09-07 07:25:27

一、前言

跳表（Skip List）这种数据结构在一般的数据结构书籍和算法书籍里都不怎么涉及----至少我大学数据结构课程没有讲这种结构。但是跳表确实是一种性能比较优秀的动态数据结构，并且Redis中的有序集合（Sorted Set）就是用跳表实现的。本文先大致了解一下跳表。

二、跳表

1、引出

对于一组有序数据，我们想要在其中查找某个数，如果数据使用数组存储，显然二分法是再适合不过了，但是如果数据是用链表存储的呢？难道我们用从头遍历吗？这样时间复杂度会达到O（n）级别，相比二分法O（logn）级别简直天壤地别。那么如何提高效率呢？

链表的查找时间复杂度算法为1/n(1+2+3+…+n)=O(n),数据出现的位置从第一个到最后一个的概率均为1/n,但是查询时间分别是1，2，，，n，所以平均时间复杂度为O（n）。

2、跳表

我用图片形式来理解跳表。

如下图，对初始链表做一层“索引”，每两个节点提取一个节点到上一层，然后用down指针连接到下一层。

现在我们查询16这个节点。从第一级索引开始，找到13，并且下一个为17，显然16在这两个节点之间，利用down指针下降一层，这次我们遍历2次即可。利用索引后，遍历了5+2=7次，而原始链表需要10次，这里加一层索引遍历次数减少了，效率提高了一点，但还不够，我们继续往上添加索引层。

这里我不再算了，结果是6次，效率又提高了！

那么这种链表加多级索引就是跳表的结构了。

3、链表查询的时间复杂度是多少？

①假设链表有N个节点，按图所示依次往上级添加索引，第一级有N/2个节点，第二级有N/4个节点。。。。

那么第k级索引有N/(2^k)个节点。

②假设索引有h级，*有2个节点。就有N/(2^h)=2--->h=log2N-1(以2为底N的对数)。加上原始链表，那么高度就是log2N了。

③查询时，如果每层都遍历m次（*最多遍历2次，其他级最多遍历m次）那么复杂度就是O（mlgN）（在大O表示法里，logaN级别的复杂度等于lnN复杂度,去掉m就是O（logn）级别了），我们求一下m的值。

在第k级时，我们遍历到了y和z，查询值介于两者之间，通过down指针，到达第k-1级，而这一级y和z之间最多有3个节点，那么m就等于3了。

综上跳表的查询时间复杂度就是O（logn）了。

4、跳表的耗费空间吗？

这个问题就很简单了，空间复杂度就是每层节点和，即n/2+n/4+...+4+2=n-2,空间复杂度就是O（n）了。

当然了这里也可以扩大索引间隔，减少一点索引空间，但是我们还是按照上面的求时间复杂度方法，得到的结果仍是O（logn）。实际应用中，向来是比较乐意用空间换时间的，所以这种做法的意义并不大，因为时间复杂度还是没变！

并且这里我们使用整数作为例子来讲得，软件开发中，链表存的可能是一个很大的对象，索引只需要记录关键字和一些指针，那么额外的空间和原数据相比完全可以忽略！

5、高效的动态插入和删除

我想汉字没有图片表达的清楚，所以还是用图片来表述！

时间复杂度仍是O（logn）。我们说单链表插入复杂度为O(1)，但是这是指插入动作，并不包含查找插入点所耗的时间，加上查找时间O（n），跳表效率还是高一点！

删除要麻烦一点，因为删除的节点要是在索引中，我们还得更新索引，更新索引就得找到前驱节点，当然双链表可以不用考虑了！

6、索引动态更新

考虑这样一种情况

更极端的可以退化成单链表，所以索引的动态更新是必要的！

AVL树是通过左右旋转保持平衡性，而跳表是通过随机函数生成一个值K，然后将节点添加到第一级到第K级索引中。

关于这个随机函数，我没有做深入研究（水平有限，然后有兴趣可以参考redis中关于有序集合的跳表实现）

三、Redis为什么选择跳表？

严格讲Redis还用到了散列表，但是本文讲的是跳表，所以暂时忽略！

在Redis开发手册中，有序集合支持的操作有

插入一个数据
删除一个数据
查找一个数据
迭代输出有序序列
按照区间查找数据

前面可以用其他数据结构完成----比如红黑树，但是最后一个显然用跳表去定位起点（然后逐条输出）更好实现！再者跳表的代码虽然很难但是比起红黑树相对起来要好实现。

但是。。。。。。。红黑树有现成的实现，直接拿来用，而跳表却需要自己实现。。。。。。。

四、简单的跳表实现代码

代码由王争老师完成

package skiplist;
 
import java.util.Random;
 
/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 *
 * Author：ZHENG
 */
public class SkipList {
 
  private static final int MAX_LEVEL = 16;
 
  private int levelCount = 1;
 
  private Node head = new Node();  // 带头链表
 
  private Random r = new Random();
 
  public Node find(int value) {
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }
 
    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }
 
  public void insert(int value) {
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    for (int i = 0; i < level; ++i) {
      update[i] = head;
    }
 
    // record every level largest value which smaller than insert value in update[]
    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;// use update save node in search path
    }
 
    // in search path node next node become new node forwords(next)for (int i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }
 
    // update node hightif (levelCount < level) levelCount = level;
  }
 
  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }
 
    if (p.forwards[0] != null && p.forwards[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }
  }
 
  // 随机 level 次，如果是奇数层数 +1，防止伪随机private int randomLevel() {
    int level = 1;
    for (int i = 1; i < MAX_LEVEL; ++i) {
      if (r.nextInt() % 2 == 1) {
        level++;
      }
    }
 
    return level;
  }
 
  public void printAll() {
    Node p = head;
    while (p.forwards[0] != null) {
      System.out.print(p.forwards[0] + " ");
      p = p.forwards[0];
    }
    System.out.println();
  }
 
  public class Node {
    private int data = -1;
    private Node forwards[] = new Node[MAX_LEVEL];
    private int maxLevel = 0;
 
    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");
 
      return builder.toString();
    }
  }
 
}

码农公寓