Redis 跳表（skiplist）知识点详解

忘是亡心i 2023-01-24 04:29 41阅读 0赞

### 目录 ###

*  前言
 *  1. zset底层结构
 *  2. 跳表结构
 *  3. 拓展思考

# 前言 #

关于Redis的相关知识点可看我之前的文章：

1.  [Redis框架从入门到学精（全）][Redis]
2.  [Python操作Redis从入门到精通附代码（全）][Python_Redis]
3.  [Redis的常见面试题（全）][Redis 1]
4.  [一文读懂基于Redis的Amazon MemoryDB数据库][Redis_Amazon MemoryDB]

科普下Redis数据类型中底层的数据结构（常考点）

<table> 
 <thead> 
  <tr> 
   <th>数据类型</th> 
   <th>可以存储的值</th> 
   <th>操作</th> 
   <th>应用场景</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>string</td> 
   <td>字符串、整数或者浮点</td> 
   <td>对整个字符串或者字符串的其中一部分执行操作，对整数和浮点数执行自增或者自减操作</td> 
   <td>做简单的键值对缓存，计数器，共享session以及限速</td> 
  </tr> 
  <tr> 
   <td>list</td> 
   <td>列表</td> 
   <td>从两端压入或者弹出元素，对单个或者多个元素进行修剪，只保留一个范围内的元素</td> 
   <td>存储一些列表型的数据结构，类似粉丝列表、文章的评论列表之类的</td> 
  </tr> 
  <tr> 
   <td>set</td> 
   <td>无序集合</td> 
   <td>添加、获取、移除单个元素，检查一个元素是否存在于集合中。计算交集、并集、差集。从集合里面随机获取元素</td> 
   <td>交集、并集、差集的操作，比如交集，可以把两个人的粉丝列表整一，或者是用户的喜好标签等</td> 
  </tr> 
  <tr> 
   <td>hash</td> 
   <td>包含键值对的无序散列</td> 
   <td>添加、获取、移除单个键值对。获取所有键值对。检查某个键是否存在</td> 
   <td>结构化的数据，比如一个对象</td> 
  </tr> 
  <tr> 
   <td>zset</td> 
   <td>有序集合</td> 
   <td>添加、获取、删除元素。根据分值范围或者成员来获取元素。计算一个键的排名。</td> 
   <td>去重但可以排序，如获取排名前几名的用户，排行榜等</td> 
  </tr> 
 </tbody> 
</table>

# 1. zset底层结构 #

zset主要是有序集合

底层结构有压缩列表和跳表两种结构

<table> 
 <thead> 
  <tr> 
   <th>数据结构</th> 
   <th>描述</th> 
   <th>优点</th> 
   <th>缺点</th> 
   <th>应用场景</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>压缩列表</td> 
   <td>在列表的前面加入了列表长度、尾部偏移量、列表元素个数，在列表的后面加入了列表结束标识</td> 
   <td>有利于快速的找到首尾节点</td> 
   <td>不利于找其他的元素，只能一个个遍历</td> 
   <td>1.有序集合保存的元素数量小于128个<br>2.有序集合保存的所有元素长度小于64字节</td> 
  </tr> 
  <tr> 
   <td>跳表</td> 
   <td>在链表的基础上增加了多级索引，通过多级索引位置的转跳，实现快速查找元素</td> 
   <td>可快速查找对应元素，用空间换实践，实践复杂度笑了</td> 
   <td></td> 
   <td>元素数量比较多 或者 元素比较长的字符串</td> 
  </tr> 
 </tbody> 
</table>

# 2. 跳表结构 #

之所以有跳表这个结构是为了解决平衡二叉树复杂问题

> hash可快速定位，但是不是有序  
> 若用二叉查找树，有序的话会退化为链表  
> 链表加平衡因子，变成平衡二叉树（可分为b树、b+树、红黑树等）

跳表和平衡二叉树的区别如下：

<table> 
 <thead> 
  <tr> 
   <th>共同点</th> 
   <th>差异</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>查找、插入、删除的时间复杂度都是o（logn）</td> 
   <td>跳表 查找区间元素比较快，但是 平衡二叉树 查找区间元素 一开始需要定位左端点，之后查找后续节点比较费时</td> 
  </tr> 
 </tbody> 
</table>

最后选用了跳表，是因为跳表实现起来容易，所以用它来实现有序集合

**基本的性质：**

1.  主要是单链表 + 索引的方式实现，以空间换时间的形式，提高查找速度
2.  底层主要由两个结构组成

![在这里插入图片描述][2e353a5bef6f4112b56906e8ce0c802a.png]

*  zskiplist：保存跳表信息（头尾节点、跳表层数最大的层数、长度）
 *  zkiplistnode：保存跳表节点信息（比如level层：每层都有两个属性，指针和跨度，跨度大距离远）

类似如下结构，原本是1到6的链表结构，专门找5这个数字的话，需要遍历5个节点  
如果每隔一个数字建立一个索引，具体如下：  
![在这里插入图片描述][b557807ca95c45b0af72d2a8ed7f913c.png]

通过一级索引来减少遍历节点的次数  
如果觉得一级索引比较慢，可以在一级索引的基础上在建立索引

当数据量比较大的时候，跳表查询、插入、删除的复杂度均为为 O（logn），本身的主要思想是二分法

# 3. 拓展思考 #

> 为什么zset使用跳表而不用红黑树或者二叉树？

Redis直接操作内存而不是磁盘，所以不需读取IO，速度比较快

*  跳表不是很占用内存（基本取决于节点数据），本身节点的数据参数会让内存密集度小于B+树
 *  跳表本身实现方式比其他结构都要简单（将相同级别的节点存储在同一个文件或者映射中，有利于解决缓存局部性问题）  
    而MYSQL使用B+树是为了减少IO以及支持范围查询

关于这个问题的讲解，结合MYSQL的底层结构讲解比较清晰。  
（对应的数据库最终使用了b+树，可看我这篇文章的推理：[Mysql底层原理详细剖析+常见面试题（全）][Mysql]）

[Redis]: https://blog.csdn.net/weixin_47872288/article/details/118410080
[Python_Redis]: https://blog.csdn.net/weixin_47872288/article/details/125383014
[Redis 1]: https://blog.csdn.net/weixin_47872288/article/details/121958141
[Redis_Amazon MemoryDB]: https://blog.csdn.net/weixin_47872288/article/details/125414495
[2e353a5bef6f4112b56906e8ce0c802a.png]: /images/20221119/76999406b00a486289aa9a603f836490.png
[b557807ca95c45b0af72d2a8ed7f913c.png]: /images/20221119/fd335eb904e94bee9a9ebf6ab03f7ede.png
[Mysql]: https://blog.csdn.net/weixin_47872288/article/details/122223717