string,list,hash,set,zset
sds
struct sdshdr{ //等于 SDS 保存字符串的长度 int len; //记录 buf 数组中未使用字节的数量 int free; //字节数组,用于保存字符串 char buf[]; }
而对于SDS,由于len属性和free属性的存在,对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略:
1、空间预分配:对字符串进行空间扩展的时候,扩展的内存比实际需要的多,这样可以减少连续执行字符串增长操作所需的内存重分配次数。
2、惰性空间释放:对字符串进行缩短操作时,程序不立即使用内存重新分配来回收缩短后多余的字节,而是使用 free 属性将这些字节的数量记录下来,等待后续使用。(当然SDS也提供了相应的API,当我们有需要时,也可以手动释放这些未使用的空间。)
typedef struct listNode{ //前置节点 struct listNode *prev; //后置节点 struct listNode *next; //节点的值 void *value; }listNode
typedef struct list{ //表头节点 listNode *head; //表尾节点 listNode *tail; //链表所包含的节点数量 unsigned long len; //节点值复制函数 void (*free) (void *ptr); //节点值释放函数 void (*free) (void *ptr); //节点值对比函数 int (*match) (void *ptr,void *key); }list;
typedef struct dictht{ //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码,用于计算索引值 //总是等于 size-1 unsigned long sizemask; //该哈希表已有节点的数量 unsigned long used; }dictht
typedef struct dictEntry{ //键 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; }v; //指向下一个哈希表节点,形成链表 struct dictEntry *next; }dictEntry
注意这里还有一个指向下一个哈希表节点的指针,我们知道哈希表最大的问题是存在哈希冲突,如何解决哈希冲突,有开放地址法和链地址法。这里采用的便是链地址法,通过next这个指针可以将多个哈希值相同的键值对连接在一起,用来解决哈希冲突。
Redis中跳跃表节点定义如下:
typedef struct zskiplistNode { //层 struct zskiplistLevel{ //前进指针 struct zskiplistNode *forward; //跨度 unsigned int span; }level[]; //后退指针 struct zskiplistNode *backward; //分值 double score; //成员对象 robj *obj; } zskiplistNode
多个跳跃表节点构成一个跳跃表:
typedef struct zskiplist{ //表头节点和表尾节点 structz skiplistNode *header, *tail; //表中节点的数量 unsigned long length; //表中层数最大的节点的层数 int level; }zskiplist;
大多数情况下,Redis使用简单字符串SDS作为字符串的表示,相对于C语言字符串,SDS具有常数复杂度获取字符串长度,杜绝了缓存区的溢出,减少了修改字符串长度时所需的内存重分配次数,以及二进制安全能存储各种类型的文件,并且还兼容部分C函数。 通过为链表设置不同类型的特定函数,Redis链表可以保存各种不同类型的值,除了用作列表键,还在发布与订阅、慢查询、监视器等方面发挥作用。 Redis的字典底层使用哈希表实现,每个字典通常有两个哈希表,一个平时使用,另一个用于rehash时使用,使用链地址法解决哈希冲突。 跳跃表通常是有序集合的底层实现之一,表中的节点按照分值大小进行排序。 压缩列表是Redis为节省内存而开发的顺序型数据结构,通常作为列表键和哈希键的底层实现之一。