Redis学习 -- 常用数据结构

二、链表

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

//双向链表
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.h、src/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<<exp) */
};

四、跳表

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

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

• 还没有人评论，欢迎说说您的想法！

相关课程

C++ 匠心之作 从0到1入门学编程

3818 9.8元

SpringMvc视频教程

5233 1元

云知梦-CSS3样式设计

2778 0元 限免