数据结构与算法：跳表（Skip List）

我们都知道Redis支持以下五种数据类型：

1. 字符串-String
2. 列表-List
3. 哈希-Hash
4. 集合-Set
5. 有序集合-SortedSet

redis基础

Java高频面试题- 每日三连问？【Day1】 — Redis篇

Java高频面试题- 每日三连问？【Day2】 — Redis篇2

现在将焦点锁定在有序集合-SortedSet上，有序集合是如何实现的呢？

带着这个问题开始今天的内容：跳表（Skip List）

01

何为'跳表'

猜数游戏我想大家都玩过，我们用这个例子来理解一下跳表思想：

1~100之间，给定一个数字让你来猜，这个游戏过程可能是这样的

你：50 我：小了 你：75 我：大了 你：65 我：小了 你：70 我：小了 你：72 我：大了 你：71 （猜中！）

分析一下整个过程，在前五轮的猜数中，你用类似二分的思路迅速将目标数字缩小到了70~72之间，于是快速猜中目标数字71，这就是跳表的思想。

02

跳表模型

跳表是基于链表实现的

链表回顾

数据结构与算法--链表（Linked list）

我们用上面的案例先创建一个数字1~100的链表：

接下来你猜数的过程在跳表中是这样实现的：

可以看到我们在基础数据的上层增加了一层，在跳表中叫做：索引链

于是跳表命中数字71的路线是这样的：

你可以想象一下，如果没有索引链层，由于链表不支持像数组那样根据下标随机访问。所以我们如果想命中数字71，就需要从链表的第一个元素开始依次循环70次，跳表让我们的查询更快，这就是跳表的优势。

03

多级索引链

现在我们更改一下游戏规则，数字范围从1~100变为1~10000，这样再让你猜是不是头都大了？即便你建立了索引链，但索引链的长度依然可想而知。

那么跳表是怎么做的呢？

答案是：既然一层索引链不够，就在索引链的上层再建立索引，层层嵌套，直到索引链足够小，形成多级索引：

你也许会想到，多级索引将会导致内存消耗，其实这也是数据结构高效的一个通用思路：用内存换效率。

以上就是今天的内容，关于跳表的篇幅比较简短，相信大家很容易理解，觉得有帮助的话不妨收藏分享，我们下期继续。