点击蓝色 “陈树义” 关注我哟
作者：沙茶敏碎碎念
来源：baijiahao.baidu.com
跳表是 redis 的一个核心组件，也同时被广泛地运用到了各种缓存地实现当中，它的主要优点，就是可以跟红黑树、AVL 等平衡树一样，做到比较稳定地插入、查询与删除。理论插入查询删除的算法时间复杂度为 O (logN)。
01 什么是跳表
链表，相信大家都不陌生，维护一个有序的链表是一件非常简单的事情，我们都知道，在一个有序的链表里面，查询跟插入的算法复杂度都是 O (n)。
我们能不能进行优化呢，比如我们一次比较两个呢？那样不就可以把时间缩小一半？
同理，如果我们 4 个 4 个比，那不就更快了？
跳表就是这样的一种数据结构，结点是跳过一部分的，从而加快了查询的速度。跳表跟红黑树又有什么差别呢？既然两者的算法复杂度差不多，为什么 Redis 要使用跳表而不使用红黑树呢？跳表相对于红黑树，主要有这几个优点：
-
代码相对简单，手写个跳表还有可能，手写个红黑树试试？ -
如果我们要查询一个区间里面的值，用平衡树可能会麻烦。这里的麻烦指的是实现和理解上，平衡二叉树查询一段区间也是可以做到的。3. 删除一段区间，这个如果是平衡二叉树，就会相当困难，毕竟设计到树的平衡问题，而跳表则没有这种烦恼。好了，相信你对跳表已经有一些认识了，我们来简单介绍平衡二叉树的几个基本操作。
02 查询
假如我们要查询 11，那么我们从最上层出发，发现下一个是 5，再下一个是 13，已经大于 11，所以进入下一层，下一层的一个是 9，查找下一个，下一个又是 13，再次进入下一层。最终找到 11。
是不是非常的简单？我们可以把查找的过程总结为一条二元表达式（下一个是否大于结果？下一个：下一层）。理解跳表的查询过程非常重要，试试看查询其他数字，只要你理解了查询，后面两种都非常简单。
03 插入
插入的时候，首先要进行查询，然后从最底层开始，插入被插入的元素。然后看看从下而上，是否需要逐层插入。可是到底要不要插入上一层呢？我们都知道，我们想每层的跳跃都非常高效，越是平衡就越好（第一层 1 级跳，第二层 2 级跳，第 3 层 4 级跳，第 4 层 8 级跳）。但是用算法实现起来，确实非常地复杂的，并且要严格地按照 2 地指数次幂，我们还要对原有地结构进行调整。所以跳表的思路是抛硬币，听天由命，产生一个随机数，50% 概率再向上扩展，否则就结束。这样子，每一个元素能够有 X 层的概率为 0.5^(X-1) 次方。反过来，第 X 层有多少个元素的数学期望大家也可以算一下。
04 删除
同插入一样，删除也是先查找，查找到了之后，再从下往上逐个删除。比较简单，就不再赘叙。
推荐阅读
公众号 @陈树义，用最简单的语言，分享我的技术见解。