跳表
跳表(skip list) 全称 跳跃链表。 跳表（Skip List）是一种用于实现有序集合的数据结构，它通过在原始链表的基础上增加多级索引来加速查找操作。跳表的设计灵感来自于平衡树，但其实现相对简单并且具有较低的维护成本。
跳表的基本思想是通过建立多级索引来快速定位目标元素，从而避免了对整个链表进行逐个比较的操作。在跳表中，原始链表被分为多个层级，每个层级都是一个有序的链表。最底层包含所有元素，而每个上层链表都是下层链表的子集。
每个元素在跳表中都有对应的索引节点，索引节点包含两部分：指向下一层的指针和对应元素的值。索引节点按照元素的值从小到大排列，且每层的元素数量逐层减少。这样一来，通过顶层的索引节点可以快速找到对应的元素，然后在下一层进行进一步的查找，直到找到目标元素或者确定其不存在。
跳表的查找操作的时间复杂度为O(log n)，其中n为元素的数量。这是因为每一层的索引节点数量大约是下一层的一半，这样在每一层上的查找次数约为常数级别。而在最底层进行实际数据查找的时间复杂度是O(n)。因此，整体的查找操作可以看作是对数复杂度的。
除了查找操作，跳表还支持插入和删除操作。插入操作需要更新索引节点的指针，以保持索引结构的正确性。删除操作需要更新对应的索引节点，同时可能还需要调整其他索引节点的指针。这样虽然会增加插入和删除的复杂度，但相比于平衡树来说，跳表的插入和删除操作更加简单高效。
跳表作为一种灵活且高效的数据结构，在很多基于内存的数据库和缓存系统中得到了广泛应用。它是一种折衷方式，可以在时间和空间之间做出权衡，提供较快的查询速度同时保持相对较低的维护成本。 跳表的性能和平衡树的性能是一样的，在插入，删除，搜索的时间复杂度都是 O(n), 是一 种利用空间换时间的数据结构。 跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它。
跳表结合了链表和二分查找的思想
由原始链表和一些通过“跳跃”生成的链表组成
第 0 层是原始链表，越上层“跳跃”的越高，元素越少
上层链表是下层链表的子序列
查找时从顶层向下，不断缩小搜索范围
主要逻辑是: 从高层开始查找直到找到等于指定元素的节点 E 或者第一个大于指定元素的 节点 G。如果是节点 E，那么直接返回就好了。如果是 G 节点, 那么就以 G 节点的前一个节 点L,在下一层进行查找，重复上面的逻辑，直到找到节点 E，或者到达跳表的结尾。
比如下图中查找 5 的过程为:
· head->8, 8>5,从 head 开始，去下一层查找。
· head->4->8, 8>5,从 4 元素开始查找。去下一层查找
· head->4->8, 8>5,从 4 元素开始查找。去下一层查找.
· head->4->6, 6>5,从 4 元素开始查找。去下一层查找
这篇文章略显浅薄,仅供参考
