Redis跳跃表

为什么使用跳跃表

跳跃表(skiplist)作为Redis的底层编码之一,在牺牲一定内存空间的情况下,它可以提高链表的查询效率。众所周知,链表的查询时间复杂度由节点个数来决定的,它的时间复杂度为O(n)。虽然链表很适合存储大量节点,但是随着节点越来越多,它的查询越来越慢,这与链表适合存储大量节点这一说法就非常矛盾了。

那么该如何解决这一问题呢?反观常用的关系型数据库,比如Mysql,在查询非常慢的时候,我们通常会去在查询条件的字段上建索引来提高它的查询效率,既然如此,为什么Redis不可以呢?

skiplist主要应用于Redis的有序集合中(zset),这个和Mysql建立索引的道理是一样的,集合中的元素必须是有序的,就像新华字典一样,根据拼音从a - z排序,如果要找某一个元素,先知道这个元素是什么拼音开头的,然后去索引页找(索引部分只有几页,所以找起来很快),大索引下面还有二级索引(ai、an、ang ..),然后去对应的页数去找(实际位置),这样就很快了。

image.png

跳跃表查找过程

跳跃表在不改变原有集合结构的基础上垂直扩展索引,下面是集合的所有元素,比如现在要查找46,需要遍历7个节点

image.png

第二层在第原有数据的基础上建立索引,索引值分别是2,21,37,55,现在查找46,只需要遍历4次,2 -> 21 -> 37 -> 46

image.png

如果想查询速度更快,可以在第二层索引的基础上再建立一层索引,查询效率进一步提升,只需要查3次就找到了46的元素,21 -> 37 -> 46

image.png

可以看到,虽然查询性能进一步提升了,但是内存浪费也非常严重,所以并不是索引越多越好

跳跃表源码解析

// skiplist的节点
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    robj *obj;							// 数据值
    double score;						// 分数,根据这个决定顺序
    struct zskiplistNode *backward;		// 后退指针,回到上一个zskiplistNode
    // 层
    struct zskiplistLevel {				
        struct zskiplistNode *forward;	// 前进指针,下一个zskiplistNode
        unsigned int span;				// 和下一个zskiplistNode隔了几个节点
    } level[];
} zskiplistNode;

// skiplist的集合
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;	// 首、尾节点引用
    unsigned long length;					// 节点数量
    int level;								// 跳跃表中最大的zskiplistNode的层数
} zskiplist;

// zset底层使用了skiplist
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

结合上面的例子来描述以下结构图
image.png

  • level(层):level数组可以包含多个元素,每个元素都包含一个指向其他节点的指针, 程序可以通过这些层来加快访问其他节点的速度。每次创建一个新跳跃表节点的时候, 程序都会随机生成一个介于 1 和 32 之间的值作为 level 数组的大小, 这个大小就是层的“高度”。
  • forward(前进指针):用于依次访问每个节点,程序首先访问表头,然后在最高的层数并且它的next指向不为NULL,比如上图就从L3开始往下一个节点走,当走到值为55的节点的时候,next指向NULL,那么程序就知道到跳跃表的结尾了。
  • span(跨度):用于记录和下一个节点的距离,指向NULL的跨度为0。和顺序表不一样,跨度并不是用来计算下一个节点的位置的,获取下一个节点的位置直接用forward就行了。跨度其实是用来计算当前节点在跳跃表中的排位的,比如下图:要去查找值为17的的节点:先通过第二层(L2)头结点->2,经过了2个跨度,再降级到第一层(L1)2->17,经过了一个跨度,跨度为3,那么值为17的节点在表中排名第3。
  • backward(后退指针):用于从表尾向表头方向访问节点,跟可以一次跳过多个节点的前进指针不同, 因为每个节点只有一个后退指针, 所以每次只能后退至前一个节点。
  • score(分值):是一个 double 类型的浮点数, 跳跃表中的所有节点都按分值从小到大来排序。在同一个跳跃表中, 各个节点保存的成员对象必须是唯一的, 但是多个节点保存的分值却可以是相同的。如果分值相同的节点将按照成员对象在字典序中的大小来进行排序, 成员对象较小的节点会排在前面(靠近表头的方向), 而成员对象较大的节点则会排在后面(靠近表尾的方向)
  • header 和 tail 指针分别指向跳跃表的表头和表尾节点, 通过这两个指针, 程序定位表头节点和表尾节点的复杂度为 O(1)
  • length:记录节点的数量,程序可以在 O(1) 复杂度内返回跳跃表节点的数量
  • level:用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量, 注意表头节点的层高并不计算在内

参考:http://redisbook.com/preview/skiplist/datastruct.html
https://www.cnblogs.com/hunternet/p/11248192.html
https://blog.csdn.net/qpzkobe/article/details/80056807

# Redis 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×