自学内容网 自学内容网

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)!