数据结构 -- 跳表
文章目录
- 概要
- 跳表的结构
- 跳表的查找过程
- 插入操作
- 删除操作
- 补充
概要
跳表（Skip List）是一种基于链表的数据结构，通过增加多级索引来加速查找、插入和删除操作。它可以看作是链表与二分查找的结合体，能够在保持数据有序的同时，实现快速的查找，时间复杂度与平衡树（如红黑树）相同，但实现上更为简单。（跳表又称为：多层级的有序链表）
跳表结构：
跳表的结构
跳表通过构建多层级的链表来提高查找效率。最底层的链表是一个完全有序的链表，包含所有的元素。随着层级升高，每一层链表都会跳过一些元素，从而使查找路径变短。通过这种分层的方式，可以在保持数据有序的同时，实现类似于平衡树的快速查找性能。
- 最底层链表：包含所有元素，按升序排列。所有的搜索最终都会回到这一层，保证能够找到元素。
- 上层索引：每一层的节点是下一层节点的一个子集，用于跳跃式查找。每层链表都按一定概率选取前一层的节点，形成多个层级。
跳表的典型结构如下图所示：
第3层 : [3]------------------->[7]----------->[12]
第2层 : [3]----------->[5]---->[7]----->[10]->[12]
第1层 : [3]->[4]->[5]->[6]->[7]->[8]->[9]->[10]->[12]
- 最底层 Level 1 包含所有元素。
- 上层的每一层是下一层的子集，用于跳跃式查找，加快定位。（
降低了查找时间复杂度，但是重复节点需要额外空间）
跳表的查找过程
跳表的查找类似于二分查找的思想，通过从上到下、从左到右逐步缩小范围，找到目标元素。
查找步骤：
- 从最高层（第一个非空层级）的头节点开始，向右移动，直到当前节点的右边节点大于目标值或右边没有节点。
- 如果右边节点大于目标值或者没有右节点，下降到下一层，继续从当前节点向右查找。
- 重复步骤 1 和 2，直到降到最底层。
- 在最底层找到目标元素，返回结果；如果不存在则返回
null。
例如，查找值 9 的过程：
- 从 第3层 开始，
3 -> 7之后，右边的12比9大，往下到 Level 2。 - 在 第2层，
7 -> 10，右边的10比9大，继续往下到 Level 1。 - 在 第1层，从
7 -> 8 -> 9，找到了目标元素9。
插入操作
插入操作同样从最上层开始，但每当插入一个新节点时，还需要决定是否将该节点插入到更高层级中（即是否创建该节点的索引）。跳表通过随机化策略来决定节点是否在更高层级出现。
插入步骤：
- 按照查找操作，从最高层开始找到插入位置，在最底层找到插入点。
- 插入元素到最底层的链表中。
- 通过随机选择决定是否将节点插入到更高层级，如果是，则在更高层中插入相应的节点索引。
- 重复步骤 3，直到随机选择决定不再向上插入或达到跳表的最高层。
例如，插入 11 的过程：
- 在 Level 1 找到
10和12之间的位置，插入11。 - 随机选择决定
11也出现在 Level 2 中，于是在 Level 2 的10和12之间插入11。 - 再次随机决定
11不会出现在更高层级，插入结束。
删除操作
删除操作与查找操作类似，从最高层开始查找需要删除的元素，找到元素后，在每一层级的链表中删除该元素的索引。
删除步骤：
- 从最高层开始，逐步向下查找目标元素。
- 一旦找到目标元素，在所有包含该元素的层级中删除该元素的节点。
- 当删除完所有层级中的节点后，跳表结构自动调整。
补充
Redis 的有序集合（Sorted Set）就是用跳表实现的，它能够高效支持插入、删除、查找、范围查询等操作。
红黑树：平衡二叉搜索树
B+树：多路平衡搜索树（和跳表类似，所有数据在最后一个层级有序）
面试题：Redis 的有序集合为什么不使用红黑树？
答：跳表范围查询高效
面试题：Redis 的有序集合为什么不使用B+树？
答：
-
复杂度和性能：B+ 树的时间复杂度是 O(log n)，但是其底层结构需要维护多个层次的节点分裂、合并等复杂操作，特别是在插入和删除时，涉及平衡和重构，带来较高的性能成本。而 跳表（SkipList） 的时间复杂度同样是 O(log n)，但其结构更简单，动态操作（如插入、删除、更新）的实现也更加直接，符合 Redis 追求简洁高效的设计理念。
-
基于内存的设计：Redis 是一个基于内存的数据库，不需要频繁访问磁盘，因此无需像 B+ 树那样专门为磁盘 I/O 优化。在内存环境下，跳表能够提供足够的性能，且其实现简单，内存占用也较为合理。
❤觉得有用的可以留个关注ya❤