Redis 的跳跃表（Skip List）是一种用于有序集合（sorted set）中的底层数据结构。跳跃表是一种平衡的动态数据结构，它支持快速的搜索、插入和删除操作，性能可以与平衡树（如红黑树）相媲美。跳跃表的核心思想是通过多个层次的“跳跃”节点来加速查找过程。

跳跃表的结构

• 层级结构: 跳跃表由多个层次组成，最底层（第 1 层）包含所有的元素，每一层都是上一层的子集，且层级越高包含的元素越少。通过在高层次跳跃，可以快速接近目标元素。
• 节点: 每个节点包含键值对（key-value），以及指向下一节点的指针。根据概率，每个节点随机决定它所属的层数（通常是基于几何分布），从而决定该节点会出现在多少层上。

跳跃表的操作

1. 查找:

   • 查找操作从最高层开始，沿着节点的指针进行“跳跃”，如果当前节点的键小于目标键，则向右移动，否则向下移动到下一层，直到找到目标元素或确定元素不存在。
   • 通过这种“跳跃”方式，查找的时间复杂度为 O(log n)。

2. 插入:

   • 插入操作首先进行查找，确定新元素应该插入的位置，然后从第 1 层开始插入节点。
   • 插入时，随机决定新节点所属的层数，并在对应的层次中插入该节点。每层的插入操作类似于链表的插入，调整相应指针即可。

3. 删除:

   • 删除操作同样从查找开始，找到目标节点后，从最底层开始删除节点，逐层删除，并调整相应的指针。

跳跃表在 Redis 中的应用

• 有序集合（ZSet）: Redis 中的有序集合是通过跳跃表和字典（hash table）结合实现的。字典用于通过键快速查找对应的分数（score），跳跃表则用于根据分数排序。
• 范围查询: 跳跃表特别适合执行范围查询，如查找分数在某个区间内的所有元素，因为跳跃表结构支持高效的区间查找操作。
• 时间复杂度: 跳跃表的插入、删除、查找的平均时间复杂度为 O(log n)，在最坏情况下，时间复杂度也接近于 O(log n)。

跳跃表 vs. 平衡树

• 实现简单: 跳跃表的实现比平衡树（如红黑树、AVL树）要简单，不需要复杂的旋转和重平衡操作。
• 随机性: 跳跃表依赖随机化来保持平衡状态，这在大多数情况下可以达到与平衡树类似的性能。
• 存储开销: 跳跃表需要额外的指针来维护多层结构，因此在某些情况下，可能会比树结构占用更多的内存。

总结

Redis 的跳跃表是一个高效的动态数据结构，特别适合用于有序集合中的数据管理。通过跳跃表，Redis 能够在保证较低时间复杂度的前提下，支持快速的查找、插入、删除和范围查询操作。