redis为什么使用跳表而不是红黑树,redis中的跳表

　　Yyds干货库存

　　跳表Redis只在Zset对象的底层实现中使用跳表，跳表的优点是可以支持平均O(logN)复杂度的节点搜索。

　　zset结构中有两种数据结构：一种是跳转表，一种是哈希表。这同时具有高效范围查询和高效单点查询的优点。

　　typedef结构zset {

　　dict * dict

　　zskiplist * zsl

　　} zset在数据插入或数据更新的过程中，Zset对象会依次插入或更新跳转表和哈希表中相应的数据，从而保证跳转表和哈希表中记录的信息的一致性。

　　Zset对象可以支持范围查询(比如ZRANGEBYSCORE操作)，因为它的数据结构设计采用了跳转表，可以获得复杂度不变的元素权重(比如ZSCORE操作)，因为它也采用哈希表进行索引。

　　很多人可能会疑惑，为什么我一开始说Zset对象的底层数据结构是“压缩列表”或者“跳转表”，而不是哈希表？

　　Zset对象使用跳转表作为其数据结构时，使用的是由“哈希表跳转表”组成的struct Zset。但是我们讨论的时候总是说跳转表是zset对象的底层数据结构，却没有提到哈希表，因为struct zset中的哈希表只是用来获取复杂度不变的元素权重，大部分操作都是通过跳转表来实现的。

　　接下来，我们来详细说说跳转列表。

　　用跳转表结构设计链表时，查询效率很低，时间复杂度为O(N)，于是出现了跳转表。跳转表是在链表的基础上改进的，实现了“多层”有序链表，优点是可以快速读取定位数据。

　　跳表是什么样子的？我给你举个例子。下图显示了级别为3的跳转表。

　　图中的头节点有L0~L2三个头指针，分别指向不同级别的节点，然后每一级的节点通过指针连接起来：

　　L0层中有五个节点，即节点1、2、3、4和5。L1有三个节点，分别是节点2、3和5。L2只有一个节点，即节点3。如果要找到链表中的元素节点4，只能从头遍历链表，需要查找4次。使用跳转表后，我们只需要查找2次就可以定位到节点4，因为我们可以直接从L2级跳转到头节点的节点3，然后向前遍历找到节点4。

　　正如您所看到的，这个搜索过程在多个层次上跳跃，最终找到元素。当数据量较大时，跳转表的查找复杂度为O(logN)。

　　那么跳表节点是如何实现多级的呢？取决于“跳表节点”的数据结构，如下：

　　typedef结构zskiplistNode {

　　//Zset对象的元素值

　　sds ele

　　//元素权重值

　　双倍积分；

　　//向后指针

　　struct zskiplistNode * backward

　　//节点的级别数组，保存每个层上的前向指针和跨度

　　结构zskiplistLevel {

　　struct zskiplistNode * forward

　　无符号长跨度；

　　} level[]；

　　} zskiplistNodeZset对象要同时存储“元素”和“元素权重”，对应跳转表节点结构，是sds类型的ele变量和double类型的score变量。跳转表的每个节点都有一个向后指针(struct zskiplistNode *backward)，指向前一个节点。目的是从跳转表的结束节点开始访问节点，方便逆序查找。

　　跳表是一个有层次关系的链表，每一层可以包含多个节点，每个节点之间用指针连接。为了实现这个特性，我们依赖于跳表的节点结构中zskiplistLevel结构类型的level数组。

　　级别数组中的每个元素代表跳转表的一个级别，即由zskiplistLevel结构表示。例如，leve[0]表示第一级，leve[1]表示第二级。ZskiplistLevel结构定义了“指向下一跳节点的指针”和“span”，用来记录两个节点之间的距离。

　　例如，下图显示了每个节点的范围。

　　我第一次看到span的时候，以为是和遍历操作有关，实际上并没有什么关系。遍历操作只能通过使用前向指针(struct zskiplistNode *forward)来完成。

　　Span其实就是计算这个节点在跳数列表中的排名。具体怎么做？由于跳表中的节点是按顺序排列的，所以在计算某个节点的排名时，一路上访问的所有层的跨度都是从头节点开始累加到该节点的查询路径，结果就是跳表中目标节点的排名。

　　例如，为了找到图中跳列表中节点3的排名，从第一个节点开始搜索节点3。搜索过程只经过一级(L2)，该级的跨度为3，因此节点3在跳表中的排名为3。

　　另外，图中的头节点实际上是一个zskiplistNode跳转表节点，只是没有用到头节点的后向指针、权重和元素值，所以图中省略了这部分。

　　问题来了。谁定义哪个跳表节点是头节点？这就引入了“跳转表”结构，如下：

　　typedef结构zskiplist {

　　struct zskiplistNode *header，* tail

　　无符号长长度；

　　int级别；

　　} zskiplist跳转表结构包含：

　　跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头尾节点；跳表的长度便于获得O(1)时间复杂度的跳表节点数；跳表中的最大层数便于在O(1)时间复杂度下获得跳表中层高最高的节点的层数；在搜索跳表节点时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会使用跳表节点中的SDS型元素和元素的权重进行判断。有两个判断条件：

　　如果当前节点的权重“小于”要查找的权重，跳转表将访问这一层的下一个节点。如果当前节点的权重“等于”要查找的权重，并且当前节点的SDS类型数据“小于”要查找的数据，则跳转表将访问该层上的下一个节点。如果不满足上述两个条件，或者下一个节点为空，跳转表将使用当前遍历节点的级别数组中的下一级指针，然后沿着下一级指针继续搜索，相当于跳转到下一级进行搜索。

　　例如，下图有一个3级跳转表。

　　如果要查找“元素：abcd，权重：4”的节点，搜索过程如下：

　　从第一个节点的顶层开始，L2指向“元素：abc，权重：3”节点。这个节点的权重比要找的节点小，所以需要访问这一层的下一个节点；但这一层的下一个节点是一个空节点(leve[2]指向一个空节点)，所以会跳到下一层的“Element: abc，Weight: 3”节点去寻找，即leve[1]；“element: abc，weight: 3”节点的leve[1]的下一个指针指向“element: abcde，weight: 4”节点，然后与要查找的节点进行比较。虽然节点“Element: abcde，Weight: 4”的权重与要搜索的权重相同，但是当前节点的SDS类型数据“大于”要搜索的数据，所以会继续跳转到节点的下一级“Element: abc，Weight: 3”来查找，即Leve[0]；“element: abc，weight: 3”节点的leve[0]的下一个指针指向“element: abcd，weight: 4”节点，这正是要查找的节点。查询已完成。跳转表的节点数设置了跳转表相邻两层节点数的比值，会影响跳转表的查询性能。

　　例如，在下面的跳表中，第二层的节点数只有一个，而第一层的节点数是六个。

　　这时如果要查询节点6，基本上和链表的查询复杂度一样，需要依次搜索第一级的节点，复杂度为O(N)。因此，为了降低查询复杂度，我们需要维护相邻层中节点数量之间的关系。

　　* *跳表相邻两层节点数的理想比例为2:1，搜索复杂度可降至O(logN)**。

　　下面的跳表显示，两个相邻层中的节点数量比为2: 1。

　　如何才能使相邻两层的节点数之比保持在2: 1？

　　如果采用增减节点的方法来调整跳表节点来维持比例，会带来额外的开销。

　　Redis采用了一种巧妙的方法，即在创建节点时，跳表随机生成每个节点的层数，并不严格保持相邻两层节点数之比为2: 1。

　　具体来说，在创建节点时，将生成一个范围在[0-1]内的随机数。如果这个随机数小于0.25(相当于25%的概率)，则将层数增加一层，然后生成下一个随机数，直到随机数的结果大于0.25，最终确定这个节点的层数。

　　这样，每增加一层楼的概率等于不超过25%。楼层越高，概率越低，楼层高度上限为64。

　　为什么跳表而不是平衡树？Zset为什么用跳转表而不用平衡树(如AVL树、红黑树等。)?

　　Redis作者@antirez对这个问题怎么说：

　　有几个原因：

　　它们不是非常占用内存。基本上由你决定。改变关于节点具有给定数量的级别的概率的参数将使得比btrees更少的存储器密集。一个已排序的集合通常是许多ZRANGE或ZREVRANGE操作的目标，也就是说，作为一个链表遍历跳过列表。通过这种操作，跳转列表的高速缓存局部性至少与其他类型的平衡列表一样好。它们更容易实现、调试等等。例如，由于跳过列表的简单性，我收到了一个补丁(已经在Redis master中)，增加了实现zrankin o (log (n))的跳过列表。它只需要对代码做很少的修改。简单翻译一下，主要从内存占用、支持范围查找、实现难度三个方面总结原因：

　　它们不是非常占用内存。这基本上取决于你。改变关于一个节点具有给定层数的概率的参数将使它比btree占用更少的内存。Zset经常需要执行ZRANGE或ZREVRANGE命令，即以链表的形式遍历跳转表。通过这个操作，跳转表的缓存局部性至少和其他类型的平衡树一样好。它们更容易实现、调试等。比如，由于跳表的简单，我收到了一个补丁(Redis master中已经有了)，它扩展了跳表，在O(log(N)中实现了ZRANK。它只需要对代码做一些修改。让我再补充一些细节：

　　与平衡树相比，跳转表在内存占用方面更加灵活。平衡树的每个节点包含两个指针(分别指向左右子树)，而跳表的每个节点的平均指针数是1/(1-p)，取决于参数p的大小，如果像Redis中的实现，p=1/4，那么每个节点平均包含1.33个指针，比平衡树更有优势。

　　做范围搜索时，跳表比平衡树简单。在平衡树上，我们找到指定范围的小值后，需要继续寻找中间顺序的遍历顺序不超过大值的其他节点。如果不修改平衡树，这里的中序遍历就不容易实现。但在跳转表上搜索范围非常简单，找到小值后只需分几步遍历一级链表即可实现。

　　相对于算法实现的难度，跳表比平衡树简单多了。平衡树的插入和删除可能会导致子树的调整，逻辑复杂，而跳转表的插入和删除只需要修改相邻节点的指针，操作简单快速。

　　版权归作者所有：原创作品来自博主Codeong小宋，转载请联系作者取得转载授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。