原书出处
大数据日知录_架构与算法
03 大数据常用的算法与数据结构
SkipList由William Pugh于1990年提出,这是一种可替代平衡树的数据结构,不像平衡树需要强制保持树的平衡,SkipList依靠随机生成数以一定概率来保持数据的平衡分布。尽管在最坏情况下SkipList的效率要低于平衡树,但是大多数情况下其效率仍然非常高,其插入、删除、查找数据的时间复杂度都是O (log(N ))。除了高效外其实现和维护也非常简单,所以在很多大数据系统中在维护有序列表高效读/写的场景下会采用SkipList,比如LevelDB在实现其用于内存中暂存数据的结构MemTable就是使用SkipList实现的,Redis在实现Sorted Set数据结构时采用的也是SkipList,再如Lucene中也使用SkipList来对倒排列表进行快速查找。因这三者实现思路基本遵循经典SkipList的实现方式,所以本节不另行介绍其技术细节。
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html
EPUB SHA-256:e45b74c4bdd8959aef24f2a5183280eb73ec5f173108f8679a4bbf44bbd5b34d