主题
《面渣逆袭》Redis 篇 · 第 7/8 章。原版 PDF（下载 / 打印）
这一部分就比较深了，如果不是简历上写了精通Redis ，应该不会怎么问。
46.说说Redis底层数据结构？
Redis有动态字符串(sds)、链表(list)、字典(ht)、跳跃表(skiplist)、整数集合(intset)、压缩列表**(ziplist)**等底层数据结构。
Redis 并没有使用这些数据结构来直接实现键值对数据库，而是基于这些数据结构创建了一个对象系统，来表示所有的k ey-value 。
我们常用的数据类型和编码对应的映射关系：
简单看一下底层数据结构，如果对数据结构掌握不错的话，理解这些结构应该不是特别难：
- 字符串：redis 没有直接使用C 语言传统的字符串表示，而是自己实现的叫做简单动态字符串SDS
的抽象类型。
C 语言的字符串不记录自身的⻓度信息，而SDS 则保存了⻓度信息，这样将获取字符串⻓度的时间由
O(N) 降低到了O (1) ，同时可以避免缓冲区溢出和减少修改字符串⻓度时所需的内存重分配次数。
- 链表linkedlist：redis 链表是一个双向无环链表结构，很多发布订阅、慢查询、监视器功能都是
使用到了链表来实现，每个链表的节点由一个listNode 结构来表示，每个节点都有指向前置节点和后置节点的指针，同时表头节点的前置和后置节点都指向NULL 。
- 字典dict：用于保存键值对的抽象数据结构。Redis 使用hash 表作为底层实现，一个哈希表里可
以有多个哈希表节点，而每个哈希表节点就保存了字典里中的一个键值对。
每个字典带有两个hash 表，供平时使用和rehash 时使用，hash 表使用链地址法来解决键冲突，被分配到同一个索引位置的多个键值对会形成一个单向链表，在对hash 表进行扩容或者缩容的时候，为了服务的可用性，rehash 的过程不是一次性完成的，而是渐进式的。
- 跳跃表skiplist：跳跃表是有序集合的底层实现之一，Redis 中在实现有序集合键和集群节点的内
部结构中都是用到了跳跃表。Redis 跳跃表由zskiplist 和zskiplistNode 组成，zskiplist 用于保存跳跃表信息（表头、表尾节点、⻓度等），zskiplistNode 用于表示表跳跃节点，每个跳跃表节点的层高都是1 -32 的随机数，在同一个跳跃表中，多个节点可以包含相同的分值，但是每个节点的成员对象必须是唯一的，节点按照分值大小排序，如果分值相同，则按照成员对象的大小排序。
- 整数集合intset：用于保存整数值的集合抽象数据结构，不会出现重复元素，底层实现为数组。
- 压缩列表ziplist：压缩列表是为节约内存而开发的顺序性数据结构，它可以包含任意多个节点，
每个节点可以保存一个字节数组或者整数值。
47.Redis 的 SDS 和 C 中字符串相比有什么优势？
C 语言使用了一个长度为N+1的字符数组来表示长度为N的字符串，并且字符数组最后一个元素总是**\0**，这种简单的字符串表示方式 不符合 Redis 对字符串在安全性、效率以及功能方面的要求。
C 语言的字符串可能有什么问题？
这样简单的数据结构可能会造成以下一些问题：
获取字符串长度复杂度高：因为 C 不保存数组的长度，每次都需要遍历一遍整个数组，时间复杂
度为O(n)；不能杜绝缓冲区溢出/ 内存泄漏的问题 :C 字符串不记录自身长度带来的另外一个问题是容易造成缓存区溢出（bufferoverflow ），例如在字符串拼接的时候，新的
C 字符串只能保存文本数据→ 因为 C 语言中的字符串必须符合某种编码（比如 ASCII ），例如中间出现的**'\0'**可能会被判定为提前结束的字符串而识别不了；
Redis 如何解决？优势？
简单来说一下 Redis 如何解决的：
多增加 len 表示当前字符串的长度：这样就可以直接获取长度了，复杂度 O(1) ；
自动扩展空间：当 SDS 需要对字符串进行修改时，首先借助于len和alloc检查空间是否满
足修改所需的要求，如果空间不够的话，SDS 会自动扩展空间，避免了像 C 字符串操作中的溢出情况；
- 有效降低内存分配次数：C 字符串在涉及增加或者清除操作时会改变底层数组的大小造成重新分
配，SDS 使用了空间预分配和惰性空间释放机制，简单理解就是每次在扩展时是成倍的多分配的，在缩容是也是先留着并不正式归还给 OS ；
- 二进制安全：C 语言字符串只能保存ascii码，对于图片、音频等信息无法保存，SDS 是二进
制安全的，写入什么读取就是什么，不做任何过滤和限制；
48.字典是如何实现的？Rehash 了解吗？
字典是 Redis 服务器中出现最为频繁的复合型数据结构。除了hash结构的数据会用到字典外，整个
Redis 数据库的所有key和value也组成了一个全局字典，还有带过期时间的key也是一个字
典。(存储在 RedisDb 数据结构中)字典结构是什么样的呢？
Redis中的字典相当于 Java 中的HashMap，内部实现也差不多类似，采用哈希与运算计算下标位置；通过**" 数组 + 链表"的链地址法**来解决哈希冲突，同时这样的结构也吸收了两种不同数据结构的优点。
字典是怎么扩容的？
字典结构内部包含两个 hashtable，通常情况下只有一个哈希表 ht[0] 有值，在扩容的时候，把h t[0]里的值rehash 到h t[1] ，然后进行渐进式re hash— — 所谓渐进式rehash ，指的是这个rehash 的动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。
待搬迁结束后，h [1] 就取代h [0] 存储字典的元素。
49.跳跃表是如何实现的？原理？
PS: 跳跃表是比较常问的一种结构。
跳跃表（skiplist ）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。
为什么使用跳跃表?
首先，因为 zset 要支持随机的插入和删除，所以它不宜使用数组来实现，关于排序问题，我们也很容易就想到红黑树/ 平衡树这样的树形结构，为什么 Redis 不使用这样一些结构呢？
- **性能考虑：**在高并发的情况下，树形结构需要执行一些类似于 rebalance 这样的可能涉及整棵树
的操作，相对来说跳跃表的变化只涉及局部；
- **实现考虑：**在复杂度与红黑树相同的情况下，跳跃表实现起来更简单，看起来也更加直观；
基于以上的一些考虑，Redis 基于WilliamPugh的论文做出一些改进后采用了跳跃表这样的结构。
本质是解决查找问题。
跳跃表是怎么实现的？
跳跃表的节点里有这些元素：
层
跳跃表节点的level 数组可以包含多个元素，每个元素都包含一个指向其它节点的指针，程序可以通过这些层来加快访问其它节点的速度，一般来说，层的数量月多，访问其它节点的速度就越快。
每次创建一个新的跳跃表节点的时候，程序都根据幂次定律，随机生成一个介于1 和3 2 之间的值作为level 数组的大小，这个大小就是层的“ 高度”
前进指针
每个层都有一个指向表尾的前进指针（level[i].forward 属性），用于从表头向表尾方向访问节点。
我们看一下跳跃表从表头到表尾，遍历所有节点的路径：
跨度
层的跨度用于记录两个节点之间的距离。跨度是用来计算排位（rank ）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
例如查找，分值为3 .0 、成员对象为o 3 的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3 ，所以目标节点在跳跃表中的排位为3 。
分值和成员
节点的分值（score 属性）是一个double 类型的浮点数，跳跃表中所有的节点都按分值从小到大来排序。
节点的成员对象（o bj 属性）是一个指针，它指向一个字符串对象，而字符串对象则保存这一个
SDS 值。
50.压缩列表了解吗？
压缩列表是 Redis为了节约内存而使用的一种数据结构，是由一系列特殊编码的连续内存快组成的顺序型数据结构。
一个压缩列表可以包含任意多个节点（entry ），每个节点可以保存一个字节数组或者一个整数值。
压缩列表由这么几部分组成：
zlbyttes: 记录整个压缩列表占用的内存字节数
zltail: 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
zllen: 记录压缩列表包含的节点数量
entryX:列表节点zlend: 用于标记压缩列表的末端
51.快速列表 quicklist 了解吗？
Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表 linkedlist ，也就是说当元素少时使用 ziplist ，当元素多时用 linkedlist 。
但考虑到链表的附加空间相对较高，prev和next指针就要占去16个字节（6 4 位操作系统占用
8个字节），另外每个节点的内存都是单独分配，会家具内存的碎片化，影响内存管理效率。
后来 Redis 新版本（3 .2 ）对列表数据结构进行了改造，使用quicklist代替了ziplist和
linkedlist，quicklist 是综合考虑了时间效率与空间效率引入的新型数据结构。
quicklist 由list 和ziplist 结合而成，它是一个由ziplist 充当节点的双向链表。
