跳跃表
Redis的zset是一个复合结构,一方面需要一个hash结构来存储value和score的对应关系,另一方面需要提供按照score排序的功能,还需要能够指定score的范围来获取value列表的功能,这就需要另一个结构“跳跃列表”。
zset的内部实现是一个hash字典加一个跳跃列表。
基本机构
Redis的跳跃列表公有64层,容纳2^64个元素不成问题。每一个kv块对应的结构zslnode结构,kv header也是这个结构,只不过value字段时NULL值——无效的,score是Double.MIN_VALUE,用来垫底的。kv之间使用指针串起来形成了双向链表结构,它们是有序排列的,从小到大。不同的kv层高可能不一样,层数越高的kv越少,同一层的kv会使用指针串起来。每一个层元素的遍历都是从kv header出发
struct zslnode {
string value;
double score;
zslnode*[] forwards; // 多层连接指针
zslnode* backward; // 回溯指针
}
struct zslforward {
zslnode* item;
long span; //跨度
}
struct zsl {
string value;
double score;
zslforward*[] forwards; // 多层连接指针
zslnode* backward; // 回溯指针
}
查找过程
我们要定位到那个紫色的kv,需要从header的最高层开始遍历找到第一个节点(最后一个比“我”小的元素),然后从这个节点开始降一层再遍历找到第二个节点(最后一个比“我”小的元素),然后一直降到最底层进行遍历找到了期望的节点(最底层的最后一个比我“小”的元素)
随机层数
对于每一个新插入的节点,都需要调用一个随机算法给它分配一个合理的层数。直观上期望的目标是50%的概率被分配到Level1,25%的概率被分配到Level2,以此类推,每一层晋升率是50%。
Redis标准源码的晋升率只有25%,所以官方的跳跃表更扁平化,层高相对较低,在单个层上需要遍历的节点数会稍多一点。
因为层数一般不高,所以遍历的时候从顶层开始往下遍历会浪费,跳跃列表会记录当前的最高层数maxLevel,遍历时从这个maxLevel开始遍历,性能提高很多。
插入过程
首先我们在搜索合适插入点的过程中将“搜索路径”找出来,然后就可以开始创建新节点。创建的时候需要给这个节点随机分配一个层数,再讲搜索路径上的节点和这个新节点通过前向后向指针串起来。如果分配的新节点的高度高于当前跳跃表列表的最大高度,就需要更新一下跳跃列表的最大高度。
删除过程
删除过程和插入过程类似,都需要先把这个“搜索路径”找出来,然后对于每个层的相关节点重排一下前向后向指针,同时注意更新一下最高层maxLevel
更新过程
当我们调用zadd方法时,如果对应的value不存在,那就是插入过程。如果这个value已经存在,只是调整一下score的值,那就需要走一个更新流程。假设这个新的score值不会带来排序上的改变,那么久不需要调整位置,直接修改元素的score值就可以。但是如果排序位置改变了,那就要调整位置。
一个简单的策略是先删除元素,再插入元素,需要经过两次路径搜索。Redis就是这么干的。
如果score值一样
在一个极端的情况下,zset中所有的score值都是一样的,zset的查找性能会退化为O(n)么?所以zset的排序元素不止看score的值,还看value比较
元素排名
zset可以获取元素的排名。Redis在skiplist 的forward指针上进行了优化,给每个forward指针都增加了span属性,span是“跨度”的意思,表示从前一个节点沿着当前层的forward指针跳到当前这个节点中间会跳过多少个节点。Redis在插入、删除操作会小心翼翼更新span值。
我们计算一个元素的排名时,只需要将“搜索路径”经过的所有节点的跨度span值进行叠加就可以算出元素的最终rank值。