redis 从0到1完整学习 （九）：SkipList 数据结构

---

1. 引言

前情提要：
《redis 从0到1完整学习 （一）：安装&初识 redis》
《redis 从0到1完整学习 （二）：redis 常用命令》
《redis 从0到1完整学习 （三）：redis 数据结构》
《redis 从0到1完整学习 （四）：字符串 SDS 数据结构》
《redis 从0到1完整学习 （五）：集合 IntSet 数据结构》
《redis 从0到1完整学习 （六）：Hash 表数据结构》
《redis 从0到1完整学习 （七）：ZipList 数据结构》
《redis 从0到1完整学习 （八）：QuickList 数据结构》

本文主要结合源码来介绍 SkipList 的数据结构

2. redis 源码下载

Redis 源码可以点击这里下载，方便查看其中定义的一些数据结构。

3. skipList 数据结构

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

Redis 使用 skipList 作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis 就会使用 skipList 来为有序集合键的底层实现。

如图是 skipList 的示意图，本质上是用空间换时间，跳表详细的可以参考这里

数据结构如下：

• skipList 是一个双向链表，每个节点都包含 score和 ele 值
• 节点按照 score 值排序，score 值一样则按照 ele 字典排序
• 层级越高，节点的跨度越大

结合上面数据结构，Redis 的 skipList 组织如下：

4. 参考

《redis 从0到1完整学习 （一）：安装&初识 redis》
《redis 从0到1完整学习 （二）：redis 常用命令》
《redis 从0到1完整学习 （三）：redis 数据结构》
《redis 从0到1完整学习 （四）：字符串 SDS 数据结构》
《redis 从0到1完整学习 （五）：集合 IntSet 数据结构》
《redis 从0到1完整学习 （六）：Hash 表数据结构》
《redis 从0到1完整学习 （七）：ZipList 数据结构》
《redis 从0到1完整学习 （八）：QuickList 数据结构》