有序集合对象
有序集合的对象的编码可以为ziplist或者skiplist
ziplist实现有序集合
当满足下面两个条件时,有序集合的底层数据结构为skiplist
1. 元素数量小于128个
2. 所有元素成员的长度都小于64字节
ziplist编码的有序集合使用两个连续的节点来表示键值对,第一个保存成员,第二个保存分值,按分值从小到达排列
创建一个ziplist编码的有序集合对象的函数如下
robj *createZsetZiplistObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(REDIS_ZSET,zl);
o->encoding = REDIS_ENCODING_ZIPLIST;
return o;
}
举个例子,如执行下列命令
ZADD price 8.5 apple 5.0 banana 6.0 cherry
则内存布局如下图
skiplist实现有序集合
其实时同时用skiplist 和 dict 实现有序集合
结构体如下
typedef struct zset {
// 字典,键为成员,值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表,按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;
创建函数如下
robj *createZsetObject(void) {
zset *zs = zmalloc(sizeof(*zs));
robj *o;
zs->dict = dictCreate(&zsetDictType,NULL);
zs->zsl = zslCreate();
o = createObject(REDIS_ZSET,zs);
o->encoding = REDIS_ENCODING_SKIPLIST;
return o;
}
为什么要同时使用skiplist和dict来实现呢?
因为dict可以实现O(1)的查找,但是dict存储数据时无序的,在执行范围操作时需要排序复杂度为O(NlogN),而skiplist为顺序结构,在实现范围操作时只需O(N)节省了时间。
skiplist和dict会使用指针来共享相同元素的成员和分值
,因而并不会造成很大的内存浪费,而大大提高了时间效率
执行之前的命令后,用skiplist实现的有序集合的内存布局如下图
上图中重复了成员和分值,但实际会通过指针来共享成员和分值
小节
有序集合可以用ziplist或者(skiplist + dict)来实现,ziplist因为的连续内存,不能太长,用来存储小字符串和小整数。 skiplist配合dict,利用了dict O(1)查找的优势和skiplist有序的优势,有因为共享了相同元素的成员和分值而不造成内存浪费
到这里基本所有的数据结构实现源码都读完了,要开始分析数据库实现了