你好,我是蒋德钧。
有序集合(Sorted Set)是 Redis 中一种重要的数据类型,它本身是集合类型,同时也可以支持集合中的元素带有权重,并按权重排序。
而曾经就有一位从事 Redis 开发的同学问我:为什么 Sorted Set 能同时提供以下两种操作接口,以及它们的复杂度分别是 O(logN)+M 和 O(1) 呢?
ZRANGEBYSCORE:按照元素权重返回一个范围内的元素。
ZSCORE:返回某个元素的权重值。
实际上,这个问题背后的本质是:为什么 Sorted Set 既能支持高效的范围查询,同时还能以 O(1) 复杂度获取元素权重值?
这其实就和 Sorted Set 底层的设计实现有关了。Sorted Set 能支持范围查询,这是因为它的核心数据结构设计采用了跳表,而它又能以常数复杂度获取元素权重,这是因为它同时采用了哈希表进行索引。
那么,你是不是很好奇,Sorted Set 是如何把这两种数据结构结合在一起的?它们又是如何进行协作的呢?今天这节课,我就来给你介绍下 Sorted Set 采用的双索引的设计思想和实现。理解和掌握这种双索引的设计思想,对于我们实现数据库系统是具有非常重要的参考价值的。
好,接下来,我们就先来看看 Sorted Set 的基本结构。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
0/1000字
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《Redis源码剖析与实战》,如需阅读全部文章,
请订阅文章所属专栏,新⼈⾸单¥59.9
立即订阅