一、啥是跳表

咱先说说跳表是个啥。跳表其实就是一种数据结构，它能让我们在里面快速地查找、插入和删除数据。打个比方，你有一本超级厚的字典，你要找一个字，要是一页一页翻，那得翻到猴年马月。但如果这本字典有目录，你先从目录里找到大概位置，再去对应页码找，就快多啦。跳表就有点像有目录的字典，它在普通链表的基础上，多了几层索引，能让我们更快地找到想要的数据。

跳表的基本结构

跳表是由多层链表组成的。最底层是一个普通的链表，存储着所有的数据。上面的每一层都是下面一层的索引。比如说，最底层链表有 10 个节点，那上一层可能就只有 5 个节点，再上一层可能就只有 2 个节点，以此类推。这样，当我们要查找一个数据时，就可以先从最上层的索引开始找，快速缩小查找范围，然后再到下一层继续找，直到找到目标数据或者确定数据不存在。

示例代码（Python 技术栈）

import random

# 定义跳表节点类
class SkipListNode:
    def __init__(self, value, level):
        # 节点的值
        self.value = value
        # 节点的每一层的下一个节点
        self.forward = [None] * (level + 1)

# 定义跳表类
class SkipList:
    def __init__(self, max_level=16):
        # 最大层数
        self.max_level = max_level
        # 当前跳表的最高层数
        self.level = 0
        # 头节点，初始值为负无穷
        self.head = SkipListNode(float('-inf'), max_level)

    def random_level(self):
        # 随机生成节点的层数
        level = 0
        while random.random() < 0.5 and level < self.max_level:
            level += 1
        return level

    def insert(self, value):
        # 用于记录每一层需要更新的节点
        update = [None] * (self.max_level + 1)
        current = self.head
        # 从最高层开始查找插入位置
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]
        # 如果值已存在，不插入
        if current and current.value == value:
            return
        # 随机生成新节点的层数
        new_level = self.random_level()
        # 如果新节点的层数大于当前跳表的最高层数
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.head
            self.level = new_level
        # 创建新节点
        new_node = SkipListNode(value, new_level)
        # 更新每一层的指针
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, value):
        current = self.head
        # 从最高层开始查找
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
        current = current.forward[0]
        # 如果找到目标值，返回 True，否则返回 False
        if current and current.value == value:
            return True
        return False

    def delete(self, value):
        update = [None] * (self.max_level + 1)
        current = self.head
        # 从最高层开始查找要删除的节点
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]
        # 如果找到要删除的节点
        if current and current.value == value:
            # 更新每一层的指针
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]
            # 如果删除节点后，最高层没有节点了，降低最高层数
            while self.level > 0 and not self.head.forward[self.level]:
                self.level -= 1


# 使用示例
skip_list = SkipList()
skip_list.insert(3)
skip_list.insert(1)
skip_list.insert(2)
print(skip_list.search(2))  # 输出: True
skip_list.delete(2)
print(skip_list.search(2))  # 输出: False

二、Redis 为啥选跳表实现有序集合

Redis 是一个非常流行的内存数据库，它的有序集合是一种很重要的数据类型。有序集合里的每个元素都有一个分数，元素会根据分数从小到大排序。那 Redis 为啥选择跳表来实现有序集合呢？

快速查找

跳表的查找效率很高，平均时间复杂度是 O(log n)。在 Redis 的有序集合里，我们经常需要根据分数查找元素，或者查找某个范围内的元素。用跳表的话，就能快速地定位到目标元素，提高查询效率。比如说，我们要查找分数在 10 到 20 之间的所有元素，跳表可以快速地找到分数为 10 的元素，然后依次往后找，直到找到分数大于 20 的元素为止。

插入和删除操作高效

跳表的插入和删除操作也很高效，平均时间复杂度也是 O(log n)。在 Redis 的有序集合里，元素是动态变化的，经常会有新元素插入，或者旧元素删除。跳表可以在插入和删除元素时，快速地调整索引结构，保证数据的有序性。比如说，我们要插入一个新元素，跳表会根据元素的分数，快速找到插入位置，然后更新索引。

实现简单

跳表的实现相对简单，代码量也比较少。Redis 是一个开源的项目，代码的可维护性很重要。用跳表来实现有序集合，可以让代码更简洁，更容易维护。

支持范围查询

Redis 的有序集合经常需要进行范围查询，比如查找分数在某个区间内的元素。跳表可以很方便地支持范围查询，只需要从索引中找到范围的起始位置，然后依次遍历链表，直到找到范围的结束位置。

三、跳表的应用场景

数据库索引

在数据库中，索引是提高查询效率的重要手段。跳表可以作为数据库的索引结构，快速定位到数据记录。比如说，在 MySQL 数据库中，B+ 树是常用的索引结构，但在某些场景下，跳表也可以作为一种替代方案。

缓存系统

在缓存系统中，跳表可以用来实现缓存的有序存储。比如说，Redis 就是用跳表来实现有序集合的，这样可以快速地查找和更新缓存数据。

分布式系统

在分布式系统中，跳表可以用来实现分布式索引。比如说，在分布式文件系统中，跳表可以用来快速定位文件的位置。

四、跳表的技术优缺点

优点

  • 查找、插入和删除效率高：跳表的平均时间复杂度是 O(log n)，在大多数情况下，能满足我们对数据操作的性能要求。
  • 实现简单：跳表的代码相对简单，容易理解和维护。
  • 支持范围查询：跳表可以很方便地支持范围查询，这在很多应用场景中非常有用。

缺点

  • 空间开销大：跳表需要额外的空间来存储索引，随着数据量的增加，空间开销会越来越大。
  • 随机层数的不确定性：跳表的性能依赖于随机生成的层数，如果层数分布不合理，可能会影响跳表的性能。

五、使用跳表的注意事项

空间管理

由于跳表需要额外的空间来存储索引，所以在使用跳表时，要注意空间的管理。如果数据量很大，可能需要考虑优化跳表的结构，减少空间开销。

随机层数的调整

跳表的性能依赖于随机生成的层数，所以要合理调整随机层数的生成策略。可以根据实际情况，调整随机层数的概率，保证跳表的性能稳定。

并发操作

在多线程环境下使用跳表时，要注意并发操作的问题。跳表的插入、删除和查找操作可能会相互影响，需要使用锁或者其他并发控制机制来保证数据的一致性。

六、文章总结

跳表是一种非常实用的数据结构，它具有查找、插入和删除效率高，实现简单，支持范围查询等优点。Redis 选择跳表来实现有序集合，正是看中了跳表的这些优点。在实际应用中，跳表可以用于数据库索引、缓存系统、分布式系统等场景。但跳表也有空间开销大、随机层数不确定性等缺点，在使用时需要注意空间管理、随机层数的调整和并发操作等问题。