当前位置:网站首页>面试官:Redis Zset的实现为什么用跳表,而不用平衡树?
面试官:Redis Zset的实现为什么用跳表,而不用平衡树?
2022-08-11 11:46:00 【InfoQ】
跳表
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
跳表结构设计
- L0 层级共有 5 个节点,分别是节点1、2、3、4、5;
- L1 层级共有 3 个节点,分别是节点 2、3、5;
- L2 层级只有 1 个节点,也就是节点 3 。
typedef struct zskiplistNode {
//Zset 对象的元素值
sds ele;
//元素权重值
double score;
//后向指针
struct zskiplistNode *backward;
//节点的level数组,保存每层上的前向指针和跨度
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
- 跳表的头尾节点,便于在O(1)时间复杂度内访问跳表的头节点和尾节点;
- 跳表的长度,便于在O(1)时间复杂度获取跳表节点的数量;
- 跳表的最大层数,便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量;
跳表节点查询过程
- 如果当前节点的权重「小于」要查找的权重时,跳表就会访问该层上的下一个节点。
- 如果当前节点的权重「等于」要查找的权重时,并且当前节点的 SDS 类型数据「小于」要查找的数据时,跳表就会访问该层上的下一个节点。
- 先从头节点的最高层开始,L2 指向了「元素:abc,权重:3」节点,这个节点的权重比要查找节点的小,所以要访问该层上的下一个节点;
- 但是该层的下一个节点是空节点( leve[2]指向的是空节点),于是就会跳到「元素:abc,权重:3」节点的下一层去找,也就是 leve[1];
- 「元素:abc,权重:3」节点的 leve[1] 的下一个指针指向了「元素:abcde,权重:4」的节点,然后将其和要查找的节点比较。虽然「元素:abcde,权重:4」的节点的权重和要查找的权重相同,但是当前节点的 SDS 类型数据「大于」要查找的数据,所以会继续跳到「元素:abc,权重:3」节点的下一层去找,也就是 leve[0];
- 「元素:abc,权重:3」节点的 leve[0] 的下一个指针指向了「元素:abcd,权重:4」的节点,该节点正是要查找的节点,查询结束。
跳表节点层数设置
为什么用跳表而不用平衡树?
- 它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。
- Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令,即作为链表遍历跳表。通过此操作,跳表的缓存局部性至少与其他类型的平衡树一样好。
- 它们更易于实现、调试等。例如,由于跳表的简单性,我收到了一个补丁(已经在Redis master中),其中扩展了跳表,在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。
- 从内存占用上来比较,跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针(分别指向左右子树),而跳表每个节点包含的指针数目平均为 1/(1-p),具体取决于参数 p 的大小。如果像 Redis里的实现一样,取 p=1/4,那么平均每个节点包含 1.33 个指针,比平衡树更有优势。
- 在做范围查找的时候,跳表比平衡树操作要简单。在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单,只需要在找到小值之后,对第 1 层链表进行若干步的遍历就可以实现。
- 从算法实现难度上来比较,跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而跳表的插入和删除只需要修改相邻节点的指针,操作简单又快速。
边栏推荐
猜你喜欢
leetcode:373. 查找和最小的 K 对数字
PlutoSDR学习指南【2】无线数据传输
Grid 布局介绍
Starting from zero configuration vim (11) -- plug-in management
PlutoSDR学习指南【1】环境搭建+资料分享
VirtualLab: Ince - array of laser Gaussian beam generated vortex observation
五分钟教你内网穿透
如何设计一组会出现死锁(Deadlock)的ABAP程序
低延时实时音视频在5G远程操控场景的应用实践
【毕业设计】远程智能浇花灌溉系统 - stm32 单片机 嵌入式 物联网
随机推荐
鸿海董事长刘扬伟:市场对智能手机和其他消费电子产品的需求正在放缓
class 继承的重点
参与openEuler社区不到1年,我成为了Maintainer……
老生常谈:面试必问“三次握手,四次挥手”这么讲,保证你忘不了
39页智慧粮库解决方案
Kubernetes应用发布思路分析
怎么了
基于数据库实现通用异步缓存系统
pgr_createTopology
Hugging Face快速入门(重点讲解模型(Transformers)和数据集部分(Datasets))
SQL Runtime SLX中的优化设计有哪些?
Grid 布局介绍
2021牛客暑期多校训练营5 J Jewels
VirtualLab: Ince - array of laser Gaussian beam generated vortex observation
谷歌搜索,全球宕机??
OpenHarmony如何选择图片在Image组件上显示(eTS)
Volatile关键字的作用
锂电池充电芯片IC
CSDN文章抓取
【深度学习】笔记2-模型在测试集的准确率大于训练集