本文参考：《大数据日知录》
概念
SkipList的使用还是比较广泛的，比如在LevelDB中的MemTable就是使用SkipList实现的，Redis的Sorted Set也是使用SkipList实现的。
核心思路
SkipList节点的生成
SkipList的查找
还是以此图为例，比如现在要找12这个节点，那么过程如下：
- 首先到3的节点，12>3，所以进入6的节点。
- 在6的节点，26>6，并且12<25，12>9，所以进入9的节点。
- 在9的节点，12<17，12=12，于是就找到了12的节点。
SkipList的插入
以上图为例，现在要插入17这个节点。
其过程和查找类似，唯一的问题是，前面的节点的指针是如何保留下来的？
- update[0]：12 level=0
- update[1]：9 level=1
- update[2]：6 level=2
- update[3]：6 level=3
SkipList的删除
删除的逻辑和插入类似：
- 查找到相应的节点
- 通过update数组来实现该节点的逻辑删除
- 回收该节点资源
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176646.html原文链接：https://javaforall.net
