1. 数据结构

1.1.1. 什么是跳跃表?

点击显示

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

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

  • 实现有序集合键
  • 集群节点中用作内部数据结构

    Redis跳跃表

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

results matching ""

    No results matching ""