Java 算法 - 跳表：为什么 Redis 一定要用跳表来实现有序集合？

数据结构与算法之美目录(https://www.cnblogs.com/binarylei/p/10115867.html)

在二分法查找一文中，我们知道二分法查找一种高效的数据查找方式，其时间复杂度是 O(logn)。但遗憾的是二分法查找只支持有序的静态数组。如果数据需要频繁的插入和删除，那么每次查找时就需要先排序，查找的时间复杂度就上升为 O(nlogn)。如果使用链表直接进行二分法查找，其时间复杂度就上升为 O(n)，比顺序查找还要慢。为了解决这个问题，就需要用到今天用到的数据结构 - 跳表。

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。

1. 工作原理

1.1 链表二分查找时间复杂度 O(n)

二分查找法每次都获取链表的中间结点，采用快慢结点算法获取链表的中间节点时，快慢指针都要移动链表长度的一半次，也就是 n / 2 次，总共需要移动 n 次指针才行。

• 第一次，链表长度为 n，需要移动指针 n 次；
• 第二次，链表长度为 n / 2，需要移动指针 n / 2 次；
• 第三次，链表长度为 n / 4，需要移动指针 n / 4 次；
• ......
• 以此类推，一直到 1 次为值
• 指针移动的总次数 n + n / 2 + n / 4 + n / 8 + ... + 1 = n(1 - 0.52) / (1 - 0.5) = 2n

也就是说，如果采用链表的数据结构，仅获取中间结点的时间复杂度是 O(2n)，不仅远远大于数组二分查找 O(logn)，也要大于顺序查找的时间复杂度 O(n)。

1.2 跳表索引：打破 O(n) 时间复杂度

链表直接进行二分法查找的时间复杂度之所以高，时间基本上都花在获取中间结点了。有没有一种办法可以快速获取其链表的中间结点，甚至和数组一样，时间复杂度为 O(1) 呢？答案其实很简单，使用缓存，我们直接在结点中缓存其中间结点就可以了。所以跳表是一种典型的空间换时间的数据结构。

跳表索引缓存可以分为多层，结构如下：

1.3 时间复杂度：用跳表查询到底有多快？

1.4 空间复杂度：跳表是不是很浪费内存？

高效的动态插入和删除

跳表索引动态更新

每天用心记录一点点。内容也许不重要，但习惯很重要！

Java 算法 - 跳表：为什么 Redis 一定要用跳表来实现有序集合

原文：https://www.cnblogs.com/binarylei/p/12484608.html