跳表

跳表的本质是在链表的基础上建立多级索引,如下图所示:

../_images/Skiplist.png

跳表操作:

  1. 插入
  2. 删除
  3. 查找
  4. 查找一个区间的元素
  5. 输出有序序列

为啥redis 使用跳表,不使用红黑树:

  1. 跳表操作时间复杂度和红黑树相同;
  2. 跳表代码实现更易读;
  3. 跳表区间查找效率更高