← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1770.a

SkipList随机索引

理解等级:中级

SkipList 用随机层级给有序链表增加远跳指针,平均查找、插入、删除复杂度接近 O(logN)。它不需要复杂旋转,适合内存有序表,Redis Sorted Set 和 LevelDB MemTable 都受益于这种简洁性。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 大数据常用的算法与数据结构 · 查看原书依据

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

    参考来源

    - 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html) - 结论依据:原文以“SkipList依靠随机生成数”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。 - 原始内容:SkipList由William Pugh于1990年提出,这是一种可替代平衡树的数据结构,不像平衡树需要强制保持树的平衡,SkipList依靠随机生成数以一定概率来保持数据的平衡分布。尽管在最坏情况下SkipList的效率要低于平衡树,但是大多数情况下其效率仍然非常高,其插入、删除、查找数据的时间复杂度都是O (log(N ))。除了高效外其实现和维护也非常简单,所以在很多大数据系统中在维护有序列表高效读/写的场景下会采用SkipList,比如LevelDB在实现其用于内存中暂存数据的结构MemTable就是使用SkipList实现的,Redis在实现Sorted Set数据结构时采用的也是SkipList,再如Lucene中也使用SkipList来对倒排列表进行快速查找。因这三者实现思路基本遵循经典SkipList的实现方式,所以本节不另行介绍其技术细节。