09、跳表数据结构特点？

### 考点分析
我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。
跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操作。

### 典型回答
理解跳表数据结构： 对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据， 也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。
![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/123837_8a5935d0_1767738.png "屏幕截图.png")

那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，查找起来是不是就会 更快一些呢？每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引 层。你可以看我画的图。图中的 down 表示 down 指针，指向下一级结点。
![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/123901_32f818f1_1767738.png "屏幕截图.png")
如果我们现在要查找某个结点，比如 16。我们可以先在索引层遍历，当遍历到索引层中值为 13 的结点时，我们发现下一个结点是 17，那要查找的结点 16 肯定就在这两个结点之间。 然后我们通过索引层结点的 down 指针，下降到原始链表这一层，继续遍历。这个时候，我们只需要再遍历 2 个结点，就可以找到值等于 16 的这个结点了。

这样，原来如果要查找 16， 需要遍历 10 个结点，现在只需要遍历 7 个结点。 加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。

那如果我们再加一级索引呢？效率会不会提升更多呢？ 跟前面建立第一级索引的方式相似，我们在第一级索引的基础之上，每两个结点就抽出一个结点到第二级索引。现在我们再来查找 16，只需要遍历 6 个结点了，需要遍历的结点数量 又减少了。
![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/124009_7309fa2c_1767738.png "屏幕截图.png")

所以即便加了两级索引，查找效率的提升也并不明显。为了让你能真切地感受索引提升查询 效率。我画了一个包含 64 个结点的链表，按照前面讲的这种思路，建立了五级索引。

![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/124035_bb3ad4c5_1767738.png "屏幕截图.png")

从图中我们可以看出，原来没有索引的时候，查找 62 需要遍历 62 个结点，现在只需要遍 历 11 个结点，速度是不是提高了很多？所以，当链表的长度 n 比较大时，比如 1000、10000 的时候，在构建索引之后，查找效率的提升就会非常明显。 
**Redis 中的有序集合（Sorted Set）就是用跳表来实现的。**

Java技术交流/Java技术提升库

内容风险标识

评论 (0)

Java技术交流/Java技术提升库 .gitee-modal { width: 500px !important; }

内容风险标识