跳跃表是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的!

Redis使用了跳跃表,但只有在两个地方用到

• 实现有序集合键

• 集群节点中用作内部数据结构

  Redis跳跃表

• 每个跳跃表节点的层高都是1至32之间的随机数(根据幂次定律,越大的数出现的概率越小)
• 同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的
• 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照对象的大小进行排序
• 每个节点都有一个后退指针,用于表尾向表头方向迭代(先通过跳跃表的tail指针访问表尾节点,然后通过后退指针访问倒数第二个节点..直至结束)