聊聊Mysql索引和redis跳表( 三 ) _Mysql

四、高效的动态插入和删除跳表这个动态数据结构，不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 ○(㏒n) 。
对于单纯的单链表，需要遍历每个结点来找到插入的位置。但是对于跳表来说，因为其查找某个结点的时间复杂度是 ○(㏒n)，所以这里查找某个数据应该插入的位置，时间复杂度也是 ○(㏒n) 。

文章插图

那么删除操作呢？

文章插图

五、跳表索引动态更新当我们不停的往跳表中插入数据时，如果我们不更新索引，就可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表会退化成单链表。

文章插图

作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平滑，也就是说如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。
跳表是通过随机函数来维护前面提到的平衡性。
我们往跳表中插入数据的时候，可以选择同时将这个数据插入到第几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

文章插图

随机函数可以保证跳表的索引大小和数据大小的平衡性，不至于性能过度退化。
跳表的实现有点复杂，并且跳表的实现并不是这篇的重点。主要是学习思路。
六、解答开篇Redis 中的有序集合是通过跳表来实现的，严格点讲，还用到了散列表，如果查看 Redis 开发手册，会发现 Redis 中的有序集合支持的核心操作主要有下面这几个：

插入一个数据
删除一个数据
查找一个数据
按照区间查找数据（比如查找在[100,356]之间的数据）
迭代输出有序序列

其中，插入、查找、删除以及迭代输出有序序列这几个操作，红黑树也能完成，时间复杂度和跳表是一样的，但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 ○(㏒n) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
当然，还有其他原因，比如，跳表代码更容易实现，可读性好不易出错。跳表更加灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
不过跳表也不能完全替代红黑树。因为红黑树出现的更早一些。很多编程语言中的 Map 类型都是用红黑树来实现的。写业务的时候直接用就行，但是跳表没有现成的实现，开发中想用跳表，得自己实现。

【聊聊Mysql索引和redis跳表】