Redis跳跃表的跨度到底有多大，带你看看它怎么影响性能和效率

Redis里的跳跃表是个非常巧妙的设计，它让ZSET（有序集合）这种数据结构既能快速插入删除，又能以很高的效率进行范围查询，要理解它的性能奥秘，关键之一就在于“跨度”这个概念，这个跨度到底有多大？它又是怎么在背后悄悄影响Redis的表现的呢？我们得从头慢慢说。

我们得知道跳跃表大概长什么样，你可以把它想象成一座有很多层的摩天大楼，数据就住在这栋楼的不同房间里，最底层，也就是一楼，是一个普普通通的链表，每个房间都连着下一个房间，如果你想从第一个房间走到最后一个房间，你得一个一个地经过所有中间房间，这显然很慢，为了解决这个问题，跳跃表在上面建了“电梯”，也就是高层，高层的房间比较少，每个高层房间的“跨度”更大,意思是它一步就能跨过下面好几层的许多个房间。

这个跨度具体是怎么定义的呢？根据Redis源码（redis/src/t_zset.c中关于zskiplistNode的结构定义），每个节点（房间）都有一个叫“level”的数组，数组里的每个元素代表该节点在某一层上的信息，其中就包含一个“span”字段，这个span就是跨度，它的官方定义是：遍历到下一个节点之间，需要跳过的节点数量，比如在某一层上，节点A的跨度是3，那就意味着，从A节点沿着这一层的前进指针，会直接指向节点D,而中间恰好跳过了B和C两个节点。

现在来回答第一个问题：跨度到底有多大？这个答案不是固定的，它完全取决于两个因素：节点的层级和它在链表中的实际位置。

1. 节点层级：这是最关键的因素，根据Redis的设计（参考其源码中的zslRandomLevel函数），节点层级是通过一种“抛硬币”的随机算法决定的，每建一层新楼，就相当于抛一次硬币，正面就继续往上建，反面就停，这意味着楼层越高，节点越稀少，一个节点所在的层级越高，它的跨度潜力就越大，顶层的头节点，其跨度可能就是从第一个节点直接到最后一个节点，跨度值等于整个跳跃表的长度，而底层节点的跨度，基本上都是1,因为它必须指向紧挨着的下一个节点。

2. 实际位置：即使两个节点都在同一层，它们的跨度也可能不同，在跳跃表中间插入一个新节点后，它前面那个节点的跨度会从原来的一个大数（比如5）变成1（指向新节点），而新节点的跨度则会是4（指向原来那个节点指向的目标），跨度是动态维护的,随着插入和删除操作不断调整。

   

我们看跨度是如何影响性能和效率的，这主要体现在查询过程中，尤其是ZRANGE、ZRANK这类需要按顺序查找的操作。

跨度是查询的“加速器”，跳跃表的查询是从最高层开始的，查询引擎会从高层的头节点出发，看看下一个节点的值是否小于目标值，如果是，它就沿着这一层“跳”过去，这一跳，凭借的就是跨度，一个大的跨度意味着查询过程可以像坐高速电梯一样，一下子越过底层需要步行很久才能走完的一大段距离，每次跳跃，都跳过多个节点，大大减少了需要比较的次数，跨度越大，单次跳跃的距离越远，查询速度自然就越快，可以说，跳跃表的效率，很大程度上就建立在高层节点的大跨度之上。

跨度也是维护的“成本项”，天下没有免费的午餐，大跨度带来的查询速度，是需要付出维护成本的，每当插入或删除一个节点时，Redis不仅要调整底层的指针，还需要更新所有受影响层的跨度信息，插入一个新节点，那么从它前面那个节点开始，一直到顶层的相关路径上，所有节点的跨度值都需要重新计算和更新，这个维护操作虽然时间复杂度依然是O(logN)，但常量因子会比维护一个简单的链表要大，插入删除越频繁,维护跨度的开销就相对越大。

Redis跳跃表的跨度，是一个典型的“空间换时间”和“维护成本换查询效率”的权衡体现，它的大小是动态变化的，高层级带来大跨度，大跨度成就了高效的查询，但同时也增加了数据更新时的微调工作量，Redis通过巧妙的随机层高算法，使得高层节点（大跨度节点）数量不多不少，既保证了查询效率不会退化成普通的链表，又避免了像平衡树那样严格的再平衡所带来的高昂更新成本，这正是Redis跳跃表设计的精妙之处，而跨度，则是这个精妙设计中不可或缺的核心齿轮。 基于对Redis源码，特别是redis/src/t_zset.c文件中关于zskiplist, zskiplistNode, zslRandomLevel等结构和函数的分析理解。）