怎样实现键值对数据库

Redis 是 key-value 存储系统

• key 一般都是 String 类型的字符串对象

• value 类型则为 Redis 对象（redisObject）

  value 可以是字符串对象，也可以是集合数据类型的对象，比如 List 对象、Hash 对象、Set 对象和 Zset 对象。

10 大类型说明（粗分）

• 传统的 5 大类型
  • String
  • List
  • Hash
  • Set
  • ZSet
• 新介绍的 5 大类型
  • bitmap（实质 String）
  • hyperLogLog（实质 String）
  • GEO（实质 Zset）
  • Stream（实质 Stream）
  • BITFIELD（看具体 key）

Redis 结构图

DictEntry 和 RedisObject

Redis 用 C 语言定义了 redisObject 结构体来表示 string、hash、list、set、zset 等数据类型；Redis 中每个对象都是一个 redisObject 结构。

字典、KV 是什么

每个键值对都会有一个 dictEntry

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
};

dictEntry 表示哈希表节点的结构。存放 void *key 和 void *value 指针。

*key 指向 String 对象，*value 既能指向 String 对象也能指向集合类型的对象（比如 List、Hash、Set 和 ZSet 对象）

备注：void *key 和 void *value 指针指向的是内部抽象的 Redis 对象，Redis 中的每个对象都由 redisObject 构成。底层数据结构是 SDS、双向链表、压缩列表、哈希表、跳表、整数集合等。

从 set hello world 说起

set hello world 为例，因为 Redis 是 KV 键值对的数据拉，每个键值对都会有一个 dictEntry（源码位置：dict.c），里面指向了 key 和 value 的指针，next 指向下一个 dictEntry。key 是字符串，但是 Redis 没有直接使用 C 的字符数组，而是存储在 Redis 自定义的 SDS 中。

value 即不是直接作为字符串存储，也不是直接存储在 SDS 中，而是存储在 redisObject 中。实际上五种常用的数据类型的任何一种，都是通过 redisObject 来存储的。

类型

type 键

编码

object encoding hello

Redis 字典数据库结构图

Redis 键值对的保存和读取都是 O(1) 复杂度。

从 RedisObject 到编码

redisObject + Redis 数据类型 + Redis 所有编码方式（底层实现）三者之间的关系

RedisObject 的作用

为了便于操作，Redis 采用 redisObject 结构来统一五种不同的数据类型，这样所有的数据类型就都就可以以相同的形式在函数间传递而不用使用特定的类型结构。同时，为了识别不同的数据类型，redisObjec 中定义了 type 和 encoding 字段对不同的数据类型加以区别。简单地说，redisObjec 就是 string、hash、list、set、zset 的父类，可以在函数间传递时隐藏具体的类型信息，所以作者抽象了 redisObject 结构来到达同样的目的。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr; // 指向底层数据
} robj;

• type：对象的类型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET 等等
• encoding：具体的数据结构
• lru:LRU_BITS：24 位，对象最后一次被命令程序访问的时间，与内存回收有关
• refcount：引用基数。当 refcount 为 0 的时候，表示该对象已经不被任何对象引用，则可以进行垃圾回收
• *ptr：指向真正的底层数据结构的指针

案例

set age 17