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 会自动切换到其他更适合的数据结构，如双向链表或哈希表。
原文地址：https://blog.csdn.net/Casual_Lei/article/details/140565468
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！