5.跳表

主要为了解决链表查询效率问题

一、时间复杂度

• 每级别索引的元素个数：n/2、n/4、n/8、...、n/(2^k)
• 假如索引有 h级，最高级的索引有 2 个节点。n/(2^h) = 2，从而求得h=log2(n) - 1
• 在跳表中查询任意数据的时间复杂度就是 O(logn)

二、空间复杂度

• 原始链表大小为 n，每 2 个结点抽 1 个，每层索引的结点数: n/2 , n/4 , n/8 , ⋯,8,4,2
• 原始链表大小为 n，每 3 个结点抽 1 个，每层索引的结点数: n/3, n/6, n/9 ,⋯,9,3,1
• 空间复杂度是 O(n)

三、跳表的应用

Redis 跳表的结构：https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
Redis 为何用跳表：https://www.zhihu.com/question/20202931