17 | 跳表：为什么 Redis 一定要用跳表来实现有序集合

在今天的内容中，对于跳表的时间复杂度分析，我分析了每两个结点提取一个结点作为索引的时间复杂度。如果每三个或者五个结点提取一个结点作为上级索引，对应的在跳表中查询数据的时间复杂度是多少呢？

跳表时间复杂度分析

每两个结点提取一个结点作为上级索引

• 跳表的高度： h = O(log_2(n))

• 查询操作： O(log_2(n))

• 插入操作： O(log_2(n))

• 删除操作： O(log_2(n))

• 高度变化趋势： 随节点数量的对数增加而增加，但增加速度逐渐减缓。

每三个结点提取一个结点作为上级索引

• 跳表的高度： h = O(log_3(n))

• 查询操作： O(log_3(n))

• 插入操作： O(log_3(n))

• 删除操作： O(log_3(n))

• 高度变化趋势： 随节点数量的对数增加而增加，但增加速度比每两个结点提取一个结点的情况下减缓。

每五个结点提取一个结点作为上级索引

• 跳表的高度： h = O(log_5(n))

• 查询操作： O(log_5(n))

• 插入操作： O(log_5(n))

• 删除操作： O(log_5(n))

• 高度变化趋势： 随节点数量的对数增加而增加，但增加速度比每三个结点提取一个结点的情况下减缓。