Redis底层数据类

发布时间:2018-11-15  栏目:NoSQL  评论:0 Comments

链表在Redis
中的用很常见,比如排表键的底层实现有即是链表。除了链表键之外,发布暨订阅、慢查询、监视器等功用为运用了链表,
Redis
服务器本身还用链表来保存多独客户端的状态信息,以及以链表来构建客户端输出缓冲区(
output buffer)。

Redis支持五种多少列:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted
set:有序聚集)。

 (与HashMap一样的hash方法)

5、zset(sorted set:有序聚集)

Redis zset 和 set 一样吧是string类型元素的集,且无同意再的分子。

不同的凡每个元素都见面涉及一个double类型的分数。redis正是经过分数来为集中的分子开展打小至大的排序。

 zset的分子是绝无仅有的,但分数(score)却得以重新。

  • 渐进式rehash

3、List(列表)

Redis
列表是概括的字符串列表,按照插入顺序排序。你可以长一个要素导列表的首(左边)或者尾部(右边)。

列表最多但存储 2^(32 – 1)元素 (4294967295, 每个列表可存储40大多亿)。

通过以length
属性来记录节点的数码,程序可以在0(1)复杂度内返回跳跃表的长度。level
属性则用来在O(1)复杂度内获得跳跃表中层高顶深之百般节点的层数。

2、Hash(哈希)

Redis hash 是一个键值对聚集。

Redis
hash是一个string类型的field和value的映射表,hash特别符合用来存储对象。每个
hash 可以储存 2^(32 – 1)键值对(40几近亿)

操作:

4、Set(集合)

Redis的Set是string类型的无序集聚。

会合是经哈希表实现之,所以添加,删除,查找的复杂度都是O(1)。

注意: 添加了区区浅的聚合,根据集合内元素的唯一性,第二破栽的要素以为忽视。

聚拢中极度深之分子反复也 2^(32 – 1)(4294967295,
每个集合可存储40基本上亿个成员)。

  • 升级

1、String(字符串)

string是redis最中心的门类,你得领略成与Memcached一模型一样的品种,一个key对应一个value。

string类型是二进制安全之。意思是redis的string可以分包其他数。比如jpg图片或序列化的目标

string类型是Redis最中心的数据类型,一个键最可怜能储存512MB。

quicklist结构意思为一个由于ziplist组成的双向链表,链表中之各一个节点都以压缩列表ziplist的布局保留着数量,而ziplist有多单entry节点,保存着多少。相当与一个quicklist节点保存之是同切开数量,而不再是一个数码。

Redis
的数据库就是行使字典来作底层实现之,对数据库的充实、删、查、改操作也是构建以对字典的操作之上的。字典还是哈希键的平底实现有,当一个哈希键包含的键值对比较多,又或键值对遭受之素都是于丰富的字符串时,
Redis 就会见利用字典作为哈希键的最底层实现。

https://blog.csdn.net/DERRANTCM/article/details/78908070

 

sds结构一共发生五种Header定义,其目的是为满足不同长度的字符串可以用不同尺寸的Header,从而节省内存。

 

结构:

压缩了的ziplist结构—quicklistLZF:

与一般的双端链表无异,定义了链表节点的结构体之后,下面就定义链表的结构体,用来方便管理链表节点,其组织体定义如下:

Redis主要数据结构:简短动态字符串(SDS)、双端链表、字典、跳跃表、整数集合、压缩列表和高效列表

table 属性是一个累组,数组中之每个元素还是一个针对性dict.h/dictEntry
结构的指针,每个dictEntry 结构保留在一个键值对。

由此应用SDS代替C字符串的优点:

zltail:4字节,记录压缩列表尾部节点距离起始地址之偏移量

 

五、整数集合

每个intset.h/intset 结构意味着一个整数集合:

 

 quicklist表头结构:

next
属性是靠于任何一个哈希表节点的指针,这个指针可以用大半独哈希值相同的键值对连日于一如既往破,以之来解决键冲突(collision)的题目。

Redis提供了三栽跳跃表节点删除操作。分别如下:

无异于、简单动态字符串(SDS):

多个跳跃表节点就得做一个跳跃表:

 图片 1

根据加分值来删除节点,由zslDeleteByScore函数实现;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key); // 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key); // 复制键的函数
    void *(*valDup)(void *privdata, const void *obj); // 复制值的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 对比键的函数
    void (*keyDestructor)(void *privdata, void *key); // 销毁键的函数
    void (*valDestructor)(void *privdata, void *obj); // 销毁值的函数
} dictType;
typedef struct dict {
    dictType *type; // 类型特定函数
    void *privdata; // 私有数据
    dictht ht[2]; // 哈希表
    long rehashidx; //rehash 索引,当 rehash 不在进行时,值为 -1
    unsigned long iterators; // 目前正在运行的安全迭代器的数量
} dict;
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;

x = zsl->header;
// 从最高层开始查询
for (i = zsl->level-1; i >= 0; i--) {
// 前向指针不为空,前置指针的分值小于score或当前向指针的分值等于空但成员对象不等于o的情况下,继续向前查找
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                sdscmp(x->level[i].forward->ele,ele) <= 0))) {
            rank += x->level[i].span;
            x = x->level[i].forward;
        }

        // 此时x可能是header,所以此处需要判断一下
        if (x->ele && sdscmp(x->ele,ele) == 0) {
            return rank;
        }
    }
    return 0;
}

       其中哈希表的负载因子可以透过公式:

  随着操作的随地实践,哈希表保存的键值对会晤慢慢地多或者缩减,为了让哈希表的负荷因子(load
factor)维持以一个靠边的限制以内,当哈希表保存之键值对数据最为多或者最好少时,程序需要对哈希表的尺寸进行相应的扩张或者收缩。

 

  • 老二进制安全。
typedef struct list {
    listNode *head;//头
    listNode *tail;//尾
    void *(*dup)(void *ptr);//复制函数
    void (*free)(void *ptr);//释放函数
    int (*match)(void *ptr, void *key);//节点值对比函数
    unsigned long len;//链表长度
} list;
  • 压缩修改字符串是带来的内存重新分配次数;

Redis 的链表实现之特性可总结如下:

entry:不定,列表中之每个节点

 

  • 哈希算法:
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 跳跃表的表头节点和表尾节点
    unsigned long length; // 表中节点的数量
    int level; // 表中层数最大的节点层数
} zskiplist;

跳跃表数据结构
跳跃表的结构体定义在server.h文件中。其中包括腾表节点zskiplistNode和跳跃表zskiplist两个结构体。

       渐进式rehash 的功利在受其采用分而治之的艺术,将rehash
键值对所待的乘除工作全摊到对字典的每个长、删除、查找和换代操作及,从而避免了集中式rehash
而带的宏大计算量。

  • 渐进式rehash 执行中的哈希表操作
typedef struct zskiplistNode {
    sds ele; // 成员对象
    double score; // 分值
    struct zskiplistNode *backward; // 后向指针
    struct zskiplistLevel {// 层
        struct zskiplistNode *forward; // 前向指针
        unsigned int span; // 跨度
    } level[];
} zskiplistNode;

图片 2

type 属性和privdata 属性是针对不同品类的键值对,为创建多态字典而设置的:

 

若果privdata 属性则保留了需传为那些类型特定函数的可选参数。

 

Redis为sdlist定义了一个迭代器结构,其能够正序和逆序的看list结构:

  • 将获字符串长度所需要的复杂度降低到O(1);
  • 杜缓冲区溢起底状态;

  C
字符串里面未能够包含空字符,否则最先于先后读人的空字符将被误认为是字符串结尾,这些使得C
字符串只能保留文本数据。虽然数据库一般用于保存文本数据,但利用数据库来保存像图、音频、视频、压缩文件二前行制数据的景象呢不少见,因此,为了保证Redis
可以适用于各种不同之使状况, SDS 的API
都是二进制安全之(binary-safe),所有SDS API
都见面为处理二进制的法子来拍卖SDS
存放在buf数组里之多少,程序不会见针对内部的多寡做另外限制、过滤、或者只要,数据在写入时凡安的,它叫读取时便是哪些。

       #负载因子=哈希表巳保存节点数量/哈希表大小load factor=
ht[0].used / ht[0].size

  每当我们只要拿一个新因素添加到整数集合里面,并且新元素的品类比较整数集合现有所有因素的类型且设抬高时,整数集合需要事先进行升级换代(upgrade),然后才能够以新元素添加到整数集合里面。整数集合的提升政策有一定量个便宜,一个凡是晋升整数集合的八面玲珑,另一个是硬着头皮地节约空间

      
字典的删减(delete)、查找(find)、更新(update)等操作会在点滴个哈希表上展开。新添加至字典的键值对一律会给保留及ht[l]里面,而ht[0]则不再进行其它添加操作。

zllen:2字节,记录压缩列表包含的节点数量

quicklist节点结构:

字典是相同种用于保存键值对(key-value
pair)的纸上谈兵数据结构。在字典中,一个键(key)可以同一个价(value)进行关联(或者说将键映射为价值),这些涉及的键和价值就称键值对。因此Redis
构建了投机之字典实现。

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    // updata[]数组记录每一层位于插入节点的前一个节点
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
// rank[]记录每一层位于插入节点的前一个节点的排名
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
x = zsl->header;
// 从最高层开始查找
    for (i = zsl->level-1; i >= 0; i--) {
        // 存储rank值是为了交叉快速地到达插入位置
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        // 前向指针不为空,前置指针的分值小于score或当前向指针的分值等于空但成员对象不等于0的情况下,继续向前查找
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        // 存储当前层上位于插入节点的前一个节点
        update[i] = x;
}
// 此处假设插入节点的成员对象不存在于当前跳跃表内,即不存在重复的节点
// 随机生成一个level值
    level = zslRandomLevel();
if (level > zsl->level) {
        // 如果level大于当前存储的最大level值
     // 设定rank数组中大于原level层以上的值为0
     // 同时设定update数组大于原level层以上的数据
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        // 更新level值
        zsl->level = level;
}
// 创建插入节点
    x = zslCreateNode(level,score,ele);
for (i = 0; i < level; i++) {
        // 针对跳跃表的每一层,改变其forward指针的指向
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        // 更新插入节点的span值
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
// 更新高层的span值
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    // 设定插入节点的backward指针
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

      
//如果程序执行的凡缩短字符串的操作,比如截断操作(trim),那么当实践是操作下,程序用经内存重分配来刑释解教字符串不再使用的那有些空中一一如果忘记了当时同样步就是会有内存泄漏。

 

栽节点:

typedef struct dictht {
    dictEntry **table;// 哈希表数组
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩蜀,用于计算索引值, 总是等于size-1
    unsigned long used; // 该哈希表已有节点的数量
} dictht;
  • rehash

zlend:1字节,特殊值0xFF,标记压缩列表的收。

重要操作:

  跳跃表(skiplist)是相同种植有序数据结构,它经过当每个节点受到保障多只对任何节点的指针,从而达到快速访问节点的目的。

七、快速列表(quicklist)

       //SDS通过非运空间,
SDS实现了空中预分配(同齐扩容)和惰性空间释放(同回收sds空余空间的函数)两种优化策略。

Redis提供了有的区间操作,用于取有段距离上的节点还是去某段区间上的富有节点等操作,这些操作大大提高了Redis的易用性:

https://blog.csdn.net/terence1212/article/details/53770882

结构:

type 属性是一个对dietType 结构的指针,每个dietType
结构保留了一样丛用于操作特定项目键值对之函数, Redis
会为用不同之字典设置不同之类别特定函数。

       Redis
使用跳跃表作为一如既往聚集合键的底色实现有,如果一个一成不变聚集包含的素数量比多,又或有序聚集中元素的积极分子(member)是较丰富的字符串时,
Redis 就会见下跳跃表作为一如既往聚集合键的底色实现。

  1. 据悉新元素的类型,扩展整数集合底层数组的长空大小,并为新因素分配空间。
  2. 拿脚数组现有的有着因素还更换成为跟新元素相同之档次,并以类型转换后的元素放置到科学的各类上,而且每当停放元素的长河中,需要连续保障底层数组的有序性质不换。
  3. 以新元素添加到底层数组里面。

    static intset intsetUpgradeAndAdd(intset is, int64_t value) {

    // 获取当前编码格式
    

    uint8_t curenc = intrev32ifbe(is->encoding);
    // 获取需要提升到的编码格式
    uint8_t newenc = _intsetValueEncoding(value);
    // 获取原整数集中之平头只数
    int length = intrev32ifbe(is->length);
    // 由于用添加的素一定是凌驾或者小于整数集中具有因素,故此处需要看清上加到新数据集的头部要尾部
    // 如果value为正,则补充加至新数据集的尾;反的则补充加至首部

    int prepend = value < 0 ? 1 : 0;
    
    // 设定新的编码格式
    

    is->encoding = intrev32ifbe(newenc);
    // 对原先数集进行扩容

    is = intsetResize(is,intrev32ifbe(is->length)+1);
    

    // 采用打晚往前方之重编码顺序,这样即使避免覆盖数据了。
    while(length–)

        // 将原数据集中的数据依次赋值到新数据集中
     // _intsetGetEncoded(is,length,curenc)获取数据集is的第length位上的数据,curenc为原数据集的编码格式
     // _intsetSet将数据集is的第length+prepend位上设定为上一函数返回的值
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    
    // 将待添加的数据添加到首部或者尾部
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 修改新数据集的长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
    

    }

  4. 降级:整数集合不支持降级操作,一旦对数组进行了晋升,编码就见面一直保持升级后的状态。

zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    // 申请内存
    zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    // 设定分值
    zn->score = score;
    // 设定成员对象
    zn->ele = ele;
    return zn;
}

三、字典

typedef struct dictEntry {
    void *key; // 键
    union {// 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下个哈希表节点,形成链表
} dictEntry;

上述三种植操作的去除节点部分都出于zslDeleteNode函数完成。zslDeleteNode函数用于去某个节点,需要加以当前节点和各级一样重叠下时节点的前头一个节点。

sds释放函数sdsfree、sds动态调整函数sdsMakeRoomFor、回收sds空余空间的函数sdsRemoveFreeSpace(实际上,就是重新分配一块内存,将原本数据拷贝到新内存上,并释放原有空间,程序并无立使用外存重分配来回收缩短后大多出来的字节,而是下free
属性将这些字节的数据记录起来,并听候未来采取)、sds连接操作函数sdscatlen。

https://blog.csdn.net/terence1212/article/details/53543799

  //如果程序执行的是增长字符串的操作,比如拼接操作(append),那么当尽这操作前,程序用先通过外存重分配来扩充底层数组的空中大小顺序如果忘记了就同样步就是会见发生缓冲区溢出。

typedef struct quicklistEntry {
    const quicklist *quicklist;   //指向所属的quicklist的指针
    quicklistNode *node;          //指向所属的quicklistNode节点的指针
    unsigned char *zi;            //指向当前ziplist结构的指针
    unsigned char *value;         //指向当前ziplist结构的字符串vlaue成员
    long long longval;            //指向当前ziplist结构的整数value成员
    unsigned int sz;              //保存当前ziplist结构的字节数大小
    int offset;                   //保存相对ziplist的偏移量
} quicklistEntry;

零星单节点内的跨度进一步怪,它们相距得哪怕更远。指向NULL
的有着前进指针的跨度都为0 ,因为它并未连往其他节点。

六、压缩列表

当一个排表键只含有少量底列表项,并且每个列表项或就算是有点整数型或者是长比短的字符串。常因此来作为列表建以及哈希键的平底实现。为了节省内存而付出。

  1. 服务器即尚未当履行BGSAVE 命令或者BGREWRITEAOF
    命令,并且哈希表的负荷因被不止等于1。
  2. 服务器即在尽BGSAVE 命令或者BGREWRITEAOF
    命令,并且哈希表的载重因子大于等于5。

结构:

 

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 表示字符串真正的长度,不包含空终止字符*/
    uint8_t alloc; /* 表示字符串的最大容量,不包含Header和最后的空终止字符 */
    unsigned char flags; /*表示header的类型*/
    char buf[];
};

ht 属性是一个分包两独桩之累组,数组中的每个件都是一个dictht
哈希表,一般情况下,字典只使ht[0]哈希表,
ht[l]哈希表只会以对ht[0]哈希表进行rehash
时以。除了ht[1]以外,另一个与rehash 有关的性就是rehashidx
,它记录了rehash 目前之进度,如果手上不曾在进展rehash
,那么她的价值为-1。图4-3 展示了一个普通状态下(没有进展rehash)的字典。

跨度:臃肿的跨度(level [i] . span 属性)用于记录点滴单节点内的偏离:

      
扩展或收缩哈希表需要将ht[0]中间的具有键值对rehash到ht[l]内部,但是,这个rehash
动作连无是一次性、集中式地好的,而是分多次、渐进式地得的。这样做的来头在于以避免rehash对服务器性能造成影响。以下是哈希表渐进式rehash
的详细步骤:

      
当以下原则中之自由一个给满足时,程序会活动启针对哈希表执行扩展操作:

 结构:

因加排名来删除节点,由zslDeleteByRank函数实现

  1. quicklist宏观上是一个双向链表,因此,它装有一个双向链表的粗,进行扦插或去操作时坏有利,虽然复杂度为O(n),但是非需内存的复制,提高了频率,而且看两端元素复杂度为O(1)。
  2. quicklist微观上是平切片片entry节点,每一样切片entry节点内存连续且顺序存储,可以经二区划查找以
    log2(n) 的复杂度进行固化。

      
当要以一个新的键值对丰富到字典里时,程序用先冲键值对之键计算出哈希值和索引值,然后再次根据索引值,将含有新键值对之哈希表节点放到哈希表数组的指定索引上面。Redis
计算哈希值和索引值的法门如下: 

距离操作:

结构:

  1. 为ht [1]分红空间,让字典同时兼有ht[0]和ht[l]点滴单哈希表。
  2. 在字典中保障一个索引计数器变量rehashidx ,并以它们的价值设置为0
    ,表示rehash工作专业开。
  3. 在rehash
    进行次,每次对字典执行长、删除、查找或者更新操作时,程序除了实行指定的操作以外,还会有意无意将ht[0]哈希表在rehashidx
    索引上之兼具键值对rehash到ht[l],当rehash工作做到以后,程序将rehashidx
    属性的值增1。
  4. 乘字典操作的穿梭实践,最终在某某时间接触上,ht[0]的富有键值对都见面给rehash
    至ht[l],这时程序用rehashidx 属性的值设为-1,表示rehash
    操作都就。

朝跳跃表中插一个节点,必然会转移跳表的尺寸,可能会见转该尺寸。而且对于插入位置处在之上下节点的backward和forward指针均要改。
插入节点的重点在找到在哪里插入该节点,跳跃表是依照score分值进行排序的,其招来步骤大致是:从当前最高的level开始,向前查找,如果手上节点的score小于插入节点的score,继续上前;反之,则下降一层继续搜寻,直到第一重合结。此时,插入点就算厕找到的节点之后。

void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
        // 如果x存在于该层,则需要修改前一个节点的前向指针
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        } else {
        // 反之,则只需要将span-1
            update[i]->level[i].span -= 1;
        }
}
// 修改backward指针,需要考虑x是否为尾节点
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward;
    }
    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    zsl->length--;
}

遍历操作就利用前进指针就可做到了,跨度实际上是故来计量排位(rank)的:在查找某个节点的历程遭到,将沿途访问过的所有层的跨度累计起来,得到的结果虽是目标节点在跳表中之排位。

跳跃表操作:

  升级整数凑合并添加新元素共分为三步进行:

老是创建一个初跳跃表节点的上,程序都因事次定律(power
law,越充分之屡屡起的几率越小)随机大成一个在1 同32 之间的值作为level
数组的大大小小,这个分寸就是层的“高度”。

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

 

  当SDS需要改时,首先会见检讨SDS的半空中是否满足修改所欲的求,如果无饱会自动进行空中扩容。sds规定:如果扩展后的字符串总长度小于1M虽新字符串长度也扩大后的有限加倍;如果过量1M,则新的毕竟长度为扩大后底究竟长度加上1M;这样做的目的是缩减Redis内存分配的次数,同时尽量节省空间。

 https://blog.csdn.net/DERRANTCM/article/details/78993135

缔造一个跳跃表

 

https://blog.csdn.net/DERRANTCM/article/details/78898416

zlbytes:4字节,记录整个压缩列表占用内存的字节数

因加分值和成员来删除节点,由zslDelete函数实现;

 

typedef struct quicklistNode {
  struct quicklistNode *prev; //前驱节点指针
  struct quicklistNode *next; //后继节点指针

//不设置压缩数据参数recompress时指向一个ziplist结构
//设置压缩数据参数recompress指向quicklistLZF结构
  unsigned char *zl;
  unsigned int sz;             //压缩列表ziplist的总长度
  unsigned int count : 16;     //ziplist中包的节点数,占16 bits长度
//表示是否采用了LZF压缩算法压缩quicklist节点,1表示压缩过,2表示没压缩,占2 bits长度
  unsigned int encoding : 2;   
//表示一个quicklistNode节点是否采用ziplist结构保存数据,2表示压缩了,1表示没压缩,默认是2,占2bits长度
  unsigned int container : 2;  
//标记quicklist节点的ziplist之前是否被解压缩过,占1bit长度
//如果recompress为1,则等待被再次压缩
    unsigned int recompress : 1; 
    unsigned int attempted_compress : 1; /* 节点太小无法压缩//测试时使用 */
    unsigned int extra : 10; //额外扩展位,占10bits长度
} quicklistNode;

取得给定分值和分子的节点的行:

四、跳跃表

蹿表删除:

亚、双端链表

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

图片 3

 

https://blog.csdn.net/terence1212/article/details/53542072

Redis没有直接运用C语言中之习俗的字节数组保存字符串,而是自行构建了概括动态字符串(SDS),C字符串只是作为简单动态字符串(SDS)的字面量,用于在不必对字符串值进行改动的地方。

层(level):节点受到因故Ll 、L2 、L3 等字样标记节点的次第层, Ll
代表首先交汇,
L2意味着第二重叠,以此类推。每个层都带有两单特性:前进指针和跨度。前进指针用于访问位于表尾方向的任何节点,而跨度则记录了进步指针所依于节点和时节点的相距。跳跃表节点的level
数组可以涵盖多单元素,每个元素都蕴含一个对任何节点的指针,程序可以经这些重叠来加快访问其他节点的进度,一般的话,层的数目更是多,访问其他节点的快就越快。

       Redis
只以片个地方因此到了弹跳表,一个凡是贯彻稳步聚集合键,另一个是以集群节点受到作为内部数据结构。

typedef struct quicklistLZF {
    //表示被LZF算法压缩后的ziplist的大小
    unsigned int sz; /* LZF size in bytes*/
    //保存压缩后的ziplist的数组,柔性数组
    char compressed[];
} quicklistLZF;
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    // 申请内存
zsl = zmalloc(sizeof(*zsl)); 
// 初始化跳跃表属性
    zsl->level = 1;
zsl->length = 0;
// 创建一个层数为32,分值为0,成员对象为NULL的表头结点
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
// 设定每层的forward指针指向NULL
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
}
// 设定backward指向NULL
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}
  • 双端:链表节点带有prev 和next
    指针,获取有节点的坐节点和后置节点的复杂度都是O(1)。
  • 无环:表头节点的prev 指针和表尾节点的next 指针都对NULL
    ,对链表的看为NULL 为巅峰。
  • 带表头指针和表尾指针:通过list 结构的head 指针和tail
    指针,程序获得链表的表头节点和表尾节点的复杂度为O(1)。
  • 带链表长度计数器:程序下list 结构的len 属性来对list
    持有的链表节点进行计数,程序取得链表中节点数量之复杂度为O(1)。
  • 多态:链表节点使用void*指南针来保存节点值,并且可通过list
    结构的dup、free、match
    三独特性为节点值设置类型特定函数,所以链表可以用于保存各种不同品类的值。
  1. 收获有区间上第一独符合范围之节点。zslFirstInRange;
  2. 获有区间上最终一个称范围之节点。zslLastInRange;
  3. 剔除给定分值范围外之持有因素。zslDeleteRangeByScore;
  4. 除去给定排名区间内之有着节点。zslDeleteRangeByRank。
typedef struct quicklist {
    //指向头部(最左边)quicklist节点的指针
    quicklistNode *head;
    //指向尾部(最右边)quicklist节点的指针
    quicklistNode *tail;
    //ziplist中的entry节点计数器
    unsigned long count;        
    //quicklist的quicklistNode节点计数器
    unsigned int len;           
    //保存ziplist的大小,配置文件设定,占16bits
    int fill : 16;              
    //保存压缩程度值,配置文件设定,占16bits,0表示不压缩
    unsigned int compress : 16; 
} quicklist;
  1. #使用字典设置的哈希函数,计算键key 的哈希值
  2. hash= dict->type->hashFunction(key);
  3. #使用哈希表的sizemask 属性和哈希值,计算出索引值
  4. #根据气象不一, ht[x]可以是ht[0]或者ht[1]
  5. index = hash 品dict->ht[x].sizemask;

  6. 解决键冲突:

跳跃表基本操作 Redis中有关跳跃表的相干操作函数定义在t_zset.c文件中:

图片 4

https://blog.csdn.net/DERRANTCM/article/details/78999143

key 属性保存着键值对面临的键,而v
属性则保留着键值对遭到之值,其中键值对的价值好是一个指南针,或者是一个uint64_t
整数,又要是一个int64_t 整数。

结构:

平头集合(intset)是Redis
用于保存整数值的聚集抽象数据结构,它可保存类型为int16_t 、int32_t
或者int64_t 的平头值,并且保证集合中不见面并发重元素。

缔造一个腾表节点:

  1. 恢宏以及收缩哈希表的工作可以通过推行rehash(重新散列)操作来成功,
    Redis对字典的哈希表执行rehash的步子如下:
  2. 为字典的ht[1]哈希表分配空间,这个哈希表的空中大小取决于要履的操作,以及ht[0]即带有的键值对数码(也就算是ht[0].used
    属性的价值):
  3. 一旦实施的凡扩大操作,那么ht[1]的轻重为率先单超等于ht[0]
    .used*2的2^n(2 的n 次方幕);
  4. 只要推行之是抽操作,那么ht[1]的大大小小也第一个超过等于ht[0] .used
    的2^n
  5. 以保存在ht[0]遭遇之持有键值对rehash 到ht[1]点:
    rehash指的是双重计算键的哈希值和索引值,然后以键值对停放到ht[l]哈希表的指定位置上。
  6. 当ht[0]带有的拥有键值对都搬至了ht[1]之后(ht
    [0]成为空表),释放ht[0],将ht [1]设置为ht[0]
    ,并在ht[1]初创办一个空白哈希表,为下一致次rehash做准备。

  7. 哈希表的恢弘和收缩

 

管理ziplist信息的构造quicklistEntry:

 重大操作:

因为Redis 使用的C 语言并没有坐这种数据结构,所以Redis
构建了投机之链表实现。

  跳跃表支持平均O(logN)、最坏O(N)(的复杂度的节点查找,还好透过顺序性操作来批量拍卖节点。在大部情下,跳跃表的频率可以和平衡树相媲美,并且以跳跃表的兑现比较平衡造就要来得尤其简单,所以来成千上万顺序都以跳跃表来替代平衡树。

Redis为双端链表的各国一个节点定义了之类的结构体:

      
当有少单或以上数量的键被分配至了哈希表数组的和一个目录上面时,我们遂这些键发生了扑(collision)。redis的哈希表使用链地址法(separate
chaining)来解决键冲突,每个哈希表节点都发生一个next
指针,多独哈希表节点可以为此next
指针构成一个只是为链表,被分配到和一个目录上之基本上只节点可以据此这只有为链表连接起来,这即化解了键冲突之题材。

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 集合包含的元素数量
    int8_t contents[];// 保存元素的数组
} intset;

留下评论

网站地图xml地图