redis学习(十) 数据结构

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了redis学习(十) 数据结构，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6058字，纯文字阅读大概需要9分钟。

内容图文

字符串结构

struct sdshdr{
    int len;
    int free;
    char buf[];
}

简单字符串结构中，buf存储的字符数组也是使用'\0'作为字符数组的结尾，但是在使用上对用户是透明的，这个设计能重用C的字符数组函数。

另一个好处是，redis使用了一个常数len记录字符串的长度，在函数自动更新，不像C那样查询一个字符数组长度需要遍历字符数组，strlen命令获取字符串长度的时间复杂度有N降低到了1.

C字符串不记录自身长度带来的另一个问题就是容易造成缓冲区溢出，即在C语言的语境中合并字符串，是假设字符数组已经有足够的空间，容纳另一个字符数组，但实际上C并不能保证这点。而redis的字符串结构，会在进行相关字符串操作前，使用free检查空间是否足够，不够那么扩容。

减少修改字符串时带来的内存重新分配，即字符串数组不够时，重新分配内存空间，而SDS结构中，可以进行预分配，使得free>len,buf的实际长度不是等于len,而是free+len的长度。

而SDS不会主动删除多余的字符，而是会让free记录不需要的字符长度，这是惰性删除。

二进制安全，C字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符串，会被程序误认为是字符串结尾。这些限制使得C字符串只能保存文本数据。

SDS API都是二进制安全的，因为SDS是使用len判断字符串结尾，而不是使用'\0'字符。

链表

每个链表使用一个adlist.h/listNode结构体表示

typedef struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *value; //节点的值
}

typedef struct list{
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr); //节点值复制函数
    
    void (*free)(void *ptr); //节点值释放函数
    
    int (*match)(void *ptr,void *key); //节点值对比函数
    
}list;

redis的链表有以下特性：

每个节点有双端节点

无环，head的前端节点指向null，tail的后端节点指向null。这点和常规构成环的链表不同。

可以记录链表的长度，len

多态，拥有三个指向不同类型的函数。

字典

redis的字典使用哈希作为底层实现

typedef struct dictht{
    dictEntry **table; //哈希表数组,数组中的每一个元素都是一个指向dictEntry结构的指针
    unsigned long size; //哈希表大小
    unsigned long sizemask; //哈希表大小掩码，用于计算索引值，总是等于size-1
    unsigned long used; //该哈希表已有节点的数量
}dictht;

C里面没有二维数组，所以用指针的指针实现二维数组。

typedef struct dictEntry{
    void *key; //键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    }v; //值，可以是一个指针，也可以是uint64_t整数,int64_t整数
    struct dictEntry *next;//指向下一个哈希表节点，形成链表 ，用于解决哈希冲突的问题
}dictEntry;

图片示例：

typedef struct dict{
    //特定类型函数
    dictType *type;
    void *private;//私有数据
    dictht ht[2];//哈希表
    int trehashidx; //rehash所以，当rehash不进行时，值为-1
}dict ;

typedef struct dictType{
    //计算哈希值的函数
    unsigned int (*hashFunction)(const void* key);
    //复制键函数
    void* (*keyDup)(void *privdata,const void* key);
    //复制值函数
    void* (*valDup)(void *privdata,const void* obj);
    //比较键函数
    void (*keyCompare)(void *privdata,const void *key1,const void *key2);
    //销毁键或值函数
    void (*keyDestructor)(void *privdata,const void *key);
    void (*valDestructor)(void *privdata,const void *obj);
}

ht属性是一个包含两项的数组，数组中的每一个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只进行rehash(再哈希)时使用。

题外话，在C中函数名可以说是一个指针

比如int fun(int x, int y) 和 int *func(int x,int y)是一样的，他们的调用方式是等价的,func(2,3)=*func(2,3)

在 C 语言中，void 被翻译为"无类型"，相应的void * 为"无类型指针"

一个没有进行 再哈希的字典

哈希算法：

redis计算哈希值和索引值的方法如下：

hash=dict->type->hashFunction(key)

index=hash&dict->ht[x].sizemask //使用哈希表的sizemask属性和哈希值，计算索引值

与sizemask进行逻辑且运算是让最后得出的索引值不会超过哈希表的大小。

redis采用的是Murmurhash算法

redis解决键冲突，即键被分配在同一个索引上，方法是采用链地址法，相同索引值的键值对将联成一条链表。

rehash

随着哈希表保存的键值对增加或者减少，为了让哈希表的负载因子维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，程序需要的哈希表进行相应的扩张或者收缩。

步骤大致为三步：

第一步：为ht[1]分配空间

第二步：将ht[0]的键值对迁移到ht[1]中

第三步：将ht[1]改为ht[0],ht[0]改为ht[1]

如果执行的操作是扩展，那么ht[1]的大小为 第一个大于等于 ht[0].used*2=2^n。

如果执行的操作是收缩，那么ht[1]的大小为 第一个大于等于ht[0].used=2^n。

负载因子=ht[0].used/ht[0].size

渐进式rehash

为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]的键值对全部rehash到ht[1]中，而是分多次，渐进式地将ht[0]的键值对慢慢地rehash到ht[1]。

步骤1，为ht[1]分配空间，让字典同时持有ht[0],ht[1]两个哈希表

步骤2 在字典中维持一个索引计数器变量rehashidx,设置值0，表示再哈希正式开始

步骤3，在再哈希期间，每次对字典执行添加，删除，查询，更新操作是，程序除执行指定的操作外，还顺带将ht[0]哈希表在rehashidx索引上的索引键值对Rehash到ht[1]。当rehash工作完成后,程序将rehash属性的值增一。

步骤4，某个时间点，rehashidx值等于最开始的th[0].used，那么代表再哈希工作完成，rehashidx设置值为-1。

步骤5，释放th[0],th[1]代替工作。

在渐进式哈希期间，字典同时使用两个哈希表，如果ht[0]没有找到相应的键值对，去ht[1]上查找。

ht[0]迁移的键值对会空间被释放，新增的键值对在ht[1]

跳跃表

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

跳跃表支持平均 O(logN) ,最坏O(N)的复杂度的节点查询，还可以通过顺序性操作来批处理节点。

跳跃表的效率可以和平衡树媲美，而且实现更加简单。

redis采用跳跃表作为有序集合的底层实现之一。

redis在另一个地方用到跳跃表，实在集群节点中用作内部数据结构。

typedef struct zskiplistNode{
    struct zskiplistLevel{
        struct zskiplistNode *forward; //前进指针
        
        unsigned int span; //跨度
    }level[];
    
    struct zskiplistNode *backward;//后退指针
    
    double score;
    
    robj* obj;
}zskiplistNode;

层

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层快速访问其他节点。

跨度

层的跨度属性用于记录两个节点之间的距离，指向NULL节点的前进指针跨度都是0.

遍历操作只用到前进指针，跨度是用来计算排位的。

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

头节点并不包括在层级和长度里面。

整数集合

整数集合是redis用于保存整数值的集合抽象数据结构，它可以保存类型int16_t,int32_t,int64_t的整数。

typedef struct intset{
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
}intset;

cotents数组是整数集合的底层实现。

压缩列表

压缩列表是redis为了节约内存空间而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。

一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

对象

内容总结

以上是互联网集市为您收集整理的redis学习(十) 数据结构全部内容，希望文章能够帮你解决redis学习(十) 数据结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端