有序集合有两种编码方式:压缩列表 ziplist 和跳表 skiplist。

有序集合 sorted set (下面我们叫zset 吧) 有两种编码方式:压缩列表 ziplist 和跳表 skiplist

zsetziplist 中,成员(member)和分数(score)是挨在一起的,元素按照分数从小到大存储。

举个例子,我们用以下命令创建一个zset

  1. redis ZADD key 26.1 z 1 a 2 b
  2. (integer) 3

那么这个zset的结构大致如下:


下面我们来分析一下 zscore 命令的源码,进一步了解 zset 是如何利用 ziplist 存储的

  1. int zsetScore(robj *zobj, sds member, double *score) {
  2. // ...
  3. if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
  4. if (zzlFind(zobj->ptr, member, score) == NULL) return C_ERR;
  5. }
  6. // ...
  7. return C_OK;
  8. }
  9. unsigned char *zzlFind(unsigned char *zl, sds ele, double *score) {
  10. // eptr 是 member 的指针,sptr 是 score 的指针
  11. unsigned char *eptr = ziplistIndex(zl,0), *sptr;
  12. // 遍历 ziplist
  13. while (eptr != NULL) {
  14. // 因为 member 和 score 是挨着存储的,所以获取 member 的下一个节点就是 score 啦
  15. sptr = ziplistNext(zl,eptr);
  16. serverAssert(sptr != NULL);
  17. // 对比当前的 member 和要查询的 member 是否相等
  18. if (ziplistCompare(eptr,(unsigned char*)ele,sdslen(ele))) {
  19. // 如果相等,则获取分数
  20. if (score != NULL) *score = zzlGetScore(sptr);
  21. return eptr;
  22. }
  23. // 不相等则继续往下遍历
  24. eptr = ziplistNext(zl,sptr);
  25. }
  26. return NULL;
  27. }
  28. // 获取分数
  29. double zzlGetScore(unsigned char *sptr) {
  30. unsigned char *vstr;
  31. unsigned int vlen;
  32. long long vlong;
  33. char buf[128];
  34. double score;
  35. serverAssert(sptr != NULL);
  36. // ziplistGet 通过 sptr 指针获取值。根据节点的编码(前文有说到ziplist节点的编码) 对参数赋值
  37. // 如果是字符串,则赋值到 vstr; 如果是整数,则赋值到 vlong。
  38. serverAssert(ziplistGet(sptr,&vstr,&vlen,&vlong));
  39. if (vstr) {
  40. // 如果是字符串,那么存的就是浮点数
  41. memcpy(buf,vstr,vlen);
  42. buf[vlen] = \'\0\';
  43. // 字符串转换成浮点数
  44. score = strtod(buf,NULL);
  45. } else {
  46. // 整数类型就直接赋值
  47. score = vlong;
  48. }
  49. return score;
  50. }

skiplist 编码的底层实现是跳表。

下面是跳表的结构图 (图片来自 《Redis 设计与实现》图片集 )

  1. 图中最左部分就是 zskiplist 结构,其代码实现如下(server.h):
  1. typedef struct zskiplist {
  2. // 头指针和尾指针,指向头尾节点
  3. struct zskiplistNode *header, *tail;
  4. // 跳表的节点数(不包含头结点,空跳表也会包含头结点)
  5. unsigned long length;
  6. // 所有节点中,最大的层数
  7. int level;
  8. } zskiplist;
  1. 图中右边的四个节点,就是跳表节点 zskiplistNode,其代码实现如下(server.h):
  1. typedef struct zskiplistNode {
  2. // 成员
  3. sds ele;
  4. // 分数
  5. double score;
  6. // 后退指针,指向前一个节点
  7. struct zskiplistNode *backward;
  8. // 层,每个节点可能有很多层,每个层可能指向不同的节点
  9. struct zskiplistLevel {
  10. // 前进指针,指向下一个节点
  11. struct zskiplistNode *forward;
  12. // 跟下一个节点之间的跨度
  13. unsigned long span;
  14. } level[];
  15. } zskiplistNode;

跳表最重要的一个地方就是层 level,为什么这么说呢?

假设zset 用链表有序存储,如果我们要查找数据,只能从头到尾遍历,时间复杂度是 \(O(n)\),效率很低。
链表

有什么办法提高效率呢?我们可以在上面添加一层索引。
链表加索引
可以看出,我们遍历的性能变高了。例如我们想找到 6,先遍历第一层,5 到 7 之间,再往下探,就能找到 6 了!
有读者就发现了,如果数据量很大,那找起来也很慢。
是的,那么怎么解决呢?再往上加索引呗!
链表再加几层索引
这不,链表就变成了跳表了!而上面说的层,就是这些索引啦!最终跳表的查找时间复杂度是 \(O(logn)\)


我们来看看 zrange 命令的核心实现,来感受一下跳表的遍历吧

  1. zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {
  2. zskiplistNode *x;
  3. unsigned long traversed = 0;
  4. int i;
  5. // 层头结点开始
  6. x = zsl->header;
  7. // 层从高到低
  8. for (i = zsl->level-1; i >= 0; i--) {
  9. // 只要遍历的数没有达到 rank,就一直遍历
  10. while (x->level[i].forward && (traversed + x->level[i].span) <= rank)
  11. {
  12. // 每次加上层的跨度
  13. traversed += x->level[i].span;
  14. // 往前走
  15. x = x->level[i].forward;
  16. }
  17. // 如果这一层走完还没到 rank,那就往下层走,如果还是找不到就继续走,直到走到最底层
  18. if (traversed == rank) {
  19. return x;
  20. }
  21. }
  22. return NULL;
  23. }

skiplist 编码的 zset 的结构定义如下:

  1. typedef struct zset {
  2. dict *dict;
  3. zskiplist *zsl;
  4. } zset;

结构中包含了一个字典和一个跳表,为什么用了跳表还需要字典呢?
命令zscore这种单找一个值的,如果只用跳表的话,那么查找的时间复杂度是 \(O(logn)\),加上一个字典可以把时间复杂度缩减为 \(O(n)\)

那么肯定有同学就会说,加一个字典会浪费了很多空间。
的确,多加一个字典肯定会多占用一定的空间,空间换时间是一种常见的做法。不过字典的值指向的对象跟跳表的对象是共用的。

下图是一个 zset 的示例,为了方便,把他们指向的字符串对象都分别画出来了,实际上是共享的。(图片来自 《Redis 设计与实现》图片集 )

我们来看看 skiplist 编码下的 zscore 如何实现吧。

  1. int zsetScore(robj *zobj, sds member, double *score) {
  2. // 前面其他 ziplist 编码的就省略了...
  3. // if ...
  4. else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
  5. zset *zs = zobj->ptr;
  6. // 直接通过 dict 查找,时间复杂度复杂度 O(1)
  7. dictEntry *de = dictFind(zs->dict, member);
  8. if (de == NULL) return C_ERR;
  9. *score = *(double*)dictGetVal(de);
  10. }
  11. // ...
  12. return C_OK;
  13. }

当有序集合对象可以同时满足以下两个条件时,对象使用 ziplist 编码:

  • 有序集合保存的元素数量小于128个(可通过 zset-max-ziplist-entries 修改配置);
  • 有序集合保存的所有元素成员的长度都小于64字节(可通过 zset-max-ziplist-value 修改配置);

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

版权声明:本文为chenchuxin原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/chenchuxin/p/14284737.html