Redis5.0的基本数据类型的底层原理

朱雀 2022-12-21 06:08 202阅读 0赞

## Redis5.0的基本数据类型的底层原理 ##

#### 简单动态字符串（Simple Dynamic Strings, SDS ####

简单动态字符串（Simple Dynamic Strings, SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数，且在此基础上保证了二进制安全  
**注意**  
什么是二进制安全？通俗地讲，C语言中，用“\\0”表示字符串的结束，如果字符串中本身就有“\\0”字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。

struct sdshdr{ 
     //记录buf数据中已使用字节的数量
     //等于SDS所保存字符串的长度 
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组,用于保存字符串
    char buf[];
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center]  
1）有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。  
2）内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。  
3）由于有长度统计变量len的存在，读写字符串时不依赖“\\0”终止符，保证了二进制安全  
**柔性数组**存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快（因为不需要额外通过指针找到字符串的位置）；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 1]  
1）len：表示buf中已占用字节数。  
2）alloc：表示buf中已分配字节数，不同于free，记录的是为buf分配的总长度。  
3）flags：标识当前结构体的类型，低3位用作标识位，高5位预留。  
4）buf：柔性数组，真正存储字符串的数据空间。

Redis的链表实现的特性可以总结如下：  
❑双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）。  
❑无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。  
❑带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。  
❑带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）。  
❑多态：链表节点使用void\*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 2]

#### 跳跃表 ####

简介：有序集合在生活中较常见，如根据成绩对学生进行排名、根据得分对游戏玩家进行排名等。对于有序集合的底层实现，我们可以使用数组、链表、平衡树等结构。数组不便于元素的插入和删除；链表的查询效率低，需要遍历所有元素；平衡树或者红黑树等结构虽然效率高但实现复杂。Redis采用了一种新型的数据结构——跳跃表。跳跃表的效率堪比红黑树，然而其实现却远比红黑树简单。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 3]  
1）从第2层开始，1节点比51节点小，向后比较。  
2）21节点比51节点小，继续向后比较。第2层21节点的next指针指向NULL，所以从21节点开始需要下降一层到第1层继续向后比较。  
3）第1层中，21节点的next节点为41节点，41节点比51节点小，继续向后比较。第1层41节点的next节点为61节点，比要查找的51节点大，所以从41节点开始下降一层到第0层继续向后比较。  
4）在第0层，51节点为要查询的节点，节点被找到。  
采用图3-2所示的数据结构后，总共查找4次就可以找到51节点，比有序链表少2次。当数据量大时，优势会更明显。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 4]

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，而zskiplist结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 5]  
图5-1展示了一个跳跃表示例，位于图片最左边的是zskiplist结构，该结构包含以下属性：  
❑header：指向跳跃表的表头节点。  
❑tail：指向跳跃表的表尾节点。❑level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。  
❑length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 6]

header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为O（1）。通过使用length属性来记录节点的数量，程序可以在O（1）复杂度内返回跳跃表的长度。level属性则用于在O（1）复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。  
压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现  
压缩列表是一种为节约内存而开发的顺序型数据结构。❑压缩列表被用作列表键和哈希键的底层实现之一。❑压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。❑添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/ec6b0270108440b68e930111b8e2402c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/0692609218024ae4973082a0169ca840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201115115552184.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201118100635450.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201118100730929.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2020111514523196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201115145354780.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201120144453690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0,size_16,color_FFFFFF,t_70#pic_center