redis基本数据结构(1)

来源:转载


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数组的大小不够的话,就需要重新申请空间。



分享给朋友:
您可能感兴趣的文章:
随机阅读: