文件名称：跳表-空间谱估计算法及应用 王永良
文件大小：8.18MB
文件格式：PDF
更新时间：2024-07-13 16:36:37
leveldb rocksdb leveldb架构
4.1 跳跳跳表表表 4.1.1 概概概述述述 跳表（SkipList）是由William Pugh提出的。他在论文《Skip lists: a probabilistic alternative to balanced trees》 中详细地介绍了有关跳表结构、插入删除操作的细节。 这种数据结构是利用概概概率率率均均均衡衡衡技术，加快简化插入、删除操作，且保证绝大大多操作均拥有O(log n)的良好 效率。 作者在他的论文中这样介绍跳表： 平衡树（以红黑树为代表）是一种非常复杂的数据结构，为了维持树结构的平衡，获取稳定的查询效率， 平衡树每次插入可能会涉及到较为复杂的节点旋转等操作。作者设计跳表的目的就是借助概概概率率率平平平衡衡衡，来构 建一个快速且简单的数据结构，取代平衡树。 作者从链表讲起，一步步引出了跳表这种结构的由来。 19