跳表(skiplist)


Author: yifei / Created: April 4, 2018, 2:36 p.m. / Modified: April 4, 2018, 10:54 p.m. / Edit

平衡二叉树可以实现 O(logn) 的查找复杂度。跳表可以实现相当于平衡二叉树的复杂度查询数据,而代码实现比较简单。在 Redis 中,zset 就用到了 skiplist。

跳表是用并连的链表来实现的查询结构

一些优化

空间优化,把底层的表放到硬盘里,影响增加删除节点的效率

时间优化,用数组代替链表,可以使用二分查找而非遍历

对于类似时间这种数据,比如24小时对应1440分钟对应86400秒钟

甚至可以固定直接用索引随机访问

实现

https://github.com/begeekmyfriend/skiplist/blob/master/skiplist.h


有任何问题可以发邮件到 kongyifei (at) gmail.com 讨论