开启生长之旅！这是我参与「日新计划 2 月更文挑战」的第 7 天，点击查看活动详情

导言

---

这篇文章首要聊聊Redis详细功用数据结构的完成，首要针对常用的五种数据结构，string，hash，list，set和zset的完成。

在redis.c:180中存储了Redis支撑一切的指令及其完成函数：

struct redisCommand redisCommandTable[] = {
    {"get",getCommand,2,"r",0,NULL,1,1,1,0,0},
    {"set",setCommand,-3,"wm",0,NULL,1,1,1,0,0},
    {"setnx",setnxCommand,3,"wm",0,NULL,1,1,1,0,0},
    //...
}

第二个属性便是指令的详细完成函数，进入该函数即可阅览相应的指令的详细完成。

在调用详细的指令履行函数前，指令就被拆成一个个参数存放到相应的redisClient.argv中了，比如Redis指令set aaa "aaa"会被拆成数组{"set", "aaa", "aaa"}放在redisClient.argv中。

Redis数据库的真身

---

redisClient结构体中有一个db字段，它是redisDb类型，这个便是该redisClient目前选中的数据库，不论是哪种数据类型，都会调用setKey函数将自己设置进数据库中：

void setKey(redisDb *db, robj *key, robj *val) {
    // 添加或覆写数据库中的键值对
    if (lookupKeyWrite(db,key) == NULL) {
        dbAdd(db,key,val);
    } else {
        dbOverwrite(db,key,val);
    }
    //...
}
void dbAdd(redisDb *db, robj *key, robj *val) {
    //....
    int retval = dictAdd(db->dict, copy, val);
    //...
 }

发现其实便是在往redisDb的dict字典中参加kv，dict便是Redis自己完成的字典结构，其完成相似于高档语言中的hashmap，可见一个Redis数据库本质便是一个大字典，当你创立的不同的数据结构时，本质上都是在往这个大字典中写入kv。从setKey的签名能够看出，这个大字典中的每一个key和value都是robj类型，这是个什么东西呢？

redisObject

---

robj其实是redisObject的简称：

typedef struct redisObject {
    // 类型
    unsigned type:4;   // 4 bit 位域
    // 编码 （底层数据结构类型）
    unsigned encoding:4;
    // 对象最后一次被拜访的时刻
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 指向实际值的指针  指向底层完成数据结构
    void *ptr;
} robj;

类型type代表了该robj对用户露出的类型，便是导言中说的五种类型：

数据类型	type的值
string	REDIS_STRING
list	REDIS_LIST
hash	REDIS_HASH
set	REDIS_SET
zset	REDIS_ZSET

而encoding代表底层实际使用的数据结构类型，而详细的底层数据结构完成存储在ptr字段中。

底层数据结构

---

底层数据结构是指不对用户露出，只是作为底层完成的一些数据结构，Redis有如下的底层数据结构：

• long：便是C语言中一般的long类型，当字符串能够编码成long类型的数字时，会采用这种结构
• sds：便是Redis中的字符串类型
  • 一切的key的底层数据结构都是它
  • 字符串的底层数据结构，根据其内存摆放特色又有两种
    • raw：一般的sds
    • embstr：内存中位置紧跟在相应的redisObject后面，能够和redisObject一同分配与开释
• dict：Redis自己完成字典，除了用于完成Redis内部的功用外，还用于hash和set的底层数据结构
• ziplist：在内存中连续摆放的一个列表结构，能够存储字符串或许数字，和其他结构不一样的当地是，在代码中没有详细的结构体来表示，只要一些宏能够从代表ziplist的byte串获得详细属性的值，redis.c:246。
  • 是list, hash和zset数据结构的默许完成
  • 虽然是一个紧凑的数据结构，但却无法像数组一样随机拜访，各种操作的时刻复杂度和链表相似，在查询时需求一个一个元素往下走
  • 该编码相对比较复杂，网上有许多文章解说，这里就不专门介绍了
• list：Redis自己完成的一个双向链表，可用于list的底层数据结构
• intset：整数调集，其实便是个从小到大摆放的整数数组，假如set中一切的元素都是数字的话，能够用于set的底层数据结构
• skiplist：跳表，能够和dict一同用于zset的底层数据结构，其间dict用于按成员取分值，而skiplist担任按分值取成员。

下面逐个经过图示五种数据结构是怎么在上面这7种底层数据结构中作选择的。

string

---

set msg "hello"
set number 12235

hash

---

hset o1 f1 "aaa"

list

---

lpush languages python

set

---

sadd names "Lily"

zset

---

zadd page_rank 10 google.com

在使用ziplist作为底层数据结构时，score是以字符串的方式编码在里面，详细为什么要这么做，我也比较困惑，ziplist自身是支撑存数字的。

这个skiplist + dict的结构其实是zset结构体：

typedef struct zset {
    // 字典，键为成员，值为分值
    // 用于支撑 O(1) 复杂度的按成员取分值操作
    dict *dict;
    // 跳动表，按分值排序成员
    // 用于支撑平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及规模操作
    zskiplist *zsl;
} zset;

其间dict首要用于支撑像zscore这样的按成员取分值的操作，而zsl跳动表首要用于支撑像zrange这样的依照分数取成员的操作。

End

---

作者：元青

微信大众号 「技乐书香」