[加精]Redis 跳表(一种高性能的动态数据结构)

本文作者:duka

一、前言

 跳表(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开发手册中,有序集合支持的操作有

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

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

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

四、简单的跳表实现代码

代码由王争老师完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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();
    }
  }
 
}

五、说明

文章图片由其他作者手绘完成,但联系不到作者本人,本着学习暂时借用,侵权必删!