Redis 中的跳跃表(Skiplist)是一种用于有序元素集合的快速查找数据结构。它通过一个多级索引来提高搜索效率,能够在对数时间复杂度内完成查找、插入和删除操作。跳跃表特别适用于实现有序集合(sorted set)的功能,比如 Redis 的 ZSET
数据类型。
跳跃表的基本结构
跳跃表主要由以下部分组成:
节点(Node):每个节点包含多个层(level),每个层都有一个指向前方节点的指针(forward pointer)。这些层形成了一个多层链表,其中每一层都是一个有序的链表。最底层包含了所有的元素,而上面的层则是随机选择的一些元素(通常是基于某种概率),使得上层的链表更稀疏。
层(Level):每个节点可以有多个层,层数越多,该节点在跳跃表中“跳跃”的能力就越强,即能够更快地跳过多个节点。
跨度(Span):每个层除了有一个指向前方节点的指针外,还有一个跨度(span)字段,记录了两个节点之间的距离(即两个节点之间有多少个节点)。这个信息在搜索过程中可以用来计算位置,优化搜索过程。
头节点(Header):跳跃表有一个特殊的头节点,它不包含任何数据元素,但拥有最大的层数,其作用是作为跳跃表的起点,方便从任何一层开始搜索。
高度(Height):跳跃表的高度是其头节点的层数。
跳跃表的操作
搜索:从最高层开始,沿着指针向前移动,如果当前节点的下一个节点的值大于要搜索的值,则向下移动到下一层,并继续向前移动。这个过程会重复,直到找到目标值或到达最底层且下一个节点的值大于目标值。
插入:首先执行搜索操作,找到应该插入新节点的位置。然后,根据一定的概率决定新节点的层数(通常是随机生成),并逐层插入新节点。
删除:与插入类似,首先通过搜索找到要删除的节点,然后逐层删除该节点。
跳跃表在 Redis 中的应用
Redis 使用跳跃表作为有序集合(sorted set)的底层实现之一(另一个实现是平衡树)。有序集合是一种不允许重复成员,且每个成员都会关联一个 double 类型的分数(score),Redis 通过分数来为集合中的成员进行从小到大的排序。跳跃表能够高效地实现这些操作,如添加、删除和范围查询等。
总的来说,跳跃表是 Redis 中一个非常重要的数据结构,它以其高效的有序集合操作能力,为 Redis 提供了强大的功能支持。