31｜跳表：Redis是如何存储有序集合的？

该思维导图由 AI 生成，仅供参考

跳表是一种在Redis中发挥重要作用的数据结构，特别适合存储有序集合。与红黑树相比，跳表的实现更为简洁优雅，几乎在每个方面都更胜一筹。跳表的设计动机源于对链表存储有序集合时查询效率低下的问题，通过在链表上增加多层索引，实现了类似平衡二叉搜索树的快速搜索效果。跳表节点的基本数据结构包括向右和向下的指针，通过这些指针可以维护整个多层的跳表结构。跳表的搜索过程是从左上到右下进行的，通过左右寻找目标区间和向下走的方式实现对目标值的查找。跳表的实现原理涉及如何维护多层链表结构以及在合适的时机加入新的层，以保证高效查询同时不带来过高的维护成本。跳表的设计思想类似于换乘公共交通，通过增加间距更大的“站”实现快速搜索。引入随机性的跳表通过搜索并记录路径，可以在保持跳表查询效率的同时，快捷地插入元素，降低维护成本。虽然单点查询的效率不如哈希表，但跳表可以很好地支持范围查询，这一点比红黑树也有明显优势。总的来说，跳表作为一种高效的有序集合实现，背后的原理值得深入学习。