44｜跳表：为什么Redis用跳表实现而MySQL用B+树？
王健伟
你好，我是王健伟。
字符串方面知识的讲解告一段落后，这次，我们讲一讲跳表相关的知识，也讲一讲大家所关心的一个问题——为什么 Redis 用跳表实现而 MySQL 用 B+ 树实现。
在跳表中查询及复杂度分析
回顾以往学习过的数组（线性表的顺序存储）和链表（线性表的链式存储）这两种数据结构，它们各有特点。数组查找速度非常快，但插入、删除速度很慢（要挪动数据）。而链表插入、删除速度快，但查找数据慢。
假设在一个数组中的数据是有序（比如从小到大）排列的，此时若需要快速查询某个元素，那么进行折半（二分）查找是很快就可以找到该元素或者确认该元素不存在的。但如果这组有序的数据并不是用数组而是用链表保存的，那么如何快速查找数据呢？
于是在 1989 年，美国的一位计算机科学家发明了一种新的数据结构——跳跃表，简称跳表。跳表本身基于链表，是对链表的优化（改进版的链表）。跳表这种数据结构因为出现得比较晚，所以很多老项目中并没有采用。
跳表是只能在链表中元素有序的情况下使用的数据结构，即跳表中的元素必须有序。其插入、删除、搜索的时间复杂度都是 O()。它的最大特点是实现相对简单，效率更高，在一些流行项目比如 Redis、LevelDB 中常被用来代替平衡二叉树（AVL 树）或二分查找。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
跳表是一种高效的数据结构，通过多级索引优化了有序链表的查询、插入和删除操作，将时间复杂度从O(n)降低到O(log2n)。在Redis、LevelDB等项目中常被用来代替平衡二叉树或二分查找。本文详细介绍了跳表的实现原理和操作步骤，包括插入、删除和动态更新索引的概率算法。文章还对跳表和B+树在数据库系统中的应用进行了比较，指出了它们在不同场景下的选择和优势。此外，还解答了为什么不同数据库系统选择不同的数据结构实现索引的问题。通过清晰的操作示例和对比分析，全面介绍了跳表的特点和应用，对读者快速了解跳表的实现和优势具有很高的参考价值。 Redis选择了跳表这种数据结构，因为实现简单，代码易读易懂，开销小（效率高）。文章还提供了跳表的实现代码和测试示例，展示了跳表的灵活性和高效性。整体而言，本文内容丰富、深入浅出，适合对跳表感兴趣的读者阅读学习。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论