1探索C#之跳跃列表

  • 格式:pdf
  • 大小:77.56 KB
  • 文档页数:1

探索C#之跳跃列表
一、基本介绍
SkipList是William Pugh在1990年提出的,它是一种可替代平衡树的数据结构。

SkipList 在实现上相对比较简单,比如在限定时间条件下,能非常轻松的实现SkipList,但却实现不了B树、红黑树、AVL树等,想一想单B树的删除,就要考虑非常多的细节。

虽说SkipList 简单,但性能却非常高,在平均情况下,其插入、删除、查找数据时间复杂度都是O(log(N)),其最坏情况下都为O(N),这点要低于平衡树。

由于skipList的高效及维护简单,所以很多大数据系统中在维护有序列表是都会使用SkipList,比如LevelDB在内存中暂存数据的结构 MemTable就是使用SkipList实现的,Redis在Sorted Set数据结构时也采用的是SkipList,还有Lucene中同样采用SkipList 来对倒排列表进行快速查找。

SkipList依赖随机生成数以一定概率来保持数据在树上的平衡分布,所以SkipList也属于概率算性的数据结构,和之前介绍的BoolFilter属于一个类型C#之布隆过滤器(Bloom filter)。

二、算法思想
举个例子,楼主逛完街要回张江玉兰香苑,如果从人民广场做公交车回去,要路过非常多的站:
想想这么远的路程,多悲惨(在大数据情况下找对应项同样的问题),相较来说坐地铁就快很多,然后到广兰路换程。

这就是SkipList最核心的思想非常简单。

现在路线变成:
因为可以一次跨越很多不需要的站,所以就快了很多。

如果可以搭朋友顺风车的话,变成:
这个图就非常接近SkipList的结构及思想了。

北大青鸟中关村学士后本部
地址:北京海淀区中关村大街49号大华科技商厦A座2层。