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;
来源: http://www.bubuko.com/infodetail-3350228.html