【Redis】redis基本数据结构之ZSet

怼烎@ 2022-10-17 13:47 171阅读 0赞

# 我的个人博客：[https://www.wuyizuokan.com][https_www.wuyizuokan.com] #

# 介绍： #

ZSet数据结构类似于Set结构，只是ZSet结构中，每个元素都会有一个分值，然后所有元素按照分值的大小进行排列，相当于是一个进行了排序的链表。

如果ZSet是一个链表，而且内部元素是有序的，在进行元素插入和删除，以及查询的时候，就必须要遍历链表才行，时间复杂度就达到了O(n),这个在以单线程处理的Redis中是不能接受的。所以ZSet采用了一种跳跃表的实现。这个实现有点类似于Kafka存储消息是使用的稀疏索引，kafka这个相对较简单，可以用来介绍类比学习。

如果熟悉Kafka，就知道Kafka在进行持久化的时候，生成了两个文件，一个是xxxxxxx.log，一个是xxxxxxx.index，这其中log文件中以链表的形式保存着消息的详细信息，而index文件中，则是保存着这些消息的索引，或者说偏移量，但又不是每一条消息的索引都在index文件中存在，而是稀疏的，比如log文件中的消息的索引从0-10000，那么index文件中存储的索引可能是100， 500， 700， 1000， 5000， 6500，每一个索引中都保存着对应的log文件中的消息的具体位置，如图：

![d46c1a2e244e5771837ddb9c5a5388ed.png][]

当要访问偏移量为899的这条消息时，先去index文件中查找，找到了700和1000这个区间，根据700这个索引中的信息，找到log文件中700这条消息的具体位置，然后顺序往下查找，直到找到索引为899的这条消息为止。从这个实现中我们可以看到，Kafka并没有进行log文件的整个遍历，而是通过index中的稀疏索引，找到消息在log中的大概位置，然后顺序遍历找到消息，这样就大大提高了查找的效率，如图：

![40833f444e4f3c588cc305695345c042.png][]

Redis的跳跃表和上面类似，只是更加复杂一些，Kafka的稀疏索引只有一层，而Redis的索引被提取为多层。如图：

![0943a851f358bec9c66e4f3f0b58f58d.png][]

所有的元素都会在L0层的链表中，根据分数进行排序，同时会有一部分节点有机会被抽取到L1层中，作为一个稀疏索引，同样L1层中的索引也有一定机会被抽取到L2层中，组成一个更稀疏的索引列表。

下面用图来演示一下在对快速链表进行插入、删除、查询时，是如何定位到L0层中的具体位置的。

首先，假定有这么一个链表，注意这里只展示分数，而不展示具体的值了：

![c7bad4e79ccb6d3623ad8021a26ce48b.png][]

如果要查找分数为66的元素，首先在L2层的索引找。很明显，66位于25和85中间，这时就缩小了查找区间：

![b5bda2a343da7757da39c1c561ba15c0.png][]

然后根据获得的区间，去L1对应的区间中查找，得到一个更精确的区间：

![500810aa4e58a579666a3047af22ba54.png][]

最终，根据这个更精确的区间，去L0层顺序遍历，即可得到要查找的元素：

![8e3153a6ed297d22ccb46a641cdf3b95.png][]

上述即是对Redis的跳跃表的原理的一个简述。

这种跳跃表的实现，其实和二分查找的思路有点接近，只是一方面因为二分查找只能适用于数组，而无法适用于链表，所以为了让链表有二分查找类似的效率，就以空间换时间来达到目的。

跳跃表因为是一个根据分数权重进行排序的列表，可以再很多场景中进行应用，比如排行榜，搜索排序等等。

# 命令操作： #

添加元素，zadd zsetName score1 value1 score2 value2 score3 value3 .....

![e9a970eb5967bc7d5b45902cedc2ec34.png][]

查看所有元素，zrange zsetName 0 -1

![ae13ec5fa6b0a5e6e10509de95f9eb39.png][]

查看所有元素，按score逆序排列， zrevrange zsetName 0 -1

![8b93f0b70743e8fdebc6fd4466aad042.png][]

元素数量，zcard zsetName

![1873ae28ddd0f53e3a401d94dac8f258.png][]

获取指定value的分数， zscore zsetName value

![343fcd0e07aaf458d98430a243fee49b.png][]

获取指定value的排名，zrank zsetName value(从0开始)

![7bdc9c7672faf822a1fc801f9e2d1ccd.png][]

获取指定分值区间中的元素， zrangebyscore zsetName scoreStart scoreEnd(包含上下区间)（注意inf表示无穷大，-inf表示服务券大）

![ac7a798e3c6f5554536090d5dd7c84de.png][]

获取指定分值区间中的元素，并且返回分数， zrangebyscore zsetName scoreStart scoreEnd withscores

![4257408404951c762ff55cad4324ec73.png][]

删除元素，zrem zsetName value

![ff81a0da4868a5ea99e822641d8883e3.png][]

# 代码调用： #

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 </td> 
 <td> <code>package</code>&nbsp;<code>main</code> &nbsp; <code>import</code>&nbsp;<code>(</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"fmt"</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"github.com/garyburd/redigo/redis"</code> <code>)</code> &nbsp; <code>func</code>&nbsp;<code>main(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// 连接redis</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>conn,err := redis.Dial(</code><code>"tcp"</code><code>,&nbsp;</code><code>"localhost:6379"</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"connection redis failed. error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// zadd</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>_,err = conn.Do(</code><code>"zadd"</code><code>,&nbsp;</code><code>"phones"</code><code>,&nbsp;</code><code>"100"</code><code>,&nbsp;</code><code>"Nokia"</code><code>,&nbsp;</code><code>"80"</code><code>,&nbsp;</code><code>"tianyu"</code><code>,&nbsp;</code><code>"60"</code><code>,&nbsp;</code><code>"xiaomifeng"</code><code>,&nbsp;</code><code>"50"</code><code>,&nbsp;</code><code>"shangshai"</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"sadd failed, error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// zrange</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result,err := redis.Strings(conn.Do(</code><code>"zrange"</code><code>,&nbsp;</code><code>"phones"</code><code>,&nbsp;</code><code>"0"</code><code>,&nbsp;</code><code>"-1"</code><code>))</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"zrange failed, error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Println(result)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// zrevrange</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result,err = redis.Strings(conn.Do(</code><code>"zrevrange"</code><code>,&nbsp;</code><code>"phones"</code><code>,&nbsp;</code><code>"0"</code><code>,&nbsp;</code><code>"-1"</code><code>))</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"zrange failed, error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Println(result)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// zcard</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>size,err := conn.Do(</code><code>"zcard"</code><code>,&nbsp;</code><code>"phones"</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"zrange failed, error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Println(size)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// zscore</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>score,err := redis.Int(conn.Do(</code><code>"zscore"</code><code>,&nbsp;</code><code>"phones"</code><code>,&nbsp;</code><code>"shangshai"</code><code>))</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"zrange failed, error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Println(score)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// zrem</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>_,err = conn.Do(</code><code>"zrem"</code><code>,&nbsp;</code><code>"phones"</code><code>,&nbsp;</code><code>"shangshai"</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>err != nil { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Errorf(</code><code>"zrange failed, error info: "</code><code>, err)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fmt.Println(</code><code>"delete shangshai success."</code><code>)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// 关闭连接</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>defer</code>&nbsp;<code>conn.Close()</code> <code>}　　</code> </td> 
 </tr> 
 </tbody> 
</table>

执行效果：

![407e636c6a703870b3516e809da2b7f3.png][]

时间总是悄悄流逝

[https_www.wuyizuokan.com]: https://www.wuyizuokan.com/
[d46c1a2e244e5771837ddb9c5a5388ed.png]: /images/20221014/1633d7d415944ab892e49cf2bea16eb7.png
[40833f444e4f3c588cc305695345c042.png]: /images/20221014/b51ae30dc1144f348f35f6d7ab260832.png
[0943a851f358bec9c66e4f3f0b58f58d.png]: /images/20221014/4019d7fdc7304a42a66a53b2ea1abd28.png
[c7bad4e79ccb6d3623ad8021a26ce48b.png]: /images/20221014/65bffca2d911489098087dd7d7d77c13.png
[b5bda2a343da7757da39c1c561ba15c0.png]: /images/20221014/2d10950295034f0e962a32573afc446f.png
[500810aa4e58a579666a3047af22ba54.png]: /images/20221014/222ca3f07c45470bae56c9c351886319.png
[8e3153a6ed297d22ccb46a641cdf3b95.png]: /images/20221014/f0506e93ccf549f9a1a7964705ba4471.png
[e9a970eb5967bc7d5b45902cedc2ec34.png]: /images/20221014/6959607f3add40e58f827a069a50473d.png
[ae13ec5fa6b0a5e6e10509de95f9eb39.png]: /images/20221014/5ee87cc58acf4b0083ada4231b408d30.png
[8b93f0b70743e8fdebc6fd4466aad042.png]: /images/20221014/216ef959b77541f4817020eb06d28602.png
[1873ae28ddd0f53e3a401d94dac8f258.png]: /images/20221014/71e3fa5d63954554818235b709ce7da7.png
[343fcd0e07aaf458d98430a243fee49b.png]: /images/20221014/379c0daf641e4f64b741e9d33d3b9074.png
[7bdc9c7672faf822a1fc801f9e2d1ccd.png]: /images/20221014/7f7ae014ec3545fabde859bc861a39ea.png
[ac7a798e3c6f5554536090d5dd7c84de.png]: /images/20221014/44b8793e55e64d40bc199359fb4491f9.png
[4257408404951c762ff55cad4324ec73.png]: /images/20221014/517be07bc9d8435982636bd418c98ace.png
[ff81a0da4868a5ea99e822641d8883e3.png]: /images/20221014/23cea1c4ea6b480b8b442cb9eb22047d.png
[407e636c6a703870b3516e809da2b7f3.png]: /images/20221014/15e8e02c878648e8a2eac60d719f5ec4.png