redis 跳跃表 插入更新

Redis的跳跃表（Skip List）是一种有序数据结构，用于实现有序集合（Sorted Set）数据类型。在Redis中，插入和更新操作都是基于跳跃表进行的。

对于插入操作，Redis使用跳跃表来维护有序集合。当需要将一个新的元素插入到有序集合中时，Redis首先会在跳跃表中寻找插入位置。通过跳跃表的索引层，Redis可以快速定位到需要插入的位置，而不必遍历整个有序集合。

具体的插入过程如下：
1. 生成一个随机层数level，决定要在跳跃表中插入的元素的索引层高度。
2. 从跳跃表的最高层开始，沿着索引层逐层下降，寻找插入位置，并记录每一层上离插入位置最近的节点。
3. 在底层插入新元素，并将该元素连接到每一层上离插入位置最近的节点。
4. 根据一定的概率，判断是否将新插入的元素提升为索引层的节点。

对于更新操作，Redis将其视为先删除旧元素，再插入新元素的操作。具体的更新过程如下：
1. 在跳跃表中搜索要更新的元素。
2. 如果找到了要更新的元素，从跳跃表中删除该元素。
3. 根据插入操作的方法，在跳跃表中插入新元素。

插入和更新操作都利用了跳跃表的特性，即通过索引层的建立，可以快速定位和搜索元素，从而提高插入和更新操作的效率。跳跃表的插入和更新操作时间复杂度都是O(log n)，其中n是有序集合中元素的数量。因此，Redis利用跳跃表实现了高效的插入和更新功能。

相关问题

为啥redis zset使⽤跳跃链表⽽不⽤红⿊树实现

Redis之所以使用跳跃表而不是红黑树，主要是因为跳跃表的实现比红黑树要简单，而且对于有序集合这个数据结构来说，跳跃表的效率和红黑树相当，甚至在一些情况下，跳跃表的效率还会更高一些。此外，跳跃表在插入和删除操作时，不需要像红黑树那样进行频繁的旋转操作，因此，跳跃表的实现也更加容易维护和扩展。总之，Redis选择跳跃表作为有序集合的底层实现，主要是为了保证数据结构的高效性和简单性。

redis ZSet

Redis ZSet（有序集合）是 Redis 数据结构之一，它是一种有序的字符串集合，每个字符串元素都与一个浮点数（分数）进行关联。ZSet 中的元素是唯一的，但分数可以重复。ZSet 主要提供了以下几个特性：

1. 有序性：ZSet 中的元素按照分数进行排序，可以根据分数进行范围查询、排名等操作。
2. 唯一性：ZSet 中的元素是唯一的，不会存在重复元素。
3. 快速插入和删除：ZSet 使用了跳跃表（skip list）和哈希表（hash table）两种数据结构实现，可以在 log(N) 的时间复杂度内完成插入和删除操作。
4. 高效的范围查询：可以根据分数范围进行查询，例如获取某个范围内的排名、获取某个范围内的元素等。
5. 支持多种操作：ZSet 还支持交集、并集、差集等操作，可以方便地对多个有序集合进行操作。

通过 Redis 提供的命令，可以对 ZSet 进行添加元素、删除元素、修改分数、根据分数范围查询元素、获取排名等操作。ZSet 在实际应用中常用于排行榜、计数器、带权重的任务调度等场景。