跳表

跳表（Skip List）是一种随机化的数据结构，它在链表的基础上引入多级索引，从而实现类似于平衡树的对数时间复杂度的搜索、插入和删除操作。跳表由 William Pugh 于1990年发明，用于替代平衡树。跳表主要用于有序数据序列，

Redis 中的有序集合 (Sorted Set) 其底层数据结构就是跳表。使用跳表可以高效的对有序集合执行添加、删除及查找等操作。

跳表的基本思想是将链表分层，么一层都是原链表的一个子集，每一层都是一个有序链表。通过这些索引，可以在对数时间内跳跃到目标元素，从而实现快速的查找、插入和删除操作。跳表的时间复杂度为 $O(\log n)$ ，比普通链表的时间复杂度 $O(n)$ 要快得多。