【Redis学习笔记（三）】之跳跃表与整数集合结构详解

忘是亡心i 2023-10-07 15:40 17阅读 0赞

#### 文章目录 ####

*   *  本文章由公号【开发小鸽】发布！欢迎关注！！！
     *  一． 跳跃表
     *   *  （一） 概述
         *  （二） 跳跃表的实现
         *   *  1. zskiplist
             *  2. zskiplistNode
     *  二． 整数集合
     *   *  （一） 概述
         *  （二） 实现
         *  （三） 升级
         *  （四） 升级的优势
         *   *  1. 提升灵活性
             *  2. 节约内存

### 本文章由公号【开发小鸽】发布！欢迎关注！！！ ###

**老规矩–妹妹镇楼：**

![20200721223424816.JPG][]

### 一． 跳跃表 ###

#### （一） 概述 ####

跳跃表是一种有序数据结构，通过在节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。支持平均O(logN)，最坏O(N)复杂度的节点查找，效率与平衡树差不多，由于事先更加简单，是平衡树的良性替代品。Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

#### （二） 跳跃表的实现 ####

Redis的跳跃表由zskiplistNode结构和zskiplist结构定义，zskiplistNode结构表示跳跃表节点，zskiplist结构用于保存跳跃表节点的相关信息。

##### 1. zskiplist #####

该结构包含以下属性：

header: 跳跃表的表头节点；

tail: 跳跃表的表尾节点；

level： 记录目前跳跃表内，层数最大的那个节点的层数，不包括表头节点；

length： 跳跃表的长度

##### 2. zskiplistNode #####

该结构包含以下属性：

level数组：跳跃表节点的各个层，每个层带有两个属性，一个是前进指针，，另一个是跨度，程序可以通过这些层来加快访问其他节点的速度，层的数量越多，速度越快。每次创建一个新的跳跃表节点时，随机生成一个介于1-32之间的值作为level数组的大小，即层高。

前进指针：用于访问位于表尾方向的其他节点  
跨度：记录了前进指针所指向节点和当前节点的距离，跨度用于计算排位的，在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来得到的结果就是目标节点在跳跃表中的排位。

后退指针：指向位于当前节点的前一个节点；

分值：各个节点的分支，按照分支从小到大排序；  
成员对象：各个节点保存了成员对象，成员对象是一个指针，指向一个字符串对象（SDS），在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值可以是相同的，分值相同的节点将按照成员对象在字典序中的大小进行排序。

### 二． 整数集合 ###

#### （一） 概述 ####

整数集合是集合键的底层实现之一，当一个集合中只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

#### （二） 实现 ####

整数集合是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16\_t, int32\_t, int64\_t的整数值，并且有去重操作。

结构如下：

typedef struct intset{
        
    	uint32_t encoding;
    	uint32_t length;
    	int8_t contents[];
    }intset;

contents数组中的每个元素就是集合中的每个整数，并按照值的大小升序排列，且没有重复项；

length属性记录了整数集合中包含的元素数量；

encoding属性决定了contents数组中存储的项的类型；

#### （三） 升级 ####

每当我们要将一个新元素添加到整数集合中，并且新元素的类型比整数集合中现有元素的类型都要长时，整数集合需要先进行升级，才能让新元素添加到整数集合中。步骤如下：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间；

2. 将底层数组现有的所有元素转变为与新元素相同的类型，并将转换后的元素放置到正确的位上，注意由于扩展了元素的大小，新元素的位置确定在最后一个，那么就从后往前重新分配位置，以保持有序性不变；

3. 将新元素添加到底层数组中；

由于有升级操作，因此向整数集合中添加新元素的时间复杂度为O(N)。注意，整数集合不支持降级操作，一旦升级了数组，就会保持升级后的状态了。

#### （四） 升级的优势 ####

##### 1. 提升灵活性 #####

由于C语言是静态类型语言，为了避免类型错误，我们不会将不同类型的值放在以同一个数据结构中，使用整数集合的升级可以自动适应新元素，不用担心出现类型错误。

##### 2. 节约内存 #####

升级只会在需要的时候，而不是大包大揽地直接用最大的类型，尽量地节省了内存。

[20200721223424816.JPG]: https://img-blog.csdnimg.cn/20200721223424816.JPG

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 redis设计与实现之跳跃表

1. 跳跃表简介 1. 跳跃表（skiplist）是一个有序结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的 2. 跳跃表的平均查询时间

小灰灰/ 2024年02月19日 17:33/ 0 赞/ 171 阅读

相关【Redis学习笔记（三）】之跳跃表与整数集合结构详解

文章目录本文章由公号【开发小鸽】发布！欢迎关注！！！一．跳跃表（一）概述（二）跳跃表的实

忘是亡心i/ 2023年10月07日 15:40/ 0 赞/ 18 阅读

相关 redis底层数据结构之整数集合

1. 问题当我们使用redis的set结构存储一些数量不多的数字时，底层是什么数据结构？ 2. 数据结构 > typedef struct intset{

淩亂°似流年/ 2023年06月26日 05:41/ 0 赞/ 127 阅读

相关 Redis设计与实现之跳跃表

跳跃表简介我们先抛开redis，单独了解下跳越表 > skiplist本质上也是一种查找结构，用于解决算法中的查找问题（Searching），即根据给定的key，快速

妖狐艹你老母/ 2023年03月01日 10:50/ 0 赞/ 114 阅读

相关 Redis数据结构之整数集合

一：整数集合的实现整数集合intset是集合键的底层实现方式之一，当一个集合只包含整数而且数量不是很多的时候，Redis就会整合集合作为集合键的底层实现方式。

水深无声/ 2022年11月06日 12:54/ 0 赞/ 296 阅读

相关 Redis数据结构之跳跃表

一：Redis数据结构之跳跃表跳跃表是一个有序的数据结构，它可以通过跳跃表节点维持的多个指向其他节点的指针，从而达到快速访问的目的，是一种可以作为代替平衡树的数据结构。

客官°小女子只卖身不卖艺/ 2022年11月06日 09:54/ 0 赞/ 236 阅读

相关 redis源码学习之跳跃表

跳跃表跳跃表对于我来说是一个比较陌生的数据结构，因此花了一上午的时间先看了一蛤MIT的公开课。[网易云课堂——MIT跳跃表][MIT] 什么是跳跃表，有一个很简单的例

清疚/ 2022年07月11日 11:19/ 0 赞/ 356 阅读

相关 Redis之动态字符串链表跳跃表整数集

分析结构体 + 重要API = 理清楚了架构。 Redis是键值，内存缓冲系统。Memcached内部仅仅支持字符串，直接用一个hash表管理。但是Redis支持数据类型更

深碍√TFBOYSˉ_/ 2022年05月23日 08:05/ 0 赞/ 173 阅读

相关 Redis数据结构之跳跃表

在Redis5大数据结构中，跳跃表（skiplist）是比较难理解的，同时却也是使用比较少的数据结构，只在实现有序集合zset和集群节点内部槽位和键的对饮关系数据结构中用到了。

雨点打透心脏的1/2处/ 2022年05月13日 12:44/ 0 赞/ 291 阅读

相关 Redis数据结构(四) —跳跃表

跳跃表跳跃表(skiplist)是一种有序的数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的跳跃表支持平均O(logN), 最

古城微笑少年丶/ 2022年01月30日 11:35/ 0 赞/ 350 阅读