Redis设计与实现数据结构篇 跳跃表 整数集合 压缩列表

• 跳跃表

  跳跃表支持平均 O(log n) ,最坏 O(n) 的查找效率。Redis只在两个地方使用了跳跃表，一个是有序集合SortedSet，另一个是在集群节点中用作内部数据结构。

跳跃表实现

typedef struct zskiplistNode{                 //跳跃表节点
    struct zskiplistLevel{                    //层
        struct zskiplistNode *forward;        //前进指针
        unsigned int span;                    //跨度
    }level[];
    struct zskiplistNode *backward;           //后退指针
    double score;                             //分值
    obj *obj;
}zskiplistNode;

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

跳跃表是有序集合的底层实现之一。（跳跃表、字典）

• 整数集合

      整数集合实现

typedef struct intset{
    uint32_t encoding;
    uint32_t length;
    unint8_t content[];
}intset;

1. content内数字有序，编码以encoding方式为准。
2. 若content内加入一个超过当前编码方式的数字，content类型升级。
3. 类型升级过程：
   1. 先确认升级后content占用的位数，例如3个uint32_t占位96位。首先对空间进行扩容。
   2. 依次分配原空间中的元素位置及占用空间大小。
   3. 修改encoding类型
4. 升级规则的优势：
   1. 灵活性
      C语言是静态类型语言，为了避免类型错误，通常不将类型不同的值加入同一数据结构。升级的设计没有打破这一原则，同时使不同类型的值可以一同加入数组。
   2. 节约内存
      如是为了避免类型错误，将uint_16,uint_32等类型不同的值加入同一数据结构，可以统一采用uint_64编码。与之相比，升级策略有效的节约了内存。
5. 整数集合一旦升级，就不能降级噢。

• 压缩列表

      压缩列表的实现

      压缩列表是哈希键和列表键的底层实现之一。

未完待续