【Redis为什么用跳表实现有序集合】章节元素查询步骤是否有多余

[SkyGra]

Redis为什么用跳表实现有序集合原文中关于元素查询的描述如下

元素查询
查询逻辑比较简单，从跳表最高级的索引开始定位找到小于要查的 value 的最大值，以下图为例，我们希望查找到节点 8：

1. 跳表的 3 级索引首先找找到 5 的索引，5 的 3 级索引**forwards[3]**指向空，索引直接向下。
2. 来到 5 的 2 级索引，其后继**forwards[2]**指向 8，继续向下。
3. 5 的 1 级索引**forwards[1]**指向索引 6，继续向前。
4. 索引 6 的**forwards[1]**指向索引 8，继续向下。
5. 我们在原始节点向前找到节点 7。
6. 节点 7 后续就是节点 8，继续向前为节点 8，无法继续向下，结束搜寻。
7. 判断 7 的前驱，等于 8，查找结束。

我觉得在步骤2中，不是已经找到了节点8吗，为啥还要向下找，步骤3~步骤7是否是多余的。其次，步骤7中应该说的是判断 7 的后继，等于 8，查找结束，而不是前驱。

此外，前文手写一个跳表中，也有类似元素查询的举例，找到节点后，便不再向下查找了，这两处的元素查询步骤有所出入。

假如我们需要查询元素 6，其工作流程如下：

从 2 级索引开始，先来到节点 4。
查看 4 的后继节点，是 8 的 2 级索引，这个值大于 6，说明 2 级索引后续的索引都是大于 6 的，没有再往后搜寻的必要，我们索引向下查找。
来到 4 的 1 级索引，比对其后继节点为 6，查找结束。
相较于原始有序链表需要 6 次，我们的跳表通过建立多级索引，我们只需两次就直接定位到了目标元素，其查寻的复杂度被直接优化为O(log n)。

附原文链接如下：

JavaGuide/docs/database/redis/redis-skiplist.md

Line 282 in a88ad33

### 元素查询

JavaGuide/docs/database/redis/redis-skiplist.md

Line 87 in a88ad33

假如我们需要查询元素 6，其工作流程如下：

[LilRind]

Redis

Redis为什么用跳表实现有序集合原文中关于元素查询的描述如下

元素查询
查询逻辑比较简单，从跳表最高级的索引开始定位找到小于要查的 value 的最大值，以下图为例，我们希望查找到节点 8：

1. 跳表的 3 级索引首先找找到 5 的索引，5 的 3 级索引**forwards[3]**指向空，索引直接向下。
2. 来到 5 的 2 级索引，其后继**forwards[2]**指向 8，继续向下。
3. 5 的 1 级索引**forwards[1]**指向索引 6，继续向前。
4. 索引 6 的**forwards[1]**指向索引 8，继续向下。
5. 我们在原始节点向前找到节点 7。
6. 节点 7 后续就是节点 8，继续向前为节点 8，无法继续向下，结束搜寻。
7. 判断 7 的前驱，等于 8，查找结束。

我觉得在步骤2中，不是已经找到了节点8吗，为啥还要向下找，步骤3~步骤7是否是多余的。其次，步骤7中应该说的是判断 7 的后继，等于 8，查找结束，而不是前驱。

此外，前文手写一个跳表中，也有类似元素查询的举例，找到节点后，便不再向下查找了，这两处的元素查询步骤有所出入。

假如我们需要查询元素 6，其工作流程如下：

从 2 级索引开始，先来到节点 4。
查看 4 的后继节点，是 8 的 2 级索引，这个值大于 6，说明 2 级索引后续的索引都是大于 6 的，没有再往后搜寻的必要，我们索引向下查找。
来到 4 的 1 级索引，比对其后继节点为 6，查找结束。
相较于原始有序链表需要 6 次，我们的跳表通过建立多级索引，我们只需两次就直接定位到了目标元素，其查寻的复杂度被直接优化为O(log n)。

附原文链接如下：

JavaGuide/docs/database/redis/redis-skiplist.md

Line 282 in a88ad33

元素查询

JavaGuide/docs/database/redis/redis-skiplist.md

Line 87 in a88ad33

假如我们需要查询元素 6，其工作流程如下：

看了下 Redis 的相关跳表的实现（参考 t_zset.c 中， zslInsert 函数）：

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                 sdscmp(x->level[i].forward->ele, ele) < 0))) { // 核心判断逻辑
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    ...
}

可以看到如果分数相等的情况下 x->level[i].forward->score == score ，且元素值小于目标元素ele时继续循环，下降到下一级。而元素值等于ele，即sdscmp(x->level[i].forward->ele, ele) == 0，会跳出循环，直接返回结果（上述代码是修改，即先找到再修改）
所以结果是在 level 2 找到分数和元素值都匹配的节点 8 后，直接返回，无需下降到 level 0（图中的node）。

[Snailclimb]

我觉得在步骤2中，不是已经找到了节点8吗，为啥还要向下找，步骤3~步骤7是否是多余的。其次，步骤7中应该说的是判断 7 的后继，等于 8，查找结束，而不是前驱。

此外，前文手写一个跳表中，也有类似元素查询的举例，找到节点后，便不再向下查找了，这两处的元素查询步骤有所出入。

感谢指出👍