[AIGC] 跳跃表是如何实现的？原理？

本文主要是介绍[AIGC] 跳跃表是如何实现的？原理？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PS:跳跃表是比较常问的一种结构。

Skip Lists: A Probabilistic Alternative to Balanced Trees

实质上就是一种可以进行二分查找的有序链表。而二分查找的基础就是分层索引。

eg: 论文第二页给的图

在头领节点的最高楼沿着跨度向前寻找，如果刚好找到所需元素，则直接返回，否则继续往前寻找，知道遇到比寻找的元素大的元素，然后返回一个跨度，并下一层楼寻找。如果在一楼也找不到说明元素不存在。

每个楼层至少有两个元素，跨度和前向指针。

eg: 插入，删除

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。

首先，因为 zset 要支持随机的插入和删除，所以它 不宜使用数组来实现，关于排序问题，我们也很容易就想到 红黑树/ 平衡树 这样的树形结构，为什么 Redis 不使用这样一些结构呢？

基于以上的一些考虑，Redis 基于 William Pugh 的论文做出一些改进后采用了 跳跃表 这样的结构。
本质是解决查找问题。

跳跃表的节点里有这些元素：

层跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其它节点的指针，程序可以通过这些层来加快访问其它节点的速度，一般来说，层的数量越多，访问其它节点的速度就越快。每次创建一个新的跳跃表节点的时候，程序都根据幂次定律，随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”
前进指针 每个层都有一个指向表尾的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。我们看一下跳跃表从表头到表尾，遍历所有节点的路径：
跨度层的跨度用于记录两个节点之间的距离。跨度是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。例如查找，分值为3.0、成员对象为o3的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的排位为3。
分值和成员 节点的分值（score属性）是一个double类型的浮点数，跳跃表中所有的节点都按分值从小到大来排序。节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存这一个SDS值。