redis 跳表原理

Redis 跳表（Skip List）是一种有序数据结构，用于实现有序集合（Sorted Set）的数据存储和快速查找。

跳表的核心思想是在链表的基础上增加多级索引，通过索引来加速查找。每一级索引包含一部分节点，这些节点按照某种规则连接起来，形成一个类似于二叉树的结构。每一级索引的节点数逐级减少，最高级索引只有两个节点，分别指向整个跳表的头节点和尾节点。

在跳表中，每个节点除了保存值之外，还保存了指向同一层级或下一层级的节点的指针。通过这样的结构，跳表可以在不需要遍历所有节点的情况下，快速定位到目标节点。

Redis 使用跳表实现有序集合的数据结构，具体实现步骤如下：

1. 创建一个带有头节点和尾节点的空跳表。
2. 向跳表中插入新的元素时，从最高级索引开始，逐级向下查找插入位置。
3. 在每一级索引中，找到插入位置后，将新节点插入到该位置后面。
4. 根据概率随机算法，决定是否在更高级索引中插入新节点的指针。
5. 删除元素时，从最高级索引开始，逐级向下查找并删除节点。
6. 如果删除节点后某一级索引只剩下头节点和尾节点，则删除该级索引。

通过使用跳表，Redis 在有序集合中执行插入、删除、查找等操作的时间复杂度可以达到 O(logN)，相比于传统的有序数组或平衡二叉树，跳表具有更高的效率和简单的实现方式。