跳表的诞生可以简单用下面的例子来看:假设一个有序链表,查询某个节点的时间复杂度是O(n),那接下来在链表上层再建立一条链表,每两个结点提取一个结点到上一级,形成L1级缓存链表,如下:
这样当我们要找寻8时,先通过L1索引链表找到7,然后在向下一级链表遍历就找了8,这比直接遍历链表的效率提高了不少,同理,再添加一级L2索引,如图:
查找8的时候先从L2级索引链表开始遍历,遍历的节点个数进一步减少,查找的时间复杂度比单纯的链表遍历进一步提升。
以上是跳表的一个思想,实现起来不同的应用实现的方式不尽相同,这里看一下在Redis中是如何设计并实现跳表。