数据结构论坛

首页 » 分类 » 问答 » redis底层数据结构3skipl
TUhjnbcbe - 2020/11/13 6:32:00

如果有序集合包含较多的元素,或者元素是较长的字符串时(具体阈值会在下文分析),redis就会使用跳跃表作为有序集合(sortedset)键的底层实现。但是sortedset底层不仅使用了skiplist,还使用了ziplist和dict。

1sortedset样例

sortetset其实就是redis的zset数据结构。

.0.0.1:zaddgrade98Chinese(integer)1.0.0.1:zaddgrade97Math(integer)1.0.0.1:zaddgrade97English(integer)1.0.0.1:OBJECTencodinggrade"ziplist".0.0.1:zaddgrade95VeryLongSubjectName1(integer)1.0.0.1:OBJECTencodinggrade"skiplist".0.0.1:zrangegrade0-1withscores1)"VeryLongSubjectName1"2)"95"3)"English"4)"97"5)"Math"6)"97"7)"Chinese"8)"98".0.0.1:zrevrangegrade0-1withscores1)"Chinese"2)"98"3)"Math"4)"97"5)"English"6)"97"7)"VeryLongSubjectName1"8)"95".0.0.1:zscoregradeEnglish"97".0.0.1:ZREVRANKgradeChinese(integer)0.0.0.1:ZREVRANGEBYSCOREgradewithscores1)"Chinese"2)"98"3)"Math"4)"97"5)"English"6)"97"

grade有序集合的所有数据保存在一个跳跃表里,其中每个跳跃表节点都保存了一门课程的分数,从低到高在跳跃表里排序:

zadd命令用于往sortedset插入成员和分值

如果分值相同,将成员的值按照字符串比较大小,虽然Math和English的分值相同,但是M大于E,所以Math比English高

zrange由低到高排序

zrank/zrevrank(升序/降序)查询指定成员的排名

zscore查询指定成员对应的分数

zrevrange根据排名范围,由高到低排序

zrevrangebyscore查询指定分数期间内的数据集合

2跳跃表的基本原理

skiplist可以翻译为跳跃表,简称跳表,是一种可实现高效查找的特殊数据结构,解决查找问题的数据结构还有平衡树或者哈希表。在大部分情况下,跳跃表的效率与平衡树差不多,并且跳跃表的实现比平衡树简单。

跳跃表的详细介绍如下链接所示:

1
查看完整版本: redis底层数据结构3skipl