乐趣区

关于redis:redis学习之四skiplist

jiezi

之前相关联文章：
redis 学习之一 SDS
redis 学习之二链表
redis 学习之三字典

一 经典的 skiplist

咱们先来看看 skiplist 的一张示意图：

这是在一个有序列表 {3，7，11，19，22，26，37} 里查找 23 这个值的一个过程，它是从头节点的最上层开始，通过每个层的比拟判断来进行节点的定位。
skiplist 个性：

  1. 由多层组成。
  2. 每一层都是有序的链表。
  3. 最底层 (Level 1) 的链表蕴含所有元素。
  4. 如果一个元素呈现在 Level i 的链表中，则它在 Level i 之下的链表也都会呈现。
  5. 每个节点蕴含两个指针，一个指向同一链表中的下一个元素，一个指向上面一层的元素。

skiplist 是一种有序数据结构，反对均匀 O(logN)、最坏 O(n)复杂度的节点查找，其效率不低于均衡树，且 skiplist 的实现较于均衡树实现要更简略。redis 应用 skiplist 次要是在有序汇合里。

skiplist 定义

typedef struct zskiplist{
    // 表头节点和表尾节点
    struct zskiplistNode *header,*tail;
    // 表中节点数量
    unsigned long length;
    // 最大节点层数
    int level;
}zskiplist;

二 redis 里 skiplist

redis 里 skiplist 定义：

typeof struct zskiplistNode{
    // 后退节点，以后节点指向的前一个节点，从后向前遍历时应用
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    strcut zskiplistLevle{
        // 后退指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    }level[];}zskiplistNode;

阐明：图中是 redis 里应用通过革新过的 skiplist，BW 是后退指针；1.0/2.0/3.0 是分值；o1/o2/o3 是对象。
redis 里的 skiplist 与经典的 skiplist 之间的比拟，有如下特点：

  1. 分数 (score) 容许反复，也就是 skiplist 的 key 是充许反复的。
  2. 大比拟过程中，须要比拟 score 也须要比拟数据自身。score 雷同时，数据自身是按字典有序的。
  3. 第一层是一个双向链表，不便由后向前遍历。
  4. 跨度 span 是用来计算排位 (rank) 的：在查找某个节点的过程中，将沿途拜访过的所有层的跨度累计起来，失去的后果就是指标节点在 skiplist 中的排位。

三 redis 里的 sorted set

Redis 中的 sorted set，是在 skiplist, dict 和 ziplist 根底上构建起来的:

  1. 当数据较少时，sorted set 是由一个 ziplist 来实现的。
  2. 当数据多的时候，sorted set 是由一个叫 zset 的数据结构来实现的，这个 zset 蕴含一个 dict + 一个 skiplist。dict 用来查问数据到分数 (score) 的对应关系，而 skiplist 用来依据分数查问数据（可能是范畴查找）。

本文参考的有：
黄健宏的《Redis 设计与实现》一书
张铁蕾对于 skiplist 的文章
其它文章

退出移动版