欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

redis源码解析--跳跃表

程序员文章站 2022-04-02 18:08:42
...

一、什么是跳跃表?

定义:

跳跃表是一种有序数据结构,它通过在每个节点中维护多个指向其他节点的指针,从而达到快速访问节点的目的。

注意几个关键词:

  • 有序:结构是有序的
  • 每个节点维护多个指针,本身结构是链表形式,和普通链表的不同之处在于每个元素内含多个指针

跳跃表支持平均O(logN),最坏O(N)复杂度的节点查询,大部分情况下,跳跃表的效率可以和平衡树相媲美,
并且因为跳跃表的实现比平衡树要来得简单,所以有不少程序都使用跳跃表来替代平衡树。

二、跳跃表示意图

redis源码解析--跳跃表
从图中可以看到:

  • 表头(head):负责维护跳跃表的节点指针。
  • 跳跃表节点:保存着元素值,以及多个层。
  • 下层的指针节点包含上层节点,最底层保持所有元素

三、redis哪些地方使用了跳跃表?

Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含你的元素较多,或者成员字符串较长,Redis就会使用跳跃表来作为有序集合的底层实现。

四、redis中跳跃表是如何实现的?

核心数据结构:

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

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

zskiplistNode结构用于表示跳跃表节点,zskiplist保持跳跃表节点的相关信息,如节点数量,表头表尾等。
redis源码解析--跳跃表

相关标签: redis 跳跃表