17、数据结构篇

1）SDS 简单动态字符串：

其实就是将字符串抽象成一个结构，用数组来存储各个字符，记录下字符串长度，空闲空间等信息，这样的结构就有利于后面数组的自动扩容。
优点：
① 可以直接获取长度，在C中获取长度需要遍历整个字符串，这里由于有属性记录，O(1)即可；
② 可以避免缓冲区溢出，因为字符串是动态变长的，不会存在越界溢出的危险；
③ 二进制安全，SDS的API均将输入信息作为二进制处理，可以保存信息原貌；
④ 减少修改字符串时的内存重分配，对于字符串的扩长采用预分配策略，如果修改后小于1MB则分配跟字符串长度一致的空闲空间，如果修改后大于1MB则分配1MB的空闲空间；对于字符串的缩短操作采用惰性释放的策略，不马上释放空间；
⑤ 兼容C的操作，提高函数复用性，减少代码冗余；

2）ZipList 压缩列表

看名字也知道了，它的诞生就是为了尽可能地压缩使用的内存空间，在双向链表中对于每一个节点都需要建立前后指针，在节点数量多的情况下，这个内存的消耗也是相当大的。压缩列表实质就是将节点的前后节点指针都去掉，节点之间依次排放在一块连续空间中，这样就节省了一定的空间。
为了进一步节省空间，ziplist 的节点也是采用可变长的形式，结构中的 prevrawlen 代表的是前一个数据的长度，默认需要一字节存储，如果前一个数据大于等于254字节，那么该属性需要使用5字节，这就会导致空间不足，也就引发了内存的重分配，后续的节点也会跟着连锁更新。因此压缩列表适用于少量元素的存储，否则重分配一次的消耗也是很大的。

3）QuickList 快速列表：

快速列表更像是一个双向链表，但它同样想避免每个数据节点都带头尾指针且容易造成内存碎片化的问题，因此quicklist中的每个节点都是一个ziplist，ziplist其中会包含一个或多个元素顺序排列，这样在理想情况下就可以完美避免上述的问题了，但这里要警惕quicklist以及ziplist退化成链表的情况，也就是要根据业务实际去调整快表中压缩列表的个数。并且快表一般用作list的实现，头尾节点的访问频率相对较高，因此快表中对非头尾的节点进行LZF无损压缩。

4）Dict 字典：

字典用于存储key-value值，在Redis中主要用于数据库K-V存储、hash结构实现之一、zset存储键值对 这三个用途。字典结构的实现主要有两种，一种是平衡树，一种是哈希表。Redis中的字典底层使用哈希表实现，跟Java中的Map等结构一样有哈希冲突，出现哈希冲突采用的是拉链法，因此一个哈希表中的元素都会有一个next指针。
同时会有设定的负载因子(当前已使用大小/设定大小)，如果超过该值会将哈希桶扩大，接着进行重新散列，因此字典结构中会同时包含两个哈希表，平时只访问哈希表1。rehash的过程即是将哈希表1的元素逐个重新散列并搬运到哈希表2，搬运完毕将原来两个哈希表的引用交换，Redis是单线程执行事件请求的，这意味着如果一次性将哈希表进行rehash会造成长时间的阻塞，因此Redis中采用的是渐进式的rehash，也就是将O(N)的复杂度均摊到每个操作中，这样可以避免单次阻塞时间较长。
增删改查跟Map类似，需要注意的是增加时会判断key是否存在，如果存在则调用更新方法，如果不存在则插入链表头。如果当前处于rehash阶段，则这四个方法的调用都会引发rehash推进，并且查询key时会在两个哈希表中进行查询。
rehash会发生在扩容和收缩操作中，扩容时会扩大到接近（哈希表1已使用大小*2）的一个2的次方幂；收缩会缩到接近（哈希表1实际使用大小）的一个2的次方。
扩容发生的时机是：①服务器没有进行RDB/AOF备份并且负载因子大于1时；②服务器正在进行RDB/AOF备份并且负载因子大于5时；③(针对全局哈希表)主线程会默认每间隔 100ms 执行一次迁移操作，每次以 100 个桶为基本单位迁移数据，并限制单次操作耗时超 1ms 就结束本次任务；
收缩的发生时机是负载因子小于0.1时。

5）SkipList 跳表：

首先对于单向链表/双向链表来说，即是是有序的链表，寻找一个元素的时间复杂度也为O(N)，这是因为我们只能顺序遍历去寻找元素。跳表实际上就是为了改进链表的查找效率，让其达到近似二分查找的效率。在底层之上有多个层级起索引作用，值得一提的是，在经典跳表中，上层节点的分布基本是每隔两个设置一个节点，这就有点类似二分查找。当寻找一个元素时会先从顶层开始寻找，这里会筛选掉一半的元素，接着下一层又会筛选掉一半的元素，以此类推，因此最后跳表的查找效率是O(logN)。跳表实际上就是链表加索引的结构，这是典型的空间换时间的设计。

虽然跳表可以将查询的时间复杂度降下来，但是新增或者删除都会改变这个原始结构，也就带来额外的维护成本，因此Redis中并不使用原始的跳表，而是进行了改进，不要求层级之间有严格的比例关系，而是每次都随机一个层数插入，当然这里的随机不是真的无规律插入，具体要看设置的p和MaxLevel的值，其可以尽可能保证节点不严重分化。
此外在层级关系中还维护一个span的属性，用于记录从同一层上一节点到达该节点所走过的步数【映射到底层的元素步数】，这个属性值可以用来计算排名信息。对于相同的score值，会按照value的字典序进行先后排列。
为什么Redis不选红黑树、哈希表这些，而是选择跳表？
① 范围查询支持：跳表、红黑树支持哈希查询，哈希表不支持范围查询；
② 范围查询性能：红黑树在进行范围查询时有时候需要重新进行遍历以确定比当前值小的最大值，而由于跳表在底层使用了双向链表，范围查询较易实现；
③ 状态调整：如果插入操作导致红黑树平衡状态被破坏了，需要进行一系列的旋转操作以确保维持平衡，而跳表由于每次都是随机插入层数，并不需要去维护其结构；
④ 内存占用：如果按照p是1/4来算，跳表中每个节点包含大概1.3个指针，而红黑树每个节点包含2个指针，这里来看跳表优一些；但整体上看，其实跳表多层的节点也会占用一些空间，但只是需要存储指针而已；
⑤ 实现复杂性：跳表实现起来较容易，红黑树实现较复杂。

6）跳表的其他知识点[From Kaito]

1、ZSet 当数据比较少时，采用 ziplist 存储，每个 member/score 元素紧凑排列，节省内存
2、当数据超过阈值（zset-max-ziplist-entries、zset-max-ziplist-value）后，转为 hashtable + skiplist 存储，降低查询的时间复杂度
3、hashtable 存储 member->score 的关系，所以 ZSCORE 的时间复杂度为 O(1)
4、skiplist 是一个「有序链表 + 多层索引」的结构，把查询元素的复杂度降到了 O(logN)，服务于 ZRANGE/ZREVRANGE 这类命令
5、skiplist 的多层索引，采用「随机」的方式来构建，也就是说每次添加一个元素进来，要不要对这个元素建立「多层索引」？建立「几层索引」？都要通过「随机数」的方式来决定
6、每次随机一个 0-1 之间的数，如果这个数小于 0.25（25% 概率），那就给这个元素加一层指针，持续随机直到大于 0.25 结束，最终确定这个元素的层数（层数越高，概率越低，且限制最多 64 层，详见 t_zset.c 的 zslRandomLevel 函数）
7、这个预设「概率」决定了一个跳表的内存占用和查询复杂度：概率设置越低，层数越少，元素指针越少，内存占用也就越少，但查询复杂会变高，反之亦然。这也是 skiplist 的一大特点，可通过控制概率，进而控制内存和查询效率
8、skiplist 新插入一个节点，只需修改这一层前后节点的指针，不影响其它节点的层数，降低了操作复杂度（相比平衡二叉树的再平衡，skiplist 插入性能更优）
关于 Redis 的 ZSet 为什么用 skiplist 而不用平衡二叉树实现的问题，原因是：
skiplist 更省内存：25% 概率的随机层数，可通过公式计算出 skiplist 平均每个节点的指针数是 1.33 个，平衡二叉树每个节点指针是 2 个（左右子树）
skiplist 遍历更友好：skiplist 找到大于目标元素后，向后遍历链表即可，平衡树需要通过中序遍历方式来完成，实现也略复杂
skiplist 更易实现和维护：扩展 skiplist 只需要改少量代码即可完成，平衡树维护起来较复杂