redis的几种数据结构

 通过分析底层的数据结构，学习如何根据场景选型和设计

 1，简单动态字符串

    redis使用的字符串SDS有别于C语言中的字符串

   a, 结构

 

    free字段为已分配但未使用的空间

    len为已使用的空间（不计入'\0'）

    buf为char数组

    b, 与C字符串区别

        redis的字符环结构可以理解为将C字符串封装了一层，通过加入的属性字段降低字符串操作的复杂度，提高安全性。

        通过len属性可以在常数复杂度获取字符串的长度，仅通过len属性可直接获取长度，而C语言字符串复杂度需要遍历，长度为O（N）。

        二进制安全的。C字符串是ASCII编码的，以'\0'来判断字符串是否结束，如果数据中包含'\0'字符便会将数据截断，当做两个字符串，因此仅限于保存文本数据。redis字符串通过len属性来获取数据而不是通过遍历寻找结束标志，因此可以存储任意内容的二进制数据。

        兼容C字符串的操作。默认在字符串最后加'\0‘，使用C库字符串的部分操作。

        避免缓冲区溢出。其实原理就是根据redis字符串的特点重写了C可能造成内存溢出的函数，如strcat拼接字符串函数，C语言中需人为保证目标字符串的空间足够大，否会造成溢出，而redis字符串通过free属性来自动判断是否可容纳源字符串，否则会扩展自身内存再拼接。

        减少内存分配次数。空间和效率的问题，redis采用的是牺牲空间来换取效率的提升，避免多次的申请或释放内存。redis是kv型数据库，要求速度快，数据也多为频繁修改，因此牺牲一部分空间是可取的。它提供了两种策略，空间预分配和惰性释放。预分配指的是一个字符串修改后会同时分配一定大小的空间给free预留，避免再次修改分配内存。惰性释放是字符串缩短后不是放空间而是给free记录，避免释放空间。

    预分配和惰性释放在memcache中也使用了，不过它是从内存管理的角度出发的。通过在初始化时对整个内存进行预分配，减少动态申请内存的操作带来的消耗，使用的内存都是连续的，避免了内存碎片，内存也不会回收而是通过内个slab的slot指针数组来保存。关于memcache的内存管理的机制具体见这里

    c, 场景

        该类型是字符串对象的一种实现方式，并用于AOF缓冲区和客户端输入缓冲区。

 

2，链表

    redis使用的联表示标准的双端无环链表

    a, 结构

        其中，head和tail表示链表的表头和表尾节点，len表示链表中节点的数目，dup、free、match分别为复制、释放和对比函数。

    b, 场景

        链表结构的特点是可以快速的在表头和表尾插入和删除元素，但查找复杂度高，是列表的底层实现之一，也因此列表没有提供判断某一元素是否在列表中的借口，因为在链表中查找复杂度高。

 

3，字典

    redis的字典使用哈希表作为底层实现。

    a, 结构

        上图为字典结构图

        dict结构中，type表示是dicttype类型的指针，表示操作特定类型的键值对的函数，privdata是传给特定函数的可选参数。ht是包含两个哈希表的数组，ht[0]表示正常存放数据的hash表，而ht[1]用于rehash，rehashidx是记录了rehash的进度，正常情况下为-1。

        dictht是哈希表，table表示哈希表数组，指针数组，size表示哈希表的大小，used表示已有节点的数目，used/size为负载因子，决定何时进行rehash。sizemask用于计算索引值。

        每个哈希表元素是dictentry结构，key为键，value可以是一个指针或是一个整数。，next为指向下一个的指针。是传统的hash表。

    b, rehash

        redis使用murmurhash算法计算hash值，能有很好的随机分布性，速度也很快。

        当负载因子大于3/2时进行扩容操作，扩容大小为第一个大于ht[0].used*2的2^n，当负载因子小于0.1进行缩容，为第一个大于ht[0].used的2^n。

        redis采用渐进式rehash，将rehash操作分摊到每次增删改查，具体过程见这里

    c, 场景

        字典是数据库和哈希对象的底层实现，数据库中dict存放所有kv，v可能是各种对象，而expire存放有过期时间的k和过期时间。用作hash底层时，k和v都是字符串对象。

4，跳跃表

    跳跃表是一种可以快速访问节点的数据结构，性能接近于平衡术，且实现简单。

    a, 结构

        跳跃链表是一种随机化数据结构，基于并联的链表。跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表。所有操作都以对数随机化的时间进行。

        header和tail指向表头和表尾，level表示最大层级，length表示节点数目（不包括首节点）

        每个节点都包含一个后退指针，用于从尾部遍历，路径唯一。obj为一个对象，score为对应的分值。level是大小随机出来的层级数组，每个层级包含一个前进指针和距离指向节点的跨度。跨度用于计算rank，跨度之和为rank。具体算法这里不介绍，具体见这里

    b, 场景

        跳跃表是有序集合的底层实现之一，跳跃表将指向有序集的 score 值和 member 域的指针作为元素， 并以 score 值为索引， 对有序集元素进行排序。  

        插入节点的流程：从表头指定的当前最大深度开始，逐层遍历找到节点插入的位置，rank数组记录的是沿途跨国的节点的跨度，即本层上一节点之前的跨度和，update数组记录的是在该层插入节点的位置，即上一个节点，之后取随机的层数初始化节点，若该层数大于当前的总层数则将层数更新对于这些大于之前的层数小于新层数之间的更新rank为0且update为头结点，之后从0开始到新节点的最大层逐层遍历将节点插入到update记录的节点之后，并更新span

        redis根据自己的需求对跳跃表做了更改：

1. score 值可重复。
2. 对比一个元素需要同时检查它的 score 和 memeber 。
3. 每个节点带有高度为 1 层的后退指针，用于从表尾方向向表头方向迭代，当执行ZREVRANGE或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

5，整数集合

    redis的整数集合实质上是动态的数组。reids的整数集合是可以根据整数的值，自动选择用什么长度来存储。

    a, 结构 

        encoing标会编码方式，8/16/32/64位，length表示集合元素的数量，contents表示数据，元素由小到大排列。 

    b, 升级

        当加入的数大于encoding对应的最大长度时，自动进行升级操作。流程是：首先扩展数组空间的大小。将原数组中的原书进行类型扩展并存储，最后将新插入的数放入对应位置。整数集合不做降级操作。

    c, 场景

        整数集合是redis集合对象的底层实现之一。当键数量小于512并且键值为整数时集合使用整数集合作为底层存储，节约内存。如何保证不重复？（待解决）。

 

6，压缩列表

redis使用压缩列表来存储小整数值或长度比较短的字符串

    压缩列表是为了节省内存开发的，是一系列特殊编码的连续内存块组成的顺序型数据结构。

    a, 结构

        zlbytes记录整个列表所占的内存数

        zltail记录距离尾节点的距离

        zllen记录节点数目

        entry是每个节点

        zlend列表结束标志

        每个节点的组成，previous_entry_length是前一节点的长度，可用于从尾节点向前遍历，encoding记录content的数据类型和长度，content为节点的值。

    b, 连锁更新

        当插入或者删除元素时，会导致previous_entry_length的长度发生变化，如有1子节点为5字节，如果原先本节点的总大小处于250至253之间，会导致笑一个节点的previous..的长度发生变化，可能引起连锁更新的情况。需要不停的重复分配空间来存放增大的大小。

        但redis中假定的是处于临界大小的数据很多并且连续这种情况几率很低，同事假定被更新的节点数目少。

    c, 场景

        redis使用压缩列表来作为列表键和哈希键的底层实现之一，存储小整数值或长度比较短的字符串时使用，previous_entry_length的存在使其可以像链表一样遍历。实现hash时顺序添加相邻接的节点为k和v。