Redis 跳跃列表与紧凑列表

Redis 跳跃列表（Skip List）

跳跃列表是一种高效的数据结构，它结合了有序数组和链表的优点，能够在 O(log n) 时间内进行插入、删除和查找操作。Redis 使用跳跃列表来实现有序集合（sorted set）的底层数据结构之一。

1. 跳跃列表的结构

跳跃列表由多个层级的链表组成，每一层都是一个有序链表。最低层包含所有元素，每一层都按一定概率跳过一些元素，从而减少查询路径的长度。

节点结构

每个节点包含以下几个部分：

• 值：节点存储的实际数据。
• 分数：用于排序的关键值。
• 前向指针数组：指向不同层级的下一个节点。

示意图：

Level 3:      1 ------> 6
Level 2:      1 --> 3 ------> 6 --> 9
Level 1:  1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9

2. 跳跃列表的操作

插入操作

插入一个新元素时，首先需要找到插入位置。查找路径通过各层链表找到最接近的节点，然后插入新节点并更新前向指针数组。

示意图：

原始列表：
Level 3:      1 ------> 6
Level 2:      1 --> 3 ------> 6 --> 9
Level 1:  1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9插入 4.5：
Level 3:      1 ------> 6
Level 2:      1 --> 3 ------> 6 --> 9
Level 1:  1 --> 2 --> 3 --> 4 --> 4.5 --> 5 --> 6 --> 7 --> 8 --> 9

删除操作

删除元素时，类似于插入操作，先找到要删除的节点，然后调整前向指针数组，移除该节点。

查找操作

查找操作利用各层链表加速定位目标元素，通过前向指针数组快速跳过无关节点，找到目标节点。

3. 跳跃列表的实现

Redis 中跳跃列表的实现主要包括以下几个结构体：

• zskiplistNode：跳跃列表节点结构，包含值、分数、前向指针数组等。
• zskiplist：跳跃列表结构，包含头节点、尾节点、节点数、最大层级等。

zskiplistNode 结构

typedef struct zskiplistNode {double score;robj *obj;struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];struct zskiplistNode *backward;
} zskiplistNode;

zskiplist 结构

typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;

4. Redis 中跳跃列表的应用

Redis 使用跳跃列表作为有序集合（sorted set）的一种实现方式（另一种实现是压缩列表，用于存储小数据量的有序集合）。跳跃列表提供了高效的插入、删除、查找和范围查询等操作，非常适合需要频繁更新和查询的有序集合。

5. 优点与缺点

优点

• 高效性：跳跃列表在插入、删除、查找等操作上都有 O(log n) 的时间复杂度，性能优越。
• 简单性：相比平衡树等复杂数据结构，跳跃列表实现相对简单，易于理解和维护。

缺点

• 空间消耗：由于需要维护多个层级的前向指针数组，跳跃列表的空间消耗相对较高。
• 概率性：跳跃列表的层级高度由随机算法决定，虽然平均性能优越，但在极端情况下可能出现性能不稳定的问题。

总结

跳跃列表是 Redis 中实现有序集合的一种高效数据结构。通过多层链表的设计，跳跃列表能够在保证高效查询的同时，提供较高的插入和删除性能。Redis 的跳跃列表实现结合了简单性和高效性，适用于各种需要有序存储和快速访问的数据场景。

Redis 紧凑列表（Ziplist）

Redis 5.0 又引入了一个新的数据结构 listpack，它是对 ziplist 结构的改进，在存储空间上会更加节省，而且结构上也比 ziplist 要精简。主要用于存储小规模的列表（list）和哈希表（hash）。紧凑列表通过一段连续的内存区域来存储多个元素，每个元素包含其值及其前一个元素的长度信息。

1. 紧凑列表的结构

紧凑列表由以下几个部分组成：

• zlbytes：紧凑列表所占用的总字节数。
• zltail：到最后一个元素的偏移量。
• zllen：紧凑列表包含的元素数量。
• entryX：列表中的元素（entry），每个元素包含其前一个元素的长度信息及其值。
• zlend：紧凑列表的结尾标记，固定为 0xFF。

示意图：

+--------+--------+--------+--------+--------+--------+--------+
| zlbytes| zltail | zllen  | entry1 | entry2 | ...    | zlend  |
+--------+--------+--------+--------+--------+--------+--------+

2. 紧凑列表的元素结构

每个元素（entry）包含以下部分：

• prevlen：前一个元素的长度。
• encoding：当前元素的编码方式，决定了元素值的存储形式。
• value：当前元素的实际值，根据编码方式的不同，可以是整数或字符串。

元素示意图：

+--------+--------+--------+
| prevlen| encoding| value  |
+--------+--------+--------+

3. 紧凑列表的操作

插入操作

插入一个新元素时，需要找到合适的位置，然后调整相应位置的偏移量和长度信息，将新元素插入到列表中。

示意图：

原始列表：
+--------+--------+--------+--------+--------+
| zlbytes| zltail | zllen  | entry1 | zlend  |
+--------+--------+--------+--------+--------+插入 entry2 后：
+--------+--------+--------+--------+--------+--------+
| zlbytes| zltail | zllen  | entry1 | entry2 | zlend  |
+--------+--------+--------+--------+--------+--------+

删除操作

删除一个元素时，需要找到该元素的位置，然后调整其前后元素的偏移量和长度信息，移除该元素。

示意图：

原始列表：
+--------+--------+--------+--------+--------+--------+
| zlbytes| zltail | zllen  | entry1 | entry2 | zlend  |
+--------+--------+--------+--------+--------+--------+删除 entry2 后：
+--------+--------+--------+--------+--------+
| zlbytes| zltail | zllen  | entry1 | zlend  |
+--------+--------+--------+--------+--------+

查找操作

查找元素时，需要遍历紧凑列表，依次比较每个元素的值，找到匹配的元素。

4. Redis 中紧凑列表的应用

紧凑列表在 Redis 中主要用于以下两种数据类型的底层实现：

• 列表（list）：当列表元素数量较少或每个元素的长度较短时，Redis 使用紧凑列表来实现。
• 哈希表（hash）：当哈希表中的键值对数量较少或每个键值对的长度较短时，Redis 使用紧凑列表来实现。

5. 优点与缺点

优点

• 节省内存：紧凑列表通过紧密排列的内存结构，显著减少了内存消耗。
• 较高的缓存命中率：由于紧凑列表在内存中是连续存储的，可以更好地利用 CPU 缓存，提高访问速度。

缺点

• 操作复杂：由于每次插入、删除操作需要调整多个元素的偏移量和长度信息，操作复杂度较高。
• 性能下降：当元素数量较多或元素长度较长时，紧凑列表的操作性能会显著下降。

总结

紧凑列表是一种高效的内存优化数据结构，适用于存储小规模列表和哈希表。通过紧密排列的内存结构，紧凑列表能够显著减少内存消耗，并提高缓存命中率。然而，由于操作复杂度较高，当数据规模增大时，紧凑列表的性能会受到一定影响。因此，在 Redis 中，紧凑列表主要用于存储小规模的数据，当数据规模增大时，Redis 会自动切换到其他更适合的数据结构，如双向链表或哈希表。