Redis里跳表遍历到底怎么搞，有啥方法能更快点？

关于Redis里跳表遍历到底怎么搞,以及怎么能更快点，咱们就根据《Redis设计与实现》这本书里讲的和源码里的逻辑，用大白话聊清楚。

跳表是啥？为啥Redis用它？

你可以把跳表想象成一个多层的火车票购票系统,最底层（L0层）就是所有乘客按照先来后到排成的长长队伍，这个队伍包含了所有的人，如果只有一个队伍，售票员想找排在第1000位的人，就得从第1位开始数999次，太慢了。

为了解决这个问题,跳表在上面的楼层（比如L1、L2层）设置了“快速通道”，这些快速通道上的人比较少，并且他们之间间隔了底层的好几个人，L1层可能每4个人里选一个代表站上去，L2层又每4个L1层的人里选一个代表站上去，形成一个更稀疏的“快速队伍”。

当售票员想找第1000位的人时,他就不用傻傻地从底层开始数，他可以先坐电梯到最高的L2层，在L2层的快速队伍里往前找，找到最后一个小于1000的位置；然后下到L1层，在L1层的队伍里，从刚才那个位置继续往前找，找到最后一个小于1000的位置；最后下到L0层，从L1层找到的那个位置开始，在基础队伍里再走几步，就能精准找到第1000位的乘客了，这样跳着找，比从头到尾扫一遍快得多，Redis用跳表来实现有序集合（zset）的其中一个原因，就是它的范围查找效率非常高，插入删除也相对高效。

在Redis里，遍历跳表具体是怎么“搞”的呢？

其实遍历分两种：一种是顺序遍历，另一种是范围遍历。

1. 顺序遍历（从前往后扫一遍）： 这个其实特别简单粗暴，因为跳表最底层（L0）就是一个完整的、排好序的普通链表，如果你想遍历整个跳表，Redis源码里的做法（比如用ZRANGE命令从0到-1）就是直接“下到一楼”，抓住L0层的头节点，然后像走钢丝一样，沿着L0层的指针，一个节点一个节点地往后走，直到走到尾巴（NULL）为止，这个过程根本用不到上面的那些“快速通道”，因为目标是看遍每一个元素，走快速通道反而会漏掉人，这种遍历的时间复杂度和元素个数成正比（O(N)），但对于需要全部数据的场景，这是最直接、不可避免的方法。

2. 范围遍历（找某个分数段的人）： 这才是跳表真正发挥威力的地方，也是你问的“怎么能更快点”的关键，比如命令ZRANGEBYSCORE myzset 80 100，就是要找出分数在80到100之间的所有成员。 Redis的跳表在这里的“快”，就体现在它不是从L0层头节点开始傻找的，它的步骤是：

   • 定位起点：它会利用那些“快速通道”（上层索引），从最高层开始，向右移动指针，寻找最后一个分数小于80的节点，找到这个节点后，下到下一层，继续同样的操作，直到在最底层（L0）找到那个最接近80但又小于80的节点，这个节点就是这次范围遍历的起始点，这个过程就是“跳”，跳过了很多不必要的节点。
   • 线性扫描：一旦在L0层找到了起始点，接下来就简单了，从这个起始点开始，沿着L0层的指针向后遍历，一边遍历一边把符合条件（分数在80到100之间）的节点加入结果集，一旦遇到分数大于100的节点，就立刻停止遍历。

有啥方法能更快点？

从上面的过程可以看出,提速的核心思路就两个：一是尽量减少比较次数，二是尽快定位到目标区间。

1. 利用跳表索引的本质：范围查询时，起点定位要“跳”起来。 这是跳表设计之初就带来的优势，对于范围查询，Redis内部已经自动使用了最高效的方式——先通过上层索引快速定位，再在底层线性收集，作为使用者，你不需要做额外的事情，只需要知道ZRANGEBYSCORE、ZRANGE这类命令在底层已经帮你优化过了，比你手动用ZSCAN然后自己过滤要快得多。

2. 避免全量遍历，尽量使用带限制的范围查询。 如果你明明只需要前10个高分成员，却用了ZRANGE key 0 -1把全部数据取出来再切片，那肯定慢，正确的做法是直接用ZRANGE key 0 9 WITHSCORES，Redis服务器端会在找到第10个元素后就停止遍历并返回，避免了不必要的网络传输和内存分配，这个“限制”（LIMIT）在范围查询中至关重要。

3. 对于超大结果集，考虑使用迭代器（CURSOR）方式。 虽然Redis的有序集合命令本身没有像SCAN那样的游标迭代命令，但如果你在客户端处理一个非常大的范围查询结果时，感觉一次性获取太慢或者内存压力大，你可以在应用层进行分页，多次调用ZRANGE key start stop，每次只取一部分（比如1000个），直到取完，这虽然不能减少Redis服务器内部的遍历成本（它可能还是要遍历整个范围），但可以缓解客户端的瞬时压力和网络带宽占用，让用户体验上感觉“更快”了。

4. 理解数据分布，利用好排他性参数。 在ZRANGEBYSCORE中，你可以使用括号来表示不包含端点，比如(80 100表示分数大于80且小于等于100，更精确的范围意味着Redis在底层线性扫描时，能更早地判断出结束点，从而提前终止扫描，虽然提升可能微小，但在边界附近数据密集的情况下，也是一个优化点。

Redis跳表的遍历,全量扫描就走底层链表；范围查询就先“跳”到起点再扫，想要更快，核心就是充分信任并利用跳表自身的范围查询优化，同时通过限定查询范围来避免不必要的数据传输和处理，作为使用者，写出高效查询的关键在于，你的命令是否能精准地描述你需要的“数据子集”，让Redis能最大限度地发挥它索引结构的优势。