搞懂Redis的跳跃表结构

大家好，我是连边。

今天更新一篇关于Redis跳表结构相关的文章，希望你能够彻底弄懂Redis跳表结构。

用途

跳跃表是zset（有序集合）的基础数据结构。跳跃表可以高效的保持元素有序，并且实现相对简单、直观的平衡树。

B站视频

友情提示，可以快速跳过抛硬币环节，有群友统计了，抛了22次硬币。

Redis Skip List B站视频

理解

看过视频之后，对跳跃表结构怎么进行增删改查的相信大家有了很直观的理解。

其实跳跃表是受多层链表的想法启发设计得来的。

如果上一层的链表的节点个数，是下面一层的节点个数的一半，这样查找就非常类似于一个二分查找。

但是为什么不直接用二分查找的方式去解决问题， 还要用随机的方式（抛硬币）来解决层数的问题呢？

试想一下，如果我们结构上强制着二分查找，相邻的两层链表上的节点个数严格按照2：1的对应关系，那么在插入新节点的时候，就会打乱这层对应关系，要维护这层关系，又必须把心插入的节点后边的所有节点重新进行调整，这又让时间复杂度退化为O(N)，删除数据也有同样的问题。

跳跃表为了避免这一问题，就采用了随机层数的方式来巧妙的解决。

不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数（level），新插入的节点就会根据自己的层数决定该节点是否在这层的链表上。

总结

今天这篇文章很短，主要的内容就是在那个强烈推荐的视频。

如果想更深入的了解，也推荐另外一篇文章Redis 数据结构之跳跃表（skiplist）。

我是连边，专注于Java和架构领域，坚持撰写有原理，有实战，有体系的技术文章。

关注 订阅号@连边 不错过精彩文章。