Redis基础(一)数据结构与数据类型

Redis数据结构

Redis一共有六种数据结构,分别是简单动态字符串、链表、字典、跳表、整数集合、压缩列表。

简单动态字符串(SDS)

Redis只会使用C字符串作为字面量,在大多数情况下,Redis使用SDS(Simple Dynamic String,简单动态字符串)作为字符串表示。

SDS的数据结构:

struct sdshdr {
    // 记录buf数据中已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;
    
    // 记录buf数组中未使用字节的数量
    int free;;
    
    // 字节数组,用于保存字符串
    char buf[];
}

image

比起C字符串,SDS具有以下优点:

  • 常数复杂度获取字符串长度
  • 杜绝缓冲区溢出
  • 减少修改字符串时带来的内存重分配次数
  • 二进行安全
  • 兼容部分C字符串函数

链表(list)

链表的数据结构:

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

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;

image

  • 链表被广泛用于实现Redis的各种功能,比如列表键、发布与订阅、慢查询、监视器等。
  • 每个链表节点由一个listNode结构来表示,每个节点都有一个指向前置节点和后置节点的指针,所以Redis的链表实现是双端链表。
  • 每个链表使用一个list结构来表示,这个结构带有表头节点指针、表尾节点指针,以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL,所以Redis的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数,Redis的链表可以用于保存各种不同类型的值。

字典(dict)

字典的数据结构:

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

typedef struct dictEntry {
    // 键
    void *key;
    
    // 值
    union {
        void *val;
        uint64_tu64;
        int64_ts64;
    }v;
    
    // 指向下一个哈希表节点,形成键表
    struct dictEntry *next;
}dictEntry;

typedef struct dict {
    // 类型特定函数
    dictType *type;
    
    // 私有数据
    void *privdate;
    
    // 哈希表
    dictht ht[2];
    
    // rehash索引
    // 当rehash不在进行时,值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -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);
    
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
}dictType;

image

  • 字典被广泛用于实现Redis的各种功能,其中包括数据库和哈希键。
  • Redis中的字典使用哈希表作为底层实现,每个字典带有两个哈希表,一个平时使用,另一个仅在进行rehash时使用。
  • 当字典被用作数据库的底层实现,或者哈希键的底层实现时,Redis使用MurmurHash2算法来计算键的哈希值。
  • 哈希表使用键地址法来解决键冲突,被分配到同一个索引上的多个键值对会连接成一个单向链表。
  • 在对哈希表进行扩展或者收缩操作时,程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面,并且这个rehash过程并不是一次性地完成的,而是渐进式地完成的。

跳表(skiplist)

跳表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳表查询的时间复杂度O(logN)、最坏情况是O(N),还可以通过顺序操作来指处理节点。

跳表的数据结构:

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

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    
    // 表中节点数量
    unsigned long length;
    
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

image

  • 跳表是有序集合的底层实现之一。
  • Redis的跳表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳表信息(比如表头节点、表尾节点、长度),而zskiplistNode则用于表示跳表节点。
  • 每个跳表节点的层高都是1至32之间的随机数。
  • 在同一个跳表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。
  • 跳表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。

整数集合(intset)

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。

整数集合的数据结构:

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

image

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组,这个数组以有序、无重复的方式保存集合元素,在有需要时,程序会根据新添加元素的类型,改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存。
  • 整数集合只支持升级操作,不支持降级操作。

压缩列表(ziplist)

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

image

  • 压缩列表是一种为节约内存而开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高。

Redis数据类型

Redis中,键的数据类型是字符串,但提供了丰富的数据存储方式,方便开发者使用,值的数据类型有很多,常用的数据类型有五种,分别是字符串(string)、列表(list)、字典(hash)、集合(set)、有序集合(sortedset)。

字符串(string)

“字符串(string)”这种数据结构类型非常简单,对应到数据结构里,就是Redis里的简单动态字符串(SDS)。

列表(list)

列表这种数据类型支持存储一组数据。这种数据类型对应两种实现方法,一种是压缩列表(ziplist),另一种是双向循环链表。

当列表中存储的数据量比较小的时候,列表就可以采用压缩列表的方式实现。具体需要同时满足下面两个条件:

  • 列表中保存的单个数据(有可能是字符串类型的)小于64字节;
  • 列表中数据个数少于512。

字典(hash)

字典类型用来存储一组数据对。每个数据对又包含键值两部分。字典类型也有两种实现方式。一种是压缩列表,另一种是散列表。

同样,只有当存储的数据量比较小的情况下,Redis才使用压缩列表来实现字典类型。具体需要满足两个条件:

  • 字典中保存的键和值的大小都要小于64字节;
  • 字典中键值对的个数要小于512个。

集合(set)

集合这种数据类型用来存储一组不重复的数据。有两种实现方式:一种是基于有序数组,另一种是基于散列表。

当要存储的数据,同时满足下面这样两个条件的时候,Redis就采用有序数组,来实现集合这种数据类型。

  • 存储的数据都是整数;
  • 存储的数据元素个数不超过512个。

有序集合(sortedset)

有序集合用来存储一组数据,并且每个数据会附带一个得分。通过得分的大小,我们将数据组织成跳表这种数据结构,以支持快速地按照得分值、得分区间获得数据。

有序集合也有两种实现方式:跳表和压缩列表。使用压缩列表来实现有序集合的前提:

  • 所有数据的大小都要小于64字节;
  • 元素个数要小于128个。

参考资料

Tags: