1 引言【一 Redis数据结构-Redis的数据存储及String类型的实现】Redis作为基于内存的非关系型的K-V数据库 。因读写响应快速、原子操作、提供了多种数据类型String、List、Hash、Set、Sorted Set、在项目中有着广泛的使用,今天我们来探讨下下Redis的数据结构是如何实现的 。
2 数据存储2.1 RedisDBRedis将数据存储在redisDb中,默认0~15共16个db 。每个库都是独立的空间,不必担心key冲突问题,可通过select命令切换db 。集群模式使用db0
typedef struct redisDb {dict *dict; /* The keyspace for this DB */dict *expires; /* Timeout of keys with a timeout set */...} redisDb;
- dict:数据库键空间,保存着数据库中的所有键值对
- expires:键的过期时间,字典的键为键,字典的值为过期事件UNIX时间戳
K-V存储我们最先想到的就是map,在Redis中通过dict实现,数据结构如下:
typedef struct dict {dictType *type;void *privdata;dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */unsigned long iterators; /* number of iterators currently running */} dict;
- type:类型特定函数是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数 。
- privdata:私有数据保存了需要传给那些类型特定函数的可选参数
- ht[2]:哈希表一个包含两个项的数组,数组中的每个项都是一个dictht哈希表,一般情况下,字典只使用ht[0] 哈希表,ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
- rehashidx:rehash 索引,当rehash不在进行时,值为 -1
- 任意相同的输入一定能得到相同的数据
- 不同的输入,有可能得到相同的输出
typedef struct dictType {uint64_t (*hashFunction)(const void *key);int (*keyCompare)(void *privdata, const void *key1, const void *key2);...} dictType;
- hashFunction:用于计算key的hash值的方法
- keyCompare:key的值比较方法
dict.h/dictht表示一个哈希表,具体结构如下:
typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;} dictht;
- table:数组指针,数组中的每个元素都是一个指向dict.h/dictEntry结构的指针,每个dictEntry结构保存着一个键值对 。
- size:记录了哈希表的大小,也就是table数组的大小,大小总是2^n
- sizemask:总是等于size - 1,这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面 。
- used:记录了哈希表目前已有节点(键值对)的数量 。
typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;} dictEntry;
- key:保存着键值对中的键(SDS类型对象)
- val:保存着键值对中的值,可以是一个uint64_t整数,或者是一个int64_t整数,又或者是一个指针指向一个被redisObject包装的值
- next:指向下个哈希表节点,形成链表指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一次,以此来解决键冲突(collision)的问题
经验总结扩展阅读
- 2023过小年能贴春联吗 春联一般什么时候贴
- 抖音带货达人是真的吗
- 洗脸巾执行标准GB和Q哪个好 一次性洗脸巾怎么挑选
- 给灶王爷上香每月的初一十五吗 给灶王爷上香是早上还是晚上
- 2023年货节发货快吗 年货节一般是什么时候
- 太平洋车险和平安车险哪个好一些 各有各的优势
- 1一5儿童玩具批发市场在哪里
- 7月15烧纸是提前还是当天呢 7月15一般几点烧纸
- 2023暑期出行求财哪一天最好 暑假适合出行求财的日子有哪
- 2022年哪一天立冬 2022年立冬时间是几月几号