跳跃表 API ------------- 表 5-1 列出了跳跃表的所有操作 API 。 ---- 表 5-1 跳跃表 API +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | 函数 | 作用 | 时间复杂度 | +===========================+=======================================================+===============================================+ | ``zslCreate`` | 创建一个新的跳跃表。 | :math:`O(1)` | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslFree`` | 释放给定跳跃表，以及表中包含的所有节点。 | :math:`O(N)` ， ``N`` 为跳跃表的长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslInsert`` | 将包含给定成员和分值的新节点添加到跳跃表中。 | 平均 :math:`O(\log N)` ，最坏 :math:`O(N)` ， | | | | ``N`` 为跳跃表长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslDelete`` | 删除跳跃表中包含给定成员和分值的节点。 | 平均 :math:`O(\log N)` ，最坏 :math:`O(N)` ， | | | | ``N`` 为跳跃表长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslGetRank`` | 返回包含给定成员和分值的节点在跳跃表中的排位。 | 平均 :math:`O(\log N)` ，最坏 :math:`O(N)` ， | | | | ``N`` 为跳跃表长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslGetElementByRank`` | 返回跳跃表在给定排位上的节点。 | 平均 :math:`O(\log N)` ，最坏 :math:`O(N)` ， | | | | ``N`` 为跳跃表长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslIsInRange`` | 给定一个分值范围（range）， | 通过跳跃表的表头节点和表尾节点， | | | 比如 ``0`` 到 ``15`` ， ``20`` 到 ``28`` ，诸如此类， | 这个检测可以用 :math:`O(1)` 复杂度完成。 | | | 如果给定的分值范围包含在跳跃表的分值范围之内， | | | | 那么返回 ``1`` ，否则返回 ``0`` 。 | | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslFirstInRange`` | 给定一个分值范围， | 平均 :math:`O(\log N)` ，最坏 :math:`O(N)` 。 | | | 返回跳跃表中第一个符合这个范围的节点。 | ``N`` 为跳跃表长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslLastInRange`` | 给定一个分值范围， | 平均 :math:`O(\log N)` ，最坏 :math:`O(N)` 。 | | | 返回跳跃表中最后一个符合这个范围的节点。 | ``N`` 为跳跃表长度。 | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslDeleteRangeByScore`` | 给定一个分值范围， | :math:`O(N)` ， ``N`` 为被删除节点数量。 | | | 删除跳跃表中所有在这个范围之内的节点。 | | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ | ``zslDeleteRangeByRank`` | 给定一个排位范围， | :math:`O(N)` ， ``N`` 为被删除节点数量。 | | | 删除跳跃表中所有在这个范围之内的节点。 | | +---------------------------+-------------------------------------------------------+-----------------------------------------------+ ---- .. 在前面的几个小节介绍了跳跃表和跳跃表节点， 并展示了它们的详细实现， 在这一节， 我们将来了解跳跃表的操作 API ， 它们包括： - 创建新跳跃表 - 删除跳跃表及其包含的所有节点 - 插入新节点到跳跃表 - 删除跳跃表中的指定节点 - 返回给定节点在跳跃表中的排位（rank） - 按排位返回节点 以下各个小节将对这些 API 进行介绍。 创建新跳跃表 """""""""""""""" ``zslCreate`` 函数用于创建并返回一个新跳跃表： :: zskiplist *zslCreate(void); 下图展示了 ``zslCreate`` 所返回的跳跃表的样子： .. graphviz:: digraph { rankdir = LR; node [shape = record]; splines = false; // zskiplist [label = " zskiplist |
header | tail | length \n 0 | level \n 1 "]; tail_null [label = "NULL", shape = plaintext]; zskiplist:tail -> tail_null; // header [label = " zskiplistNode | level[31] | level[30] | ... | level[1] | level[0] | backward | score | obj "]; L32_null [label = "NULL", shape = plaintext]; L31_null [label = "NULL", shape = plaintext]; L1_null [label = "NULL", shape = plaintext]; L0_null [label = "NULL", shape = plaintext]; // header:L32 -> L32_null [label = "0"]; header:L31 -> L31_null [label = "0"]; header:L1 -> L1_null [label = "0"]; header:L0 -> L0_null [label = "0"]; // zskiplist:header -> header:zskiplistNode; // 为了图形整齐而做的 hack tail_null -> header [style = invis]; } 除了创建跳跃表结构之外，程序还会分配一个表头节点。 以下是新建跳跃表的各项属性和它们的值： - 表头指针 ``header`` ：指向表头节点； - 表尾节点 ``tail`` ：表中还未有包含任何除表头节点以外的其他跳跃表节点，所以未有表尾节点，因此指向 ``NULL`` ； - 层高 ``level`` ：值为 ``1`` ，这是跳跃表的最低层高，程序要求每个节点至少要有一层； - 长度 ``length`` ：表中还未包含任何除表头节点以外的其他跳跃表节点，因此值为 ``0`` 。 以下是表头节点的各项属性和它们的值： - 层 ``level`` ：表头节点的层高由 ``redis.h/ZSKIPLIST_MAXLEVEL`` 常量指定，目前的值为 ``32`` ，所有层的 ``forward`` 指针都指向 ``NULL`` ，而 ``span`` 值都为 ``0`` ； - 后退指针 ``backward`` 、成员对象 ``obj`` 和分值 ``score`` ：表头节点的这些属性都不会被程序用到，所以它们不会被设置。 因为 ``zslCreate`` 函数的工作就是分配并初始化 ``zskiplist`` 结构， 以及为跳跃表创建表头， 这些工作都可以在常数时间内完成， 因此， ``zslCreate`` 函数的复杂度为 :math:`O(1)` 。 释放跳跃表 """""""""""""""" ``zslFree`` 函数用于释放给定的跳跃表 —— 它删除跳跃表包含的所有节点， 并删除跳跃表本身： :: void zslFree(zskiplist *zsl); ``zslFree`` 函数会从跳跃表的表头节点开始， 沿着节点第一层的前进指针（\ ``zskiplistNode.level[0].forward``\ ）移动， 删除沿途遇到的所有节点， 当所有节点都被删除完毕时， 函数删除跳跃表本身。 作为例子， 下图用带虚线的箭头标示了 ``zslFree`` 删除跳跃表中所有节点的顺序： .. graphviz:: image/skiplist_delete_1.dot 当所有节点都被删除之后， 代表跳跃表本身的 ``zskiplist`` 结构将被删除 （跳跃表的 ``level`` 属性和 ``length`` 属性的值没有随着节点的减少而改变， 这不是 BUG ， 原因是 ``zslFree`` 知道跳跃表即将要被删除， 所以不会更新这些属性的值）： .. graphviz:: image/skiplist_delete_2.dot 至此， ``zslFree`` 的执行结束。 对于一个长度为 :math:`N` 的跳跃表来说， ``zslFree`` 需要删除 :math:`N` 个跳跃表节点， 因此， ``zslFree`` 函数的复杂度为 :math:`O(N)` 。 插入新节点 """""""""""""""" ``zslInsert`` 函数将包含给定分值 ``score`` 和成员 ``obj`` 的节点插入到跳跃表中： :: zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj); 跳跃表节由 ``zslInsert`` 函数内部创建， 而层高度则是 ``1`` 至 ``32`` 之间（包含这两个数在内）的一个随机数。 对于一个刚刚使用 ``zslCreate`` 创建的新跳跃表 ``zsl`` 来说： .. graphviz:: image/skiplist_new.dot 执行调用 ``zslInsert(zsl, 2.0, o2);`` 之后， 跳跃表将被更新为以下状态 （假设新节点的层数为 ``2`` ）： .. graphviz:: image/skiplist_insert_1.dot 图中用虚线包围的就是新插入的节点， 虚线箭头标示了因为插入新节点而被修改的指针， 部分前进指针的跨度发生了改变。 插入操作完成之后， 跳跃表本身也发生了变化， 包括： - 跳跃表的表尾节点从原来的 ``NULL`` 指向了新节点； - 长度从原来的 ``0`` 变为了 ``1`` ； - 最大层数从原来的 ``1`` 变为 ``2`` 。 继续执行调用 ``zslInsert(zsl, 1.0, o1);`` ， 跳跃表将被更新为以下状态 （假设新节点层高为 ``4``\ ）： .. graphviz:: image/skiplist_insert_2.dot 图中用虚线包围的就是新插入的节点， 因为新节点的分值为 ``1.0`` ， 所以它排在分值为 ``2.0`` 的节点的前面。 虚线箭头标示了因为插入新节点而被修改的指针， 部分前进指针的跨度发生了改变。 另外， 跳跃表的最大层数和长度也随着新节点的插入而做了相应的修改： - 最大层数从 ``2`` 变更为 ``4`` ； - 长度从 ``1`` 变更为 ``1`` 。 最后， 这是跳跃表执行 ``zslInsert(zsl, 3.0, o3);`` 之后的状态： .. graphviz:: image/skiplist_insert_3.dot ``zslInsert`` 的平均复杂度为 :math:`O(\log N)` ， 最坏复杂度为 :math:`O(N)` 。 删除节点 """"""""""""""""" ``zslDelete`` 函数用于删除跳跃表中包含给定分值 ``score`` 和成员 ``obj`` 的节点： :: int zslDelete(zskiplist *zsl, double score, robj *obj); 举个例子， 如果对以下跳跃表执行调用 ``zslDelete(zsl, 2.0, o2);`` ， 那么图中用虚线包围的节点将被删除： .. graphviz:: image/skiplist_delete_1_before.dot 以下是删除操作完成之后， 跳跃表的状态， 带虚线的箭头表示因为删除操作而被更新的指针， 某些层的跨度也有相应的改变： .. graphviz:: image/skiplist_delete_1_after.dot 除了目标节点被删除了之外， 跳跃表的长度也从 ``3`` 变为了 ``2`` 。 如果我们继续对这个跳跃表执行调用 ``zslDelete(zsl, 3.0, o3);`` ， 那么图中用虚线包围的节点将被删除： .. graphviz:: image/skiplist_delete_2_before.dot 以下是删除操作完成之后， 跳跃表的状态， 带虚线的箭头表示因为删除操作而被更新的指针， 某些层的跨度也有相应的改变： .. graphviz:: image/skiplist_delete_2_after.dot 除了目标节点被删除了之外， 跳跃表的长度也从 ``2`` 变为 ``1`` ， 另外， 因为被删除的节点是原来跳跃表中的层高度最大的节点， 而删除操作执行之后， 表中层最高的节点的层数为 ``4`` ， 所以跳跃表的最大层高度也从原来的 ``5`` 变为 ``4`` 。 ``zslDelete`` 函数的平均复杂度是 :math:`O(\log N)` ， 最坏复杂度是 :math:`O(N)` 。 返回节点排位 """""""""""""""""" ``zslGetRank`` 函数返回包含给定分值 ``score`` 和成员 ``obj`` 的节点在跳跃表中的排位： :: unsigned long zslGetRank(zskiplist *zsl, double score, robj *obj); 排位从 ``1`` 开始， 表头节点不计算在内； 如果没找到目标节点， 那么 ``zslGetRank`` 返回 ``0`` 。 计算排位的方法在前面介绍节点跨度的时候已经说过了： 计算排位相当于在跳跃表中查找节点， 而查找节点过程中， 沿途经过的所有层的跨度之和， 就是节点的排位。 比如说， 对下图所示的跳跃表执行调用 ``zslGetRank(zsl, 3.0, o3);`` ， 函数将返回 ``3`` ， 表示目标节点在跳跃表中排名第三： .. graphviz:: image/skiplist_calc_rank.dot 图片中用虚线表示的就是查找节点时经过的层， 这些层的跨度之和就是节点的排位。 以下是另一个执行调用 ``zslGetRank(zsl, 2.0, o2);`` 的例子： .. graphviz:: image/skiplist_calc_rank_2.dot 调用将返回 ``2`` ， 表示目标节点在跳跃表中排名第二。 ``zslGetRank`` 函数的平均复杂度是 :math:`O(\log N)` ， 最坏复杂度是 :math:`O(N)` 。 按排位返回节点 """"""""""""""""""" ``zslGetElementByRank`` 函数返回跳跃表中排位为 ``rank`` 的节点： :: zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank); 排位从 ``1`` 开始， 表头节点不计算在内； 如果给出的排位超出跳跃表的长度， 那么函数返回 ``NULL`` 。 ``zslGetElementByRank`` 的实现方式和 ``zslGetRank`` 非常相似： - 程序沿着各个层的前进指针移动，并计算沿途各个层的跨度总和； - 当累计的跨度总和等于给定的跨度 ``rank`` 时，返回指针当前指向的节点。 对下图所示的跳跃表执行调用 ``zslGetElementByRank(zsl, 3);`` ， 函数将返回图中用虚线包围的节点， 至于用虚线表示的箭头， 则标示了指针的移动轨迹： .. graphviz:: image/skiplist_get_element_by_rank_1.dot 以下是另一个对跳跃表执行调用 ``zslGetElementByRank(zsl, 2);`` 的例子： .. graphviz:: image/skiplist_get_element_by_rank_2.dot ``zslGetElementByRank`` 的平均复杂度为 :math:`O(\log N)` ， 最坏复杂度为 :math:`O(N)` 。