我们专注攀枝花网站设计 攀枝花网站制作 攀枝花网站建设
成都网站建设公司服务热线:400-028-6601

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

Redis学习 -- 常用数据结构

二、链表

链表的声明与实现在/src/adlist.h/src/adlist.c

十年的高碑店网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。全网营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整高碑店建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联公司从事“高碑店网站设计”,“高碑店网站推广”以来,每个客户项目都认真落实执行。

//双向链表
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

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

//每个链表使用一个list结构来表示,这个结构带有表头节点指针、表尾节点指针,以及链表长度等信息
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的链表可以用来保存各种不同类型的值

三、字典

字典的声明与实现在src/dict.hsrc/dict.c。字典是redis的底层基础,对数据库的增删改查也是构建在对字典的操作之上的

在源码注释中,字典叫哈希表(hash table),实现了insert/del/replace/find/get-random-element 这些操作,使用链式法处理哈希冲突

重要结构体定义:

  • 哈希表节点实体
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* 同一个篮子的下一个Entry */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
} dictEntry;
  • 类型方法接口
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;
  • 哈希表结构实现
struct dict {
    //dictType 包含了一系列的用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同de
    dictType *type;
    //dictEntry结构保存着一个键值对。通常只使用ht_table[0],只有在对ht_table[0]进行rehash时,才使用ht_table[1]
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    //rehashidx 记录rehash的进度,没有进行rehash时为-1,另外,负载因子设定为1.618,在server.h中定义
    long rehashidx;
    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* size的指数 (size = 1<

四、跳表

跳表是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的,在大部分情况下,跳表的效率可以和平衡树相媲美,并且实现更为简单

Redis使用跳表作为有序集合键的底层实现之一

因还未在源码找到跳表实现,故先跳过

五、整数集合(intset)

intset是redis用来保存整数值的集合抽象数据结构,可以保存类型为int16_tint32_tint64_t的整数值,并且保证集合中不会出现重复元素

该数据结构在intset.h中定义

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

升级

当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,intset需要先进行升级(upgrade),然后才能将新元素添加到intset里面,升级分为三步骤:

  1. 根据新元素类型,扩展intset底层数组的空间大小,并为新元素分配空间。
  2. 将底层数组现有的所有元素转换成与新元素相同的类型,将转换后的元素放在正确的位置上,并且在放置元素时,维持有序
  3. 将新元素添加到底层数组
/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);    //当前编码
    uint8_t newenc = _intsetValueEncoding(value);   //新元素编码
    int length = intrev32ifbe(is->length);   //intrev32ifbe()是一个宏,只有在目标主机是大端序的时候会转换为小端序
    int prepend = value < 0 ? 1 : 0;             //判断元素位置

    /* 修改intset编码并重新分配内存 */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);     

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));   //秒啊,如果prepend为1,前面就会空出来位置放新元素,否则后面空出来

    /* 因为引发升级的新元素总是比该intset的所有元素长度都大,所以要么会放在最开头,要么放在最末尾 */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

压缩列表(ziplist)

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis会使用压缩列表来作为列表键的底层实现


网页题目:Redis学习 -- 常用数据结构
文章URL:http://mswzjz.cn/article/dsoipce.html