【Redis系列5】Redis(有序)集合对象之intset(整数集合)和skiplist(跳跃表)实现原理分析
Redis集合对象之intset和skiplist实现原理分析
前言
上一篇我们分析了列表对象的底层存储结构linkedlist，ziplist和quicklist的实现原理，并将这三种数据结构进行了分析对比。这一篇我们继续分析Redis中5种常用数据类型的第3种基本数据类型哈希对象的底层存储结构。
集合对象
集合对象的底层数据结构有两种：intset和hashtable。内部通过编码来进行区分：
| 编码属性 | 描述 | object encoding命令返回值 |
|---|---|---|
| OBJ_ENCODING_INTSET | 使用整数集合实现的集合对象 | intset |
| OBJ_ENCODING_HT | 使用字典实现的集合对象 | hashtable |
intset编码
intset(整数集合)可以保存类型为int16_t，int32_t，int64_t的整数值，并且保证集合中没有重复元素。
intset数据结构定义如下(源码inset.h内)：
typedef struct intset {
uint32_t encoding;//编码方式
uint32_t length;//当前集合中的元素数量
int8_t contents[];//集合中具体的元素
} intset;
下图就是一个intset的集合对象简图：
encoding
encoding记录了当前集合的编码方式，主要有三种：
-
INTSET_ENC_INT16
此时contents[]内的每个元素都是一个int16_t类型的整数值，范围是：-32768 ~ 32767(-215 ~ 215-1) -
INTSET_ENC_INT32
此时contents[]内的每个元素都是一个int32_t类型的整数值，范围是：-2147483648 ~ 2147483647(-231 ~ 231-1) -
INTSET_ENC_INT64
此时contents[]内的每个元素都是一个int64_t类型的整数值，范围是：-9223372036854775808 ~ 9223372036854775807(-263 ~ 263-1)
contents[]
contents[]虽然结构的定义上写的是int8_t类型，但是实际存储类型是由上面的encoding来决定的。
整数集合的升级
假如一开始整数集合中的元素都是16位的，采用了int16_t类型来存储，此时需要再存储一个32位的整数，那么就需要对原先的整数集合进行升级，升级之后才能将32位的整数放入整数集合内。
升级主要有4个步骤：
- 1、根据新添加元素的类型来扩展底层数组空间的大小，按照升级后现有元素的位数来分配新的空间。
- 2、将现有的元素进行类型转换，并将转换类型后的元素从后到前逐个重新放回到数组内。
- 3、将新元素放到数组的头部或者尾部（因为触发升级的条件就是当前数组的整数类型无法存储新元素，所以新元素要么比现有元素都大，要么就比现有元素都小）。
- 4、将
encoding属性修改为最新的编码，并且同步修改length属性。
PS：整数集合一旦升级，将会保持编码，无法降级。
升级举例
1、假如我们有一个集合存储的encoding是int16_t，内部存储了3个元素：
2、这时候需要插入一个整数50000，发现存储不下去，而50000是一个int32_t类型整数，所以需要申请新空间，申请空间大小为：4 * 32 - 48=80。
3、现在新的数组内要放置4个元素，原来的数组排在第3，所以需要将升级后的3移动到64-95位。
4、继续将升级后的2移动到32-63位
5、继续将升级后的1移动到0-31位：
6、最后将50000放到96-127位：
7、修改encoding和length属性，完成升级。
hashtable编码
hashtable结构在前面讲述哈希对象的时候进行过详细分析，想详细了解的可以点击这里。
intset和hashtable编码转换
当一个集合满足以下两个条件时，Redis会选择使用intset编码：
- 1、集合对象保存的所有元素都是整数值。
- 2、集合对象保存的元素数量小于等于512个(这个阈值可以通过配置文件
set-max-intset-entries来控制)。
一旦集合中的元素不满足上面两个条件，则会选择使用hashtable编码。
有序集合对象
有序集合对象的底层数据结构有两种：skiplist和ziplist。内部同样是通过编码来进行区分：
| 编码属性 | 描述 | object encoding命令返回值 |
|---|---|---|
| OBJ_ENCODING_SKIPLIST | 使用跳跃表实现的有序集合对象 | skiplist |
| OBJ_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象 | ziplist |
skiplist编码
skiplist即跳跃表，有时候也简称为跳表，使用skiplist编码的有序集合对象使用了zset结构来作为底层实现，而zset中同时包含了一个字典和一个跳跃表。
跳跃表
跳跃表是一种有序的数据结构，其主要特点是通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
大部分情况下，跳跃表的效率可以等同于平衡树，但是跳跃表的实现却远远比平衡树的实现简单，所以Redis选择了使用跳跃表。
下图是一个普通的有序链表，我们如果要找17，只能从头开始遍历到尾(链表中元素不支持随机访问，所以不能用二分查找，而数组中可以通过下标随机访问，所以二分查找一般适用于有序数组)，时间复杂度是O(n)。
那么假如我们可以直接跳到链表的中间，那就可以节省很多资源了，这就是跳表的原理，如下图所示就是一个跳表的数据结构示例：
上图中level1，level2，level3就是跳表的层级，每一个level层级都有一个指向下一个相同level层级元素的指针，比如上图我们遍历寻找元素35的时候就有三种方案：
- 第1种就是执行level1层级的指针，需要遍历7次才能找到元素35。
- 第2种就是执行level2层级的指针，只需要遍历5次就能找到元素35。
- 第3种就是执行level3层级的元素，这时候只需要遍历3次就能找到元素35了，大大提升了效率。
skiplist的存储结构
跳跃表中的每个节点是一个zskiplistNode节点(源码server.h内)：
typedef struct zskiplistNode {
sds ele;//元素
double score;//分值
struct zskiplistNode *backward;//后退指针
struct zskiplistLevel {//层
struct zskiplistNode *forward;//前进指针
unsigned long span;//当前节点到下一个节点的跨度(跨越的节点数)
} level[];
} zskiplistNode;
- level(层)
level即跳跃表中的层，其是一个数组，也就是说一个节点的元素可以拥有多个层，即多个指向其他节点的指针，程序可以通过不同层级的指针来选择最快捷的路径提升访问速度。
level是在每次创建新节点的时候根据幂次定律（power law）随机生成的一个介于1~32之间的数字。
- forward(前进指针)
每个层都会有一个指向链表尾部方向元素的指针，遍历元素的时候需要使用到前进指针。
- span(跨度)
跨度记录了两个节点之间的距离,需要注意的是，如果指向了NULL的话，则跨度为0
- backward(后退指针)
和前进指针不一样的是后退指针只有一个，所以每次只能后退至前一个节点。
- ele(元素)
跳跃表中元素是一个sds对象(早起版本使用的是robj对象)，元素必须唯一不能重复
- score(分值)
节点的分值是一个double类型的浮点数，跳跃表中会将节点按照分值按照从小到大的顺序排列，不同节点的分值可以重复。
上面介绍的只是跳跃表中的一个节点，多个zskiplistNode节点组成了一个zskiplist对象：
typedef struct zskiplist {
struct zskiplistNode *header, *tail;//跳跃表的头节点和尾结点指针
unsigned long length;//跳跃表的节点数
int level;//所有节点中最大的层数
} zskiplist;
到这里你可能以为有序集合就是用这个zskiplist来实现的，然而实际上Redis并没有直接使用zskiplist来实现，而是用zset对象再次进行了一层包装。
typedef struct zset {
dict *dict;//字典对象
zskiplist *zsl;//跳跃表对象
} zset;
所以最终，一个有序集合如果使用了skiplist编码，其数据结构如下图所示：
上图中上面的字典中的key就是对应了有序集合中的元素(memer)，value就对应了分值(score)。
下图中的跳跃表整数1,8,9,12也是对应了元素(memer)，最后一排的double型数字就是分值(score)。
也就是说同一份数据在字典和跳跃表中分别存储了一份，Redis为什么要这么做呢？
为什么同时选择使用字典和跳跃表
有序集合直接使用跳跃表或者单独使用字典完全可以独自实现，但是我们想一下，如果单独使用跳跃表来实现，那么虽然可以使用跨度大的指针去遍历元素来找到我们需要的数据，但是其复杂度仍然达到了O(logN)，而字典中获取一个元素的复杂度是O(1)，而如果单独使用字典虽然获取元素很快，但是字典是无序的，所以如果要范围查找就需要对其进行排序，这又是一个耗时的操作，所以Redis综合了两种数据结构来最大程度的提升性能。
ziplist编码
压缩列表在列表对象和哈希对象都有使用到，想详细了解的可以点击这里。
ziplist和skiplist编码转换
当有序集合对象同时满足以下两个条件时，会使用ziplist编码进行存储：
- 1、有序集合对象中保存的元素个数小于128个（可以通过配置
zset-max-ziplist-entries修改）。 - 2、有序集合对象中保存的所有元素的总长度小于64字节（可以通过配置
zset-max-ziplist-value修改）。
总结
本文主要分析了集合对象和有序集合对象的底层存储结构intset和skiplist的实现原理，并且重点分析了有序集合如何实现排序以及为何同时使用两种数据结构进行存储的原因。