ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
跳跃表skiplist 1.结构理解  1).对于一个单链表来讲,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很高,是 O(n)。 ![](https://img.kancloud.cn/ab/9e/ab9e03b26435d40333b99b95442ecb04_1986x700.png) 2).如果我们想要提高其查找效率,可以考虑在链表上建索引的方式。每两个结点提取一个结点到上一级,我们把抽出来的那一级叫作索引 这个时候,我们假设要查找节点8,我们可以先在索引层遍历,当遍历到索引层中值为 7 的结点时,发现下一个节点是9,那么要查找的节点8肯定就在这两个节点之间。我们下降到链表层继续遍历就找到了8这个节点 ![](https://img.kancloud.cn/58/f7/58f726b65918a2fe10194b5bcb197a6f_2194x676.png) 3)当有大量的数据时,我们可以增加多级索引,其查找效率可以得到明显提升,像这种链表加多级索引的结构,就是跳跃表! ![](https://img.kancloud.cn/b2/2c/b22cae1ce76cd0c437324b0f179d1c3e_2969x1064.png) 2.结构解读 ![](https://img.kancloud.cn/1e/ed/1eedb9eb5c2304dac85c8ad428c27473_887x706.png) 1)跳跃表的结构(zskiplist) ![](https://img.kancloud.cn/b1/a2/b1a2ddccf640b64c2dd1ebd1b5d33cf7_909x346.png) * header和tail指针分别指向跳跃表的表头和表尾节点; * length属性记录节点的数量; * level属性记录层数最高的几点的层数量; 2)跳跃表节点的结构(zskiplistNode) ![](https://img.kancloud.cn/73/2d/732dc689163a2179439710e6ca4bf9f0_1078x610.png) * 层:跳跃表节点的 level\[\] 数组可以包含多个元素,每个元素都包含一个指向其他节点的指针 和 跨度,下标从0开始为第一层; * 前进指针:每个层都有一个指向表尾方向的前进指针,用于从表头向表尾方向访问节点; *跨度:层的跨度用于记录两个节点之间的距离,指向NULL的所有前进指针的跨度为0;跨度用来计算节点的排位:在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排位。 *后退指针:后退指针用于从表尾向表头方向访问节点,每次只能后退一个节点; * 分值和成员: *分值:一个double类型的浮点数,所有节点都按照分值从小到大排序,多个节点可以包含相同的分值; *成员:一个指针,指向一个字符串对象,该字符串对象保存着一个SDS值,成员对象必须是唯一的。