主要为了解决链表查询效率问题
一、时间复杂度
添加多级索引- 每级别索引的元素个数: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
网友评论