1. ZSet@数据结构

• 能像哈希表一样给定key拿到value

• 能像set一样保证表内单元的唯一性

• 能给每个单元设置一个score, 并按照score做排序

Introduction

想象一下上面的那个链表, 如果这个链表是(按score)排过序的, 那么我们应该怎么做插入呢? 二分法在链表里用不了, 那难道要O(n)遍历吗? Zset提供了一种新思路, 关于在一个有序链表里做快速插入的方法. 一次典型的查找如下图所示:

如上所示, 为了实现快速定位, 我们首先加上了一个head节点, 这个节点的权重是MIN_INT, 永远在链表最前面. 每个节点加上了好几个指针, 指向后面的节点, 越在上面的指针, 指向更靠后面, 值更大的节点

1. 从head节点开始, 拿出指针组从顶点开始向下, 最顶部的指针指向最大的节点, 如果某个节点的值小于新值, 就前往这个节点

2. 从这个节点的指针组, 顶点向下, 遇到的第一个节点, 它的值小于插入的点, 前往, 不停的重复这个过程

3. 将新点插入这个点的后面, 修改底部双向指针

ZSET节点的层高问题

新节点的位置已经找到了, 那么这个新节点应该有几层呢? 每一层的指针应该指向哪儿呢? 插入过程层高表现出了一个非常重要的地位, 正是因为有了高层的指针, 我们才能一次向后跳好几格

我们会先随机出一个层高: 1层100%, 2层50%, 3层25%... , 接下来就是重要的层指针问题, 像下面这样:

ZSET的序号问题

我们还有一个命令叫zrank就是去知道这个节点在整个列表中的排名, 按照刚刚的办法跳点是无法知道这个点的排名的, 我们在每层的指针中新加一个元素, 叫rank指代这个指针能跳多少个节点, 最后跳完了把这些值全部加起来就ok了