跳表啊啊啊啊
按每两个节点生成一个索引，则有第一层索引节点的个数为n/2
1. 时间复杂度O(logn) 最坏O（n）
2. 空间复杂度O(n)
一. 跳表的定义
跳表，又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能
跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作。
跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构
Redis中 的 SortedSet、LevelDB 中的 MemTable 都用到了跳表
对比平衡树, 跳表的实现和维护会更加简单, 跳表的搜索、删除、添加的平均时间复杂度是 O(logn)
跳表和红黑树对比
查找: 红黑树查找操作的时间复杂度在最坏情况下为O(logn)红黑树在查找单个节点时效率很高，但如果需要按照区间查找数据,比不上跳表
- 如果你的应用场景主要是单点查询，并且对数据结构的内存使用有较高要求，那么红黑树可能是一个更好的选择。
红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，Skip需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。
原文地址：https://blog.csdn.net/qixiang2013/article/details/132610639
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！