SkipList跳表工作原理

   跳表在Redis中有具体的应用。我觉得,它是一种具有二分查找特性的特殊链表。

  • 首先,我们了解一下链表

list

  链表是链式结构的数组,链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。他不像数组,需要分配连续的内存。所以,链表有利于对内存更有效的使用。

- 链表内元素的插入与删除操作的,时间复杂度为 O(1),他不需要移动其余元素的位置,只需要修改相关元素的指针指向  
- 链表查找的时间复杂度为 O(n)  
  • 再了解一下数组

array

  数组在内存中,是连续的。元素的位置成为索引,其从0开始。

- 数组的插入与删除操作,时间复杂度为O(n),他需要移动当前元素及其以后元素的位置
- 数组查找的时间复杂度为 O(1)
  • 重点:跳表

skiplist

  h为最小元素;t为最大元素;

- 多层结构
- 有序链表
- 最底层包含所有的数据
- 第 n 层的数据,来自于 第 n-1 层
- 每个元素都指向 同层的 下一个元素,以及下一层的同位置元素
- 查找的使用从最高层开始,利用二分查找的方式查找
- 数据所在的层是随机的
0

发表评论