【Redis】求求你，别再问跳表了

妖狐艹你老母 2022-12-06 12:50 237阅读 0赞

### 目录 ###

*  跳表
 *   *  使用场景
     *  结构描述
     *  查询算法
     *  插入算法
     *  删除算法
     *  时间复杂度
     *  空间复杂度
     *  总结
     *  Redis使用跳表而不是红黑树？

# 跳表 #

## 使用场景 ##

跳表(Skiplist ）是一个特殊的链表，相比一般的链表，有更高的查找效率，可比拟二叉查找树，  
平均期望的查找、插入、删除**时间复杂度都是O(log n)**，许多知名的开源软件（库）中的数据

结构均采用了跳表这种数据结构∶

*  **Redis中的有序集合zset**
 *  LevelDB、RocksDB、HBase中Memtable
 *  Apache Lucene中的Term Dictionary、Posting List

## 结构描述 ##

我们拿我们以前的有序链表相比：

![在这里插入图片描述][20200913143820639.png_pic_center]

我们可以很清楚的看出，有序链表的查询比较慢，时间复杂度为O(n)，它的删除和插入操作比较快，我们怎样才能让它的查询的时间复杂度也变快呢？

能不能将我们的链表实现二分的查找，也就是longN，答案是肯定的，也就是我们下面所说的这种跳表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center][]

## 查询算法 ##

跳表的查询和我之前做过的一道题特别类似，[二维数组的查找][Link 1]

假设我们查询**31**这个数字

*  我们的header开始，依次进行查询，
 *  31不在负无穷到17，往右边，到达17，继续比较，在17到正无穷之间，往下跑
 *  …

整个查询过程如下所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 1]

## 插入算法 ##

对于插入来说，我们比如要插入一个21的数值

*  类似查询算法，到达17这个点，进一步到达20这个点，然后在20的后面进行插入
 *  插入完了以后，这时候要考虑索引的问题，也就是我们需要将当前这个数值向上几层呢
 *  通过一个50%的概率决定，也就是绝大多数文章讲的抛硬币（\_）

## 删除算法 ##

对于删除来说，我们比如要插入一个17的数值

*  先进行查询操作，找到这个数字
 *  将其及索引进行删除

## 时间复杂度 ##

我们知道单链表查询的时间复杂度为O(n)，而插入、删除操作需要先找到对应的位置，所以插入、删除的时间复杂度也是O(n)。

那么，跳表的时间复杂度是多少呢？

如果按照标准的跳表来看的话，每一级索引减少k/2个元素（k为其下面一级索引的个数），那么整个跳表的高度就是(log n)。

学习过平衡二叉树的同学都知道，它的时间复杂度与树的高度成正比，即O(log n)。

所以，这里跳表的时间复杂度也是O(log n)。（这里不一步步推倒了，只要记住，查询时每次减少一半的元素的时间复杂度都是O(log n)，比如二叉树的查找、二分法查找、归并排序、快速排序）

## 空间复杂度 ##

我们还是以标准的跳表来分析，每两个元素向上提取一个元素，那么，最后**额外**需要的空间就是：

n/2 + (n/2)^2 + (n/2)^3 + … + 8 + 4 + 2 = n - 2

所以，跳表的空间复杂度是O(n)。

## 总结 ##

*  跳表是可以实现二分查找的有序链表
 *  每个元素插入时随机生成它的索引的高度
 *  最低层包含所有的元素
 *  如果一个元素出现在level(x)，那么它肯定出现在x以下的level中
 *  每个索引节点包含两个指针，一个向下，一个向右
 *  跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近

## Redis使用跳表而不是红黑树？ ##

*  插入元素
 *  删除元素
 *  查找元素
 *  有序输出所有元素
 *  查找区间内所有元素

前四项红黑树都可以完成，且时间复杂度与跳表一致

但是，最后一项，红黑树就不如跳表查询的快

在跳表中，要查找区间的元素，我们只要定位到**两个区间端点在最低层级的位置**，然后按顺序遍历元素就可以了，非常高效。

而红黑树只能定位到端点后，再从**首位置开始每次都要查找后继节点**，相对来说是比较耗时的。

**跳表实现起来很容易且易读，红黑树实现起来相对困难**，所以Redis选择使用跳表来实现有序集合。

[20200913143820639.png_pic_center]: /images/20221123/ec89f5d6d70c46a09a59a69edd43cb47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/25c9114f224b4342b88e7ddb70415383.png
[Link 1]: https://blog.csdn.net/qq_40915439/article/details/104592282
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/68b7265850f14cef87c280b3bc86e9ec.png