redis基本数据结构(1)

23ed

　　redis的作者为了方便自己的使用，在redis中定义了动态字符串sds，链表，字典dict，跳跃表skiplist，整数集合intset和压缩列表ziplist这六种数据结构。下文，我简要地介绍一下几种数据结构的定义。
动态字符串sds
　　sds的全称叫simple dynamic string，它的定义和注释如下

struct sdshdr {
//buf数组中已使用的空间的长度
unsigned int len;
//buf数组中未使用的空间的长度
unsigned int free;
//用于保存字符串
char buf[];
};
　　使用sds有这样几个好处

1.  空间惰性释放：因为len和free记录了buf的长度，所以当我们释放掉一个旧的字符串的时候，可以用free来记录下buf的长度，当下次要用新的字符串的时候，可以直接使用。

2.  空间预分配：在初始化阶段可以分配比需要的更多的空间，并把大小存储在free里，需要的时候就不用重新分配新的空间了。

3.  缓冲区安全：因为已经记录了buf的长度，所以不会出现溢出的问题。

4.  快速：获得字符串长度的功能的时间复杂度缩减到了O(1)。

5.  二进制安全且兼容部分C风格字符串的表达：由于C风格的字符串以’\0’结尾来表示字符串的末尾，所以它并不是二进制安全的，sds的字符串长度是按照len属性的值来规定的，对所有字符都一视同仁。但是，sds为了兼容C的输出，默认会在字符串末尾加上’\0’。
链表
　　redis的链表就是一个普通的双向链表，额外的是redis为一条链表构造了一个list结构体，里面存储了这个链表的基本信息

typedef struct listNode {
struct listNode *prev;//前一个节点
struct listNode *next;//后一个节点
void *value;
} listNode;
typedef struct list {
listNode *head;//链表头
listNode *tail;//链表尾
void *(*dup)(void *ptr);//节点复制函数
void (*free)(void *ptr);//节点释放函数
int (*match)(void *ptr, void *key);//节点对比函数
unsigned long len;//链表节点数量
} list;

整数集合intset
　　如果集合里全是整数，那么就可以用intset来存储集合里的所有整数。

typedef struct intset {
uint32_t encoding;//编码类型，int16_t，int32_t等
uint32_t length;//包含的元素数量
int8_t contents[];//存储的元素数组
} intset;
　　contents里的元素是从小到大按序排列的，如果原来数组的编码类型是int16_t，而新存入的数要大于或者小于int16_t的取值范围的话，编码的类型就会从int16_t提升到更大的范围，如果原来的contents数组的大小不够的话，就需要重新申请空间。

版权声明：本文为博主原创文章，未经博主允许不得转载。