跳跃表

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值。