SDS ziplist skiplist hashtable
一个SDS结构如下:
struct sdshdr{
int len; //记录保存字符串的长度,也就是buf的长度
int free; //记录数组中未使用字节的数量
char buf[];
}sdshdr
一个双向链表的节点结构如下:
struct listNode{
listNode *pre;
listNode *next;
void *value;
}listNode
整个链表的结构如下:
struct list{
listNode *head; //头结点
listNode *tail; //尾节点
unsigned long len; //链表所含节点数量
void *(*dup)(void *ptr); //节点值赋值函数
void *(*free)(void *ptr); //节点值释放函数
void *(*match)(void *ptr, void *key); //节点值对比函数
}list
字典底层由哈希结构组成,而哈希包含哈希节点,三者的数据定义如下:
//哈希表结构
struct dictht{
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表大小掩码,总是等于size-1
unsigned long used; //该哈希表当前已有节点
}dictht
//哈希节点结构
struct dictEntry{
void *key; //键
union{ //值
void *val;
uint64_tu64;
int64_ts64;
}v;
dictEntry *next; //下一个节点
}dictEntry
//字典结构
struct dict{
dictType *type; //类型特定函数
void *privdata; //私有数据
dictht ht[2]; //两个哈希表,一个用于hash, 一个用于rehash
int rehashidx; //是否正在rehash,如果为-1,说明当前不在进行
}dict
跳表的数据结构比较复杂,可以参考这里
跳表是可以实现二分查找的存储结构,查找效率是O(logn)
整数集合结构如下:
struct intset{
uint32_t encoding; //决定数值类型
uint32_t length; //集合包含的元素数量
int8_t contents[]; //保存元素的数组
}intset
并且数组中的每个项按从小到大有序排列,不含任何重复项
压缩列表的结构如下:
struct ziplist{
unsigned int zlbytes; //压缩列表占用的字节内存数
unsigned int zltail; //压缩列表表尾节点的偏移量:用来倒序遍历压缩列表。
unsigned short zlen; //压缩列表包含的节点数量
zipEntry entry[]; //节点数组,包含元素的具体信息
byte zlend; //一个字节,标志节点结束
}ziplist
struct zipEntry{
previous_entry_length; //记录前一个节点的长度,一般是1字节或者5字节
encoding; //记录值的类型,一般有1字节,2字节,5字节
content; //保存的值,可以是整数或者字符串
}zipEntry