redis中zset原理

redis中有一个非常重要的数据结构，那就是Zset。它是一个有序集合，也就是说存储的数据是有序的。

说到有序集合，很容易就能想到二叉搜索树，比如AVL树、红黑树、B树、B+树这些数据结构。而Zset底层使用的是什么数据结构呢，其实zset使用的是跳跃表（skipList）的数据结构。

什么是跳跃表？
它其实是一种随机化的数据结构，一个多层的有序链表，一种基于概率统计的插入算法。

那么redis中为什么不使用红黑树而使用跳跃表？

红黑树是一种自平衡二叉搜索树，它的实现和维护相对复杂，特别是在节点的插入、删除时需要进行复杂的旋转操作来维持平衡。相比跳跃表，红黑树的实现较为困难，代码复杂度更高。
跳跃表天然支持范围查询（range query），即可以高效地查找某个区间内的元素。这种范围查询的复杂度为 O(log n) 来找到起点，然后线性遍历范围内的元素，非常适合有序集合中的排序和区间查找操作。
跳跃表是基于链表的结构，占用的内存较少，且其在顺序遍历时的缓存友好性较好。红黑树的节点存储是非连续的，顺序遍历时需要从树的最小节点遍历到最大节点，会有较多的内存不连续访问，缓存效率较低。

图1

跳跃表就像是上图一样的一个多层的链表，如果查询46的话。其步骤是：
（1）查询L4层，查询->55，需要查询1次
（2）查询L3层，查询->21–>55，需要查询2次
（3）查询L2层，查询->37–>55，需要查询2次
（4）查询L1层，查询->46，查询1次，找到结果

跳跃表就好像每两个元素抽取一个元素放到上一层，这样一次叠加，就形成了多层的链表。上一层的元素个数是下一层元素个数的1/2，所以查询的时候就类似二分查找。

这种方法类似于二分查找的方法，所以跳跃表的查找的时间复杂度为O(logN)。

跳跃表每个节点包含两个指针，一个指向同一链表中的下一个元素（next），一个指向下面一层的元素（down）。

我们来看一下插入，往跳表中插入数据的时候，可以选择同时将这个数据插入到第几层中，比如随机函数生成了值 K，那我们就将这个结点添加到第一层到第 K 层这 K 级索引中。

随机的K是如何产生的：
通过随机数来产生，第一层肯定需要添加元素，所以K的初始值为1。后面的，如果随机数为1，就是K加一，随机数为0，就退出。这样每一层插入该元素的概率为1/2的n次方。这样就很大程度上保证了后一层元素的总数量是前一层元素的2倍。

int random_level()  
{  
    K = 1;  

    while (random(0,1))  
        K++;  

    return K;  
}

再看删除，在各个层中找到包含 x 的节点，使用标准的 delete from list 方法删除该节点。直接删除元素，然后调整一下删除元素后的指针即可。跟普通的链表删除操作完全一样。

跳跃表插入和删除的时间复杂度都是O(logN)。