跳表与二叉搜索树

跳表与二叉搜索树

本文探索跳表与二叉搜索树的一些相似之处, 以此来加深对跳表结构的深入理解

适用场景

跳表在Redis中有比较广泛的使用Redis

技术要点

我们可以认定跳表本质上就是一个平衡二叉搜索树, 跳表的目标是为了能够快速的定位key所在的index

所以可以认定的是跳表的底层数据必定有序

节点内容

我们可以认为跳表的每层节点要保存的数据是

struct node {
  key: comparable,
  index: usize,
  next: node,
  next_level_node: node
}

即每一个node的都至少要包含一个用来判断大小的key, 以及一个值记录比自己更大的节点的数量(即下标)

查询

在查询跳表时, 假设有有两个node : now以及next

当查询的值大于 now又小于next时, 会进入now的下一层, 直到next比自己更大或者相等

重复此过程, 如果到达了实际的数据层依然不存在指定数据, 意味着该数据不存在

插入

按照查询流程进行可以得到一条路径

如果不存在插入值, 路径上的所有node 的index都需要加一

如果存在插入值, 返回插入失败

删除

插入流程的反向操作, index - 1

注意要点

跳表在进行插入或者删除操作的时候, 可能会产生类似平衡二叉树的重平衡操作, 这一点需要注意

辨析

为什么使用redis使用跳表而不是二叉搜索树?

因为跳表对于范围区间查询支持更好一些

参考文档

数据结构——跳表skip list_跳表插入_Overcautious的博客-CSDN博客 转载：Skip List–跳表理解跳表，从单链表开始说起下图是一个简单的有序单链表，单链表的特性就是每个元素存放下一个元素的引用。即：通过第一个元素可以找到第二个元素，通过第二个元素可以找到第三个元素，依次类推，直到找到最后一个元素。什么是跳表？跳表的查找、插入、删除元素的流程跳表查找、插入、删除元素的时间复杂度跳表插入元素时，如何动态维护索引？为什么Redis选择使用跳表而不是红黑树来实现有序集 https://blog.csdn.net/qq_44700810/article/details/124355344