42张图，带你真正搞懂redis数据类型的底层( 七 ) _redis

2、每一层都是一个有序的链表，排列顺序为由高层到底层，且至少包含两个链表节点，分别是前面的 head节点和后面的 nil节点；
3、最底层的链表包含了所有的元素；
4、如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；
5、链表中的每个节点都包含两个指针，一个指向同层的下一个链表节点，另一个指向下层的同一个链表节点；

文章插图

跳跃表节点定义如下：

typedef struct zskiplistNode {//层struct zskiplistLevel{//前进指针struct zskiplistNode *forward;//跨度unsigned int span;}level[];//后退指针struct zskiplistNode *backward;//分值double score;//成员对象robj *obj; } zskiplistNode多个跳跃表节点构成一个跳跃表：typedef struct zskiplist{//表头节点和表尾节点structz skiplistNode *header, *tail;//表中节点的数量unsigned long length;//表中层数最大的节点的层数int level; }zskiplist;

文章插图

各个功能“
①、搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。
②、插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k 后，则需要将新元素插入到从底层到k层。
③、删除：在各个层中找到包含指定值的节点
，然后将节点从链表中删除即可，如果删除以后
只剩下
头尾两个节点，则删除这一层。
”
整数集合用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。定义如下：

typedef struct intset{//编码方式uint32_t encoding;//集合包含的元素数量uint32_t length;//保存元素的数组int8_t contents[]; }intset;

整数集合的每个元素都是 contents 数组的一个数据项，它们按照从小到大的顺序排列，并且不包含任何重复项。
length属性记的是 contents数组的大小。需要注意的是虽然 contents 数组声明为 int8_t 类型，但是实际上contents数组并不保存任何 int8_t 类型的值，其真正类型有 encoding 来决定。
①、升级当我们新增的元素类型比原集合元素类型的长度要大时，需要对整数集合进行升级，才能将新元素放入整数集合中。具体步骤：
1、根据新元素类型，扩展整数集合底层数组的大小，并为新元素分配空间。
2、将底层数组现有的所有元素都转成与新元素相同类型的元素，并将转换后的元素放到正确的位置，放置过程中，维持整个元素顺序都是有序的。
3、将新元素添加到整数集合中是有序的呀！

升级能极大地节省内存。②、降级整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态
总结“
大多数情况下，Redis使用简单字符串SDS作为字符串的表示，相对于C语言字符串，SDS具有常数复杂度获取字符串长度，杜绝了缓存区的溢出，减少了修改字符串长度时所需的内存重分配次数，以及二进制安全能存储各种类型的文件，并且还兼容部分C函数。
”
通过为链表设置不同类型的特定函数，Redis链表可以保存各种不同类型的值，除了用作列表键，还在发布与订阅、慢查询、监视器等方面发挥作用（后面会介绍）。
Redis的字典底层使用哈希表实现，每个字典通常有两个哈希表，一个平时使用，另一个用于rehash时使用，使用链地址法解决哈希冲突。
跳跃表通常是有序集合的底层实现之一，表中的节点按照分值大小进行排序。
整数集合是集合键的底层实现之一，底层由数组构成，升级特性能尽可能的节省内存。
压缩列表是Redis为节省内存而开发的顺序型数据结构，经常作为列表键和哈希键的底层实现。

原文链接：
https://mp.weixin.qq.com/s?__biz=MzAwMDg2OTAxNg==&mid=2652049856&idx=1&sn=05d77ad89bb84bf55cea9e17e6192a04&utm_source=tuicool&utm_medium=referral