1,Redis 的数据结构
Redis 的底层数据结构包含简单的动态字符串 (SDS), 链表, 字典, 压缩列表, 整数集合等等; 五大数据类型(数据对象) 都是由一种或几种数结构构成.
在命令行中可以使用 OBJECT ENCODING key 来查看 key 的数据结构.
2, 简单动态字符串 SDS
Redis 是使用 C 语言编写的, 但是 string 数据类型并没有使用 C 语言的字符串, 而是重新编写一个简单的动态字符串(simple dynamic string,SDS).
- /*
- * 保存字符串对象的结构
- */
- struct sdshdr {
- // buf 中已占用空间的长度
- int len;
- // buf 中剩余可用空间的长度
- int free;
- // 数据空间
- char buf[]
- };
使用 SDS 保存字符串 Redis, 具体表示如下:
图片来自《Redis 设计与实现》 黄健宏著
free 表示 buf 数组中剩余的空间数量
len 记录了 buf 数组中已存储的字节长度
buf 数组是一个 char 类型的数据, 记录具体存储的字符串, 并且以 '\0'(空字符) 作为结束标识符
SDS 定义较 C 语言的字符串几乎相同, 就是多出两个属性 free,len; 那为何不直接使用 C 语言的字符串呢?
1, 获取字符串长度复杂度为 O(1)
由于 C 语言没有存储字符串长度, 每次获取字符串长度多需要进行循环整个字符串计算, 时间复杂度为 O(N); 而 SDS 记录了存储的字符串的长度, 获取字符串长度时直接获取 len 的属性值即可, 时间复杂度为 O(1); 而 SDS 中设置和更新长度是 API 中自动完成, 无需手动进行操作.
2, 杜绝缓冲区溢出
C 语言在进行两个字符串拼接时, 一旦没有分配足够的内存空间, 就会造成溢出; 而 SDS 在修改字符串时, 会先根据 len 的值, 检查内存空间是否足够, 如果不足会先分配内存空间, 再进行字符串修改, 这样就杜绝了缓冲区溢出.
3, 减少修改字符串时带来的内存重新分配次数
C 语言不记录字符串长度, 所以当修改时, 会重新分配内存; 如果是正常字符串, 内存空间不够会产生溢出; 如果是缩短字符串, 不重重分配会产生泄露.
SDS 采用空间预分配和惰性释放空间两种优化策略
空间预分配: 对字符串进行增长操作, 会分配出多余的未使用空间, 这样如果以后的扩展, 在一定程度上可以减少内存重新分配的次数.
惰性释放空间: 对字符串经过缩短操作, 并不会立即释放这些空间, 而是使用 free 来记录这些空间的数量, 当进行增长操作时, 这些记录的空间就可以被重新利用; SDS 提供了响应的 API 进行手动释放空间, 所以不会造成内存浪费.
4, 二进制安全
C 语言的字符串中不能包含空字符(因为 C 语言是以空字符判断字符串结尾的), 所以不能保存一些二进制文件(有可能包含空字符, 如图片);SDS 则是以 len 来判断字符串结尾, 所以 SDS 结构可以存储图片等, 并且都是以二进制方式进行处理.
5, 兼容部分 C 字符串函数
SDS 结构中 buf 保存字符串同样是以空字符结尾, 所以可以兼容 C 语言的部分字符串操作 API.
总结:
typedef struct listNode { // 前置节点 struct listNode * prev; // 后置节点 struct listNode * next; // 节点的值 void * value; }listNode;
typedef struct list { // 表头节点 listNode * head; // 表尾节点 listNode * tail; // 链表所包含的节点数量 unsigned long len; // 节点值复制函数 void *(*dup)(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;
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时, 值为 - 1 in trehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; typedef struct dictType { // 计算哈希值的函数 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType;
# 使用字典设置的哈希函数, 计算键 key 的哈希值 hash = dict->type->hashFunction(key); #使用哈希表的 sizemask 属性和哈希值, 计算出索引值 #根据情况不同, ht[x]可以是 ht[0]或者 ht[1] index = hash & dict->ht[x].sizemask;
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;
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; } intset;
来源: https://www.cnblogs.com/MouseDong/p/11133941.html