Redis 跳跃表的实现

本文主要是介绍Redis 跳跃表的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概述

跳跃表 SkipList 是一种有序数据结构，通过在每个节点中维持多个指向其它节点的指针，达到快速访问节点的目的

平均时间复杂度 O（logN），在大部分情况下，跳跃表的效率与平衡树相近，由于跳跃表实现的简易性，所以 Redis 使用跳表代替平衡树。

ZSET 存储元素，使用了 哈希表以及、SkipList 作为底层实现。

typedef struct zset {dict *dict;zskiplist *zsl;
} zset;

zskiplist 数据结构

执行添加命令，ZADD o1 1.0 o2 2.0 o3 3.0，具体节点信息展示如下：

Redis 跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义；其中 zskiplist 保存跳表的整体信息，zskiplistNode 表示具体的跳表节点

zskiplist 跳表的整体属性介绍：

typedef struct zskiplist {// 头节点，尾节点struct zskiplistNode *header, *tail;// 节点数量（不算表头）unsigned long length;// 目前表内节点的最大层数int level;
} zskiplist;

zskiplistNode 跳表节点的属性介绍：

typedef struct zskiplistNode {// member 对象robj *obj;// 分值double score;// 后退指针，指向当前节点的前一个节点，用于表尾向表头遍历时使用struct zskiplistNode *backward;// 层，节点使用 L1、L2、L3 标记节点中的各个层，每个层里面又带有两个属性struct zskiplistLevel {// 前进指针，指向表尾方向的其它节点，当程序从表头向表尾遍历时，会沿着层的前进指针进行struct zskiplistNode *forward;// 这个层跨越的节点数量unsigned int span;} level[];} zskiplistNode;

查找过程

跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。

如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。

插入过程

1. 搜索当前节点的插入位置，搜索过程和上面遍历过程一样
2. 生成插入节点，随机生成 1~32 之间的值作为节点的 level
3. 重排前进指针
4. 重排后退指针

Q&A

• 为什么层数最大是 32

当层数有 32 层时，第 0 层的节点将有 2^64 个，够用。

• zset 为什么不使用平衡树

使用平衡时时，节点变化时，重平衡操作比较复杂，而跳表实现简单。
跳表支持范围查询

这篇关于Redis 跳跃表的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---