一、简单动态字符串(SDS)
SDS通过使用一个结构如下:
struct sdshdr {
int len;
int free;
char buf[];
};
len是字符串长度,free是缓存区中的剩余大小,通过使用len记录字符串的长度,可以快速的实现字符串的长度获取,并且可以避免复制相关的操作的溢出。利用free实现对字符串存储空间的预分配和惰性释放,来实现高效的字符串的相关操作,避免了可能产生的过于频繁的内存申请和释放操作。为了兼容一部分字符操作的函数,ssd的结尾仍然以\0结束。
二、链表
redis中以listNode结构实现实现双向无环链表,使用void* 类型保存节点值,从而实现链表保存值的多态特性,可以单个链表中保存多个类型的值。
三、字典
redis 的字典使用哈希表作为低层实现,每个哈希表里面有多个节点,每个节点保存一个键值对。键用void* 类型的key,而值部分使用union类型,可以是一个void *指针,或者是64的有(无)符号数。
对于实现数据库低层和哈希键低层时,使用murmurHash2算法计算hash值,使用链地址法解决冲突,并使用rehash的方式,完成hash表的扩展或收缩。