Redis系列(七)底层数据结构之跳跃表

前言

Redis 已经是大家耳熟能详的东西了，日常工作也都在使用，面试中也是高频的会涉及到，那么我们对它究竟了解有多深刻呢？

我读了几本 Redis 相关的书籍，尝试去了解它的具体实现，将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中底层的 skiplist（跳跃表） 的实现方法。 它是 Redis 中有序集合键底层实现之一。

可以看到图中，当我在 zsetkey 中放入了两个简单的值时，编码为 ziplist , 而当我插入一个较长的值，zset 的编程方式成为了 skiplist .

对于跳跃表这个数据结构，其底层实现原理及代码实现，本文就不细讲了，如果不太清楚的读者可以看一下这个文章 跳表的原理 %E7%9A%84%E5%8E%9F%E7%90%86%E5%8F%8AConcurrentSkipListMap%E7%9A%84%E6%BA%90%E7%A0%81%E5%AD%A6%E4%B9%A0/#%E6%A6%82%E8%BF%B0), 或者自行 google 了解。

本文仅对 Redis 中跳跃表的实现做一个学习。

定义

首先让我们来看一下，skiplist 的定义：

typedef struct zskiplist{
    // 表头结点和尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned int length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

这几个属性比较简单，其中 header, tail 可以在 O(1) 的时间复杂度内定位到跳跃表的头部和尾部， length 可以在 O(1) 时间复杂度内得到跳跃表的长度。 level 可以知道当前跳跃表最高的层，从而开始从高向低进行查找。

其中 skiplistNode 的节点的定义为：

typedef struct zskiplistNode{
    struct zskiplistLevel{
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
} zskiplistNode;

这个节点的定义有点东西的。

如果了解 Java 中的 ConcurrentSkipListMap 的实现，或者看了上面我的那篇文章的话，就会知道，在 Java 中，一个 所谓的 节点（或者叫索引） 是有两个指针的，一个指向右侧的下一个索引，一个指向自己的下一层索引。

但是 Redis 不是这么实现的，在上面的定义中，可以看到 zskiplistLevel 这个结构是一个数组，用一个数组来保存， 本节点，以及本节点在所有层的索引 .

每个索引中，有两个属性，

• forward

指向右侧的指针，可以在当前层，继续向右走。

• 跨度

这个属性设计的很巧妙，可以用它来计算当前节点在 跳跃表中的一个排名，这就 zset 提供了查看排名的功能。

• backward

后退的指针，如果在高层索引向右走的太多了，可以用后退指针来向后退。

• score and obj

这两个属性用来保存当前节点的真正值以及分值。

层级问题

在 Java 中的 ConcurrentSkipListMap 的实现中，索引每一次向上升级或者不升级，都是随机的，因此：

1. 一个节点是否是一级索引的概率是 50%.
2. 是否是二级索引的概率是 25%.

...

而在 Redis 中，新添加一个节点时，会给该节点随机一个索引层数，而且概率是 25%. 之后将该节点的各层索引与左右的索引相链接。

由于概率是 25%, 因此 Redis 的跳跃表相对于 Java 中的跳跃表，结构更加扁平一些，在查找的时候，在同级索引上可能需要多查询几个。

也是因为结构扁平，因此索引的数量并不是完全的等同于节点数，额外的内存占用只有 50%. 可以为 Redis 服务器节省一点内存。

顺序问题

我们知道，在 zset 中，是可以存储分数一样的值的，此时内部如何存储？直接进行无序存储吗？

如果是这样，当一个 zset 中，所有元素的分值都一样，跳跃表表的性能就会退化成链表的性能吗？

不是这样的，Redis 除了按照分值 排序 之外，还会按照字符串的字典序来存储。

排名问题

前面提到了 跨度 这个属性，当我们需要查找某个元素的排名时，跳跃表首先开始一次查询过程，找到该节点时，也可以找到从顶层索引找到该节点的 查找路径 , 将 路径上的所有节点的 跨度 值相加就是该节点的排名。

总结

Redis 的跳跃表，和 其他语言实现的跳跃表，总体思路一样，在实现方式上有一些自己的小技巧。

跳跃表示 有序集合键 的底层实现之一，表中元素按照 score 大小进行排序，当 score 相同时，元素按照字符串的字典大小进行排序。

相比于 Java 的跳跃表，Redis 的跳跃表的索引层级更加扁平，可以节省一些内存。

参考文章

《Redis 的设计与实现（第二版）》

《Redis 深度历险：核心原理和应用实践》

完。

联系我

最后，欢迎关注我的个人公众号【 呼延十 】，会不定期更新很多后端工程师的学习笔记。

也欢迎直接公众号私信或者邮箱联系我，一定知无不言，言无不尽。

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >------> 呼延十