一，Redis 对象编码
本质上，Redis就是基于这些数据结构而构造出一个对象存储系统。redisObject 结构体有个 ptr 指针，指向对象的底层实现数据结构，encoding 属性记录对象所使用的编码，即该对象使用什么数据结构作为底层实现。
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object.
*/
#define OBJ_ENCODING_RAW /* Raw representation */ 简单动态字符串
#define OBJ_ENCODING_INT /* Encoded as integer */ 整数
#define OBJ_ENCODING_HT /* Encoded as hash table */ 字典
#define OBJ_ENCODING_ZIPLIST /* Encoded as ziplist */ 压缩列表
#define OBJ_ENCODING_INTSET /* Encoded as intset */ 整数集合
#define OBJ_ENCODING_SKIPLIST /* Encoded as skiplist */ 跳跃表
#define OBJ_ENCODING_EMBSTR /* Embedded sds string encoding */ embstr编码的简单动态字符串
#define OBJ_ENCODING_QUICKLIST /* Encoded as linked list of ziplists */
二，ZSet编码的选择
有序集合对象的编码可以是 ziplist 或者 skiplist。同时满足以下条件时使用 ziplist 编码：
- 1，元素数量小于128个
- 2，所有member的长度都小于64字节
以上两个条件的上限值可通过 zset-max-ziplist-entries 和 zset-max-ziplist-value 来修改。
三，ziplist
ziplist 编码的 Zset 使用紧挨在一起的压缩列表节点来保存，第一个节点保存 member，第二个保存 score。ziplist 内的集合元素按 score 从小到大排序，其实质是一个双向链表。虽然元素是按 score 有序排序的， 但对 ziplist 的节点指针只能线性地移动，所以在 REDIS_ENCODING_ZIPLIST 编码的 Zset 中， 查找某个给定元素的复杂度为O(n)。
ziplist内存数据结构，由如下5部分构成：
各个部分在内存上是前后相邻的并连续的，每一部分作用如下：
zlbytes： 存储一个无符号整数，固定四个字节长度（32bit），用于存储压缩列表所占用的字节（也包括zlbytes本身占用的4个字节），当重新分配内存的时候使用，不需要遍历整个列表来计算内存大小。
zltail： 存储一个无符号整数，固定四个字节长度（32bit），表示 ziplist 表中最后一项（entry）在 ziplist 中的偏移字节数。zltail 的存在，使得我们可以很方便地找到最后一项（不用遍历整个ziplist），从而可以在 ziplist 尾端快速地执行 push 或 pop 操作。
zllen： 压缩列表包含的节点个数，固定两个字节长度（16bit）， 表示 ziplist 中数据项（entry）的个数。由于zllen字段只有16bit，所以可以表达的最大值为2^16-1。
注意点：如果 ziplist 中数据项个数超过了16bit 能表达的最大值，ziplist 仍然可以表示。ziplist 是如何做到的？
如果zllen小于等于216-2（也就是不等于216-1），那么zllen就表示 ziplist 中数据项的个数；
否则，也就是 zllen 等于16bit全为1的情况，那么zllen就不表示数据项个数了，这时候要想知道ziplist中数据项总数，那么必须对ziplist从头到尾遍历各个数据项，才能计数出来。
entry：表示真正存放数据的数据项，长度不定。一个数据项（entry）也有它自己的内部结构。
zlend： ziplist最后1个字节，值固定等于255，其是一个结束标记。
四，skiplist
skiplist编码的有序集合底层是一个命名为zset的结构体，而一个 zset 结构同时包含一个字典和一个跳跃表。
跳跃表按 score 从小到大保存所有集合元素。而字典则保存着从 member 到 score 的映射，这样就可以用 O(1) 的复杂度来查找 member 对应的 score 值。虽然同时使用两种结构，但它们会通过指针来共享相同元素的member 和 score，因此不会浪费额外的内存。
1，存储结构：
2，详解：
跳表 (skip List)是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为 O(logN)。简单说来跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供 O(logN) 的时间复杂度。
先来看一个有序链表，如下图（最左侧的灰色节点表示一个空的头结点）：
在这样一个链表中，如果我们要查找某个数据，那么需要从头开始逐个进行比较，直到找到包含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，时间复杂度为 O(n)。同样，当我们要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置。
假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：
这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是7, 19, 26）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：
- 1,23首先和7比较，再和19比较，比它们都大，继续向后比较。
- 2,但23和26比较的时候，比26要小，因此回到下面的链表（原链表），与22比较。
- 3,23比22要大，沿下面的指针继续向后和26比较。23比26小，说明待查数据23在原链表中不存在，而且它的插入位置应该在22和26之间。
在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。利用同样的方式，我们可以在上层新产生的链表上，继续为每相邻的两个节点增加一个指针，从而产生第三层链表。如下图：
在这个新的三层链表结构上，如果我们还是查找23，那么沿着最上层链表首先要比较的是19，发现23比19大，接下来我们就知道只需要到19的后面去继续查找，从而一下子跳过了19前面的所有节点。可以想象，当链表足够长的时候，这种多层链表的查找方式能让我们跳过很多下层节点，大大加快查找的速度。
skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。
但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。
skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。
比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：
从上面skiplist的创建和插入过程可以看出，每一个节点的层数（level）是随机出来的，而且新插入一个节点不会影响其它节点的层数。因此，插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上，这是skiplist的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。
skiplist，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了一些节点，从而也就加快了查找速度。
刚刚创建的这个skiplist总共包含4层链表，现在假设我们在它里面依然查找23，下图给出了查找路径：
需要注意的是，前面演示的各个节点的插入过程，实际上在插入之前也要先经历一个类似的查找过程，在确定插入位置后，再完成插入操作。
实际应用中的skiplist每个节点应该包含key和value两部分。前面的描述中我们没有具体区分key和value，但实际上列表中是按照key(score)进行排序的，查找过程也是根据key在比较。
3，随机数计算
执行插入操作时计算随机数的过程，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：
在Redis的skiplist实现中，代码中两个参数的取值为：
ZSKIPLIST_P：0.25 ， ZSKIPLIST_MAXLEVEL：32
评论区