知识卡片
SkipList随机索引
内容
SkipList 用随机层级给有序链表增加远跳指针，平均查找、插入、删除复杂度接近 O(logN)。它不需要复杂旋转，适合内存有序表，Redis Sorted Set 和 LevelDB MemTable 都受益于这种简洁性。
参考来源
- 位置：《大数据日知录：架构与算法》第3章《大数据常用的算法与数据结构》"3.2 SkipList"一节（源文件：_epub-src/OEBPS/text00008.html）
- 结论依据：原文明确"SkipList依靠随机生成数以一定概率来保持数据的平衡分布……其插入、删除、查找数据的时间复杂度都是O(logN)"，并列举"LevelDB在实现其用于内存中暂存数据的结构MemTable就是使用SkipList实现的，Redis在实现Sorted Set数据结构时采用的也是SkipList"。
- 原始内容：不像平衡树需要强制保持树的平衡，SkipList依靠随机生成数以一定概率来保持数据的平衡分布。尽管在最坏情况下SkipList的效率要低于平衡树，但是大多数情况下其效率仍然非常高，其插入、删除、查找数据的时间复杂度都是O(logN)……LevelDB在实现其用于内存中暂存数据的结构MemTable就是使用SkipList实现的，Redis在实现Sorted Set数据结构时采用的也是SkipList。