「水见青山多妩媚,料青山见水应如是」
2020 年 06 ~ 10 月读书笔记
Serverless 简介
LevelDB 中的跳表实现
何为跳表
跳跃表(skiplist),简称「跳表」。是一种在链表基础上进行优化的数据结构,最早由 William Pugh 在论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出。
William Pugh 于 1989 在论文中将「跳表」定位为:一种能够替代平衡树的数据结构,比起使用强制平衡算法的各种平衡树,跳表采用一种随机平衡的策略。因此跳表拥有更为简单的算法实现,同时拥有与平衡树相媲美的时间复杂度(logn 级别)和操作效率。