Redis中的跳跃表

一、什么是跳跃表

• 一个有层数概念的双向链表

有头节点，尾节点，记录长度，层数

跳跃表要记录的状态信息

• 头节点是傀儡节点，用来指向下一个节点
• 尾节点是指向跳跃表中最大分数的节点

二、空的跳跃表

• 空的跳跃表长什么样？

  
  空的跳跃表

三、随机数

• 实际插入数据之前会进行一次随机数
• 通过多次的随机能获得当前节点的层数

如果新插入的节点是score比当前尾节点的score大，就要更新尾节点。

四、添加元素小总结

添加元素的要点
最后一层是双向链表

五、更新元素小总结

• 如果新插入元素的key之前已经存在，只是value不一样，那么就不是插入，而是更新
• 判断新插入的元素是否存在是根据另一个字典，存储了之前的key-val的信息。
  更新元素的要点

如果新增的元素扩容了我们的区间，则要把之前的节点删除，然后重新添加。

三、查询上的优化

在查询一个节点的时候，是可以跳过之前的一些节点的。