Redis二分查找和跳跃链表(有序集合)

发布于 2023-10-23  433 次阅读


[top]

目标:redis有序集合的原理,为什么选择跳跃链表

二分查找

简单定义

在一个单调有序的集合中查找元素

  • 每次将集合分为左右两部分
  • 判断解在哪个部分中并调整集合上下界
  • 重复直到找到目标元素

时间复杂度

O(logn)优于直接顺序查找O(n)

例子

查找值为22的记录过程:

  • mid = (low+high) / 2
  • mid<x: low = mid + 1
  • mid>x: high = mid -1
0123456789
13151822283456657080
low=0min=4high=9

mid = 4 (mid = (low+high) / 2)

因为key 4 的值是28,28比22大,即 high = mid -1,新的high = 3

0123456789
13151822283456657080
low=0high=3

high=3 值是22 已经找到返回结果3


跳跃链表

定义

跳表由多条链表L0 ……LN以及下行指针构成

第三级索引-♾️+♾️
第二级索引-♾️44+♾️
第一级索引-♾️234456+♾️
原始链表-♾️12233144566478+♾️

每条链表包含元素检索值单调递增,包含两个特殊节点 -∞(起始节点)和+∞(终止节点)

L0包含所有元素,对任意的i>0,Li+1是Li的子集,且Li+1中的每一个节点,有一个下行指针,指向Li中与之有相同索引值的节点

在跳跃表中查找一个元素x

  1. 从最上层的链(Ln)的开头开始 
  2. 假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较 
    1. x = y 输出查询成功
    2. x > y 从p向右移动到q的位置 
    3. x < y 从p向下移动一格
  3. 如果当前位置在最底层的链中(L0),且还要往下移动的话,则输出查询失败

例子

假设要寻找78这个值

第三级索引-♾️+♾️
第二级索引-♾️44+♾️
第一级索引-♾️234456+♾️
原始链表-♾️12233144566478+♾️
届ける言葉を今は育ててる
最后更新于 2023-10-23