什么是跳表

Redis有序集内部有使用跳表的结构,说说我对跳表的理解:

大家都知道链表的数据结构,它的查询时间复杂度是O(n)。在计算机的世界里,O(n)的复杂度,基本上肯定会被喷的。而跳表的出现,就是为了提高链表的查询效率。

跳表是一个多层结构,最底层还是链表的结构,元素和元素之间的紧紧挨着的。但从最底层依次往上,虽然其上的每一层还是链表结构,但元素和元素之间会跨好几个元素。

level1 0 ------> 2 -------> 4
level0 0 -> 1 -> 2 - > 3 -> 4

level0level1两个链表之间如何关联呢?跳表除了“层”的概念之外,还引入了新的概念“塔”,就是图中数字2表示的那一列。通过给每个元素设置一个向下的指针,就构成了“塔”。

所以,跳表中每个元素包含两个指针:

  1. 一个向右,指向当前“层”的下一个元素
  2. 一个向下,指向当前“塔”的下一个元素

这个的设计思路,其实跟二叉树很像。但却比二叉树的实现要简单好多

诸位正值青春年少,一定恣情放纵,贪恋香艳梅施之情,喜欢风流雅韵之事,洒脱木拘。然而诸位可知,草上露一碰即落,竹上霜一触即溶,此种风情难于长久。
原文地址:https://www.cnblogs.com/shilipojianshen/p/13584441.html