xinyin025/learn.lianglianglee.com
1
0
Fork 0
mirror of https://github.com/zhwei820/learn.lianglianglee.com.git synced 2025-09-17 08:46:40 +08:00
Code Issues Actions Packages Projects Releases Wiki Activity
master
learn.lianglianglee.com/专栏/Redis 核心原理与实战/14 有序集合使用与内部实现原理.md.html
周伟 0f006e4e9b add
2022-05-11 18:57:05 +08:00

1167 lines
25 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html>
<!-- saved from url=(0046)https://kaiiiz.github.io/hexo-theme-book-demo/ -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, user-scalable=no">
<link rel="icon" href="/static/favicon.png">
<title>14 有序集合使用与内部实现原理.md.html</title>
<!-- Spectre.css framework -->
<link rel="stylesheet" href="/static/index.css">
<!-- theme css & js -->
<meta name="generator" content="Hexo 4.2.0">
</head>
<body>
<div class="book-container">
<div class="book-sidebar">
<div class="book-brand">
<a href="/">
<img src="/static/favicon.png">
<span>技术文章摘抄</span>
</a>
</div>
<div class="book-menu uncollapsible">
<ul class="uncollapsible">
<li><a href="/" class="current-tab">首页</a></li>
</ul>
<ul class="uncollapsible">
<li><a href="../">上一级</a></li>
</ul>
<ul class="uncollapsible">
<li>
<a href="/专栏/Redis 核心原理与实战/01 Redis 是如何执行的.md.html">01 Redis 是如何执行的.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/02 Redis 快速搭建与使用.md.html">02 Redis 快速搭建与使用.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/03 Redis 持久化——RDB.md.html">03 Redis 持久化——RDB.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/04 Redis 持久化——AOF.md.html">04 Redis 持久化——AOF.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/05 Redis 持久化——混合持久化.md.html">05 Redis 持久化——混合持久化.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/06 字符串使用与内部实现原理.md.html">06 字符串使用与内部实现原理.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/07 附录：更多字符串操作命令.md.html">07 附录：更多字符串操作命令.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/08 字典使用与内部实现原理.md.html">08 字典使用与内部实现原理.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/09 附录：更多字典操作命令.md.html">09 附录：更多字典操作命令.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/10 列表使用与内部实现原理.md.html">10 列表使用与内部实现原理.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/11 附录：更多列表操作命令.md.html">11 附录：更多列表操作命令.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/12 集合使用与内部实现原理.md.html">12 集合使用与内部实现原理.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/13 附录：更多集合操作命令.md.html">13 附录：更多集合操作命令.md.html</a>
</li>
<li>
<a class="current-tab" href="/专栏/Redis 核心原理与实战/14 有序集合使用与内部实现原理.md.html">14 有序集合使用与内部实现原理.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/15 附录：更多有序集合操作命令.md.html">15 附录：更多有序集合操作命令.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/16 Redis 事务深入解析.md.html">16 Redis 事务深入解析.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/17 Redis 键值过期操作.md.html">17 Redis 键值过期操作.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/18 Redis 过期策略与源码分析.md.html">18 Redis 过期策略与源码分析.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/19 Redis 管道技术——Pipeline.md.html">19 Redis 管道技术——Pipeline.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/20 查询附近的人——GEO.md.html">20 查询附近的人——GEO.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/21 游标迭代器（过滤器）——Scan.md.html">21 游标迭代器（过滤器）——Scan.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/22 优秀的基数统计算法——HyperLogLog.md.html">22 优秀的基数统计算法——HyperLogLog.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/23 内存淘汰机制与算法.md.html">23 内存淘汰机制与算法.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/24 消息队列——发布订阅模式.md.html">24 消息队列——发布订阅模式.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/25 消息队列的其他实现方式.md.html">25 消息队列的其他实现方式.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/26 消息队列终极解决方案——Stream（上）.md.html">26 消息队列终极解决方案——Stream（上）.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/27 消息队列终极解决方案——Stream（下）.md.html">27 消息队列终极解决方案——Stream（下）.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/28 实战：分布式锁详解与代码.md.html">28 实战：分布式锁详解与代码.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/29 实战：布隆过滤器安装与使用及原理分析.md.html">29 实战：布隆过滤器安装与使用及原理分析.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/30 完整案例：实现延迟队列的两种方法.md.html">30 完整案例：实现延迟队列的两种方法.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/31 实战：定时任务案例.md.html">31 实战：定时任务案例.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/32 实战：RediSearch 高性能的全文搜索引擎.md.html">32 实战：RediSearch 高性能的全文搜索引擎.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/33 实战：Redis 性能测试.md.html">33 实战：Redis 性能测试.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/34 实战：Redis 慢查询.md.html">34 实战：Redis 慢查询.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/35 实战：Redis 性能优化方案.md.html">35 实战：Redis 性能优化方案.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/36 实战：Redis 主从同步.md.html">36 实战：Redis 主从同步.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/37 实战：Redis哨兵模式（上）.md.html">37 实战：Redis哨兵模式（上）.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/38 实战：Redis 哨兵模式（下）.md.html">38 实战：Redis 哨兵模式（下）.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/39 实战：Redis 集群模式（上）.md.html">39 实战：Redis 集群模式（上）.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/40 实战：Redis 集群模式（下）.md.html">40 实战：Redis 集群模式（下）.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/41 案例：Redis 问题汇总和相关解决方案.md.html">41 案例：Redis 问题汇总和相关解决方案.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/42 技能学习指南.md.html">42 技能学习指南.md.html</a>
</li>
<li>
<a href="/专栏/Redis 核心原理与实战/43 加餐：Redis 的可视化管理工具.md.html">43 加餐：Redis 的可视化管理工具.md.html</a>
</li>
</ul>
</div>
</div>
<div class="sidebar-toggle" onclick="sidebar_toggle()" onmouseover="add_inner()" onmouseleave="remove_inner()">
<div class="sidebar-toggle-inner"></div>
</div>
<script>
function add_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.add('show')
}
function remove_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.remove('show')
}
function sidebar_toggle() {
let sidebar_toggle = document.querySelector('.sidebar-toggle')
let sidebar = document.querySelector('.book-sidebar')
let content = document.querySelector('.off-canvas-content')
if (sidebar_toggle.classList.contains('extend')) { // show
sidebar_toggle.classList.remove('extend')
sidebar.classList.remove('hide')
content.classList.remove('extend')
} else { // hide
sidebar_toggle.classList.add('extend')
sidebar.classList.add('hide')
content.classList.add('extend')
}
}
function open_sidebar() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.add('show')
overlay.classList.add('show')
}
function hide_canvas() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.remove('show')
overlay.classList.remove('show')
}
</script>
<div class="off-canvas-content">
<div class="columns">
<div class="column col-12 col-lg-12">
<div class="book-navbar">
<!-- For Responsive Layout -->
<header class="navbar">
<section class="navbar-section">
<a onclick="open_sidebar()">
<i class="icon icon-menu"></i>
</a>
</section>
</header>
</div>
<div class="book-content" style="max-width: 960px; margin: 0 auto;
overflow-x: auto;
overflow-y: hidden;">
<div class="book-post">
<p id="tip" align="center"></p>
<div><h1>14 有序集合使用与内部实现原理</h1>
<p>有序集合类型 (Sorted Set) 相比于集合类型多了一个排序属性 score（分值），对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序结合的元素值，一个是排序值。有序集合的存储元素值也是不能重复的，但分值是可以重复的。</p>
<p>当我们把学生的成绩存储在有序集合中时，它的存储结构如下图所示：</p>
<p><img src="assets/2020-02-28-031227.png" alt="学生存储值.png" /></p>
<p>下面我们先从有序集合的使用开始说起。</p>
<h3>1 基础使用</h3>
<h4>1）添加一个或多个元素</h4>
<p>语法：zadd key [NX|XX] [CH] [INCR] score member [score member ...] 示例：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zadd zset1 10 java
(integer) 1
127.0.0.1:6379&gt; zadd zset1 3 golang 4 sql 1 redis
(integer) 3
</code></pre>
<p>可以看出有序集合的添加是 <code>zadd 键值 分值1 元素值1 分值2 元素值2</code> 的形式添加的。</p>
<h4>2）查询所有元素列表</h4>
<p>语法：zrange key start stop [WITHSCORES] 示例：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zrange zset 0 -1
1) &quot;redis&quot;
2) &quot;mysql&quot;
3) &quot;java&quot;
</code></pre>
<p>其中 -1 表示最后一个元素，查询结果包含开始和结束元素。</p>
<h4>3）删除一个或多个元素(根据元素值)</h4>
<p>语法：zrem key member [member ...] 示例：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zrangebyscore zset1 0 -1 #查询所有元素
1) &quot;golang&quot;
2) &quot;redis&quot;
3) &quot;sql&quot;
4) &quot;java&quot;
127.0.0.1:6379&gt; zrem zset1 redis sql #删除元素：reids、sql
(integer) 2
127.0.0.1:6379&gt; zrange zset1 0 -1 #查询所有元素
1) &quot;golang&quot;
2) &quot;java&quot;
</code></pre>
<p>删除命令中如果包含了不存在的元素，并不会影响命令的正常执行，不存在的元素将会被忽略。</p>
<h4>4）查询某元素的 score 值</h4>
<p>语法：zscore key member 示例：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zscore zset1 redis
&quot;1&quot;
</code></pre>
<h4>5）查询 score 区间内元素</h4>
<p>语法：zrangebyscore key min max [WITHSCORES] [LIMIT offset count] 示例：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zrangebyscore zset1 3 10
1) &quot;golang&quot;
2) &quot;redis&quot;
3) &quot;sql&quot;
4) &quot;java&quot;
</code></pre>
<h4>6）查询某元素排名</h4>
<p>语法：zrank key member 示例：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zadd zset 5 redis 10 java 8 mysql #创建有序集合
(integer) 3
127.0.0.1:6379&gt; zrank zset java #查询元素排序
(integer) 2
127.0.0.1:6379&gt; zrank zset redis
(integer) 0
</code></pre>
<p>可以看出，排名是从 0 开始的，排名可以理解为元素排序后的下标值。</p>
<p>更多操作命令，详见附录部分。</p>
<h3>2 代码实战</h3>
<p>下面来看有序集合在 Java 中的使用，同样先添加 Jedis 框架，示例代码如下：</p>
<pre><code class="language-java">import redis.clients.jedis.Jedis;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class ZSetExample {
public static void main(String[] args) {
Jedis jedis = new Jedis(&quot;127.0.0.1&quot;, 6379);
Map&lt;String, Double&gt; map = new HashMap&lt;&gt;();
map.put(&quot;小明&quot;, 80.5d);
map.put(&quot;小红&quot;, 75d);
map.put(&quot;老王&quot;, 85d);
// 为有序集合(ZSet)添加元素
jedis.zadd(&quot;grade&quot;, map);
// 查询分数在 80 分到 100 分之间的人(包含 80 分和 100 分)
Set&lt;String&gt; gradeSet = jedis.zrangeByScore(&quot;grade&quot;, 80, 100);
System.out.println(gradeSet); // 输出：[小明, 老王]
// 查询小红的排名(排名从 0 开始)
System.out.println(jedis.zrank(&quot;grade&quot;, &quot;小明&quot;)); // 输出：1
// 从集合中移除老王
jedis.zrem(&quot;grade&quot;, &quot;老王&quot;);
// 查询有序集合中的所有元素(根据排名从小到大)
Set&lt;String&gt; range = jedis.zrange(&quot;grade&quot;, 0, -1);
System.out.println(range); // 输出：[小红, 小明]
// 查询有序集合中的所有元素(根据 score 从小到大)
Set&lt;String&gt; rangeByScore = jedis.zrangeByScore(&quot;grade&quot;, 0, 100);
System.out.println(rangeByScore);
}
}
</code></pre>
<h3>3 内部实现</h3>
<p>有序集合是由 ziplist (压缩列表) 或 skiplist (跳跃表) 组成的。</p>
<h4>1）ziplist</h4>
<p>当数据比较少时，有序集合使用的是 ziplist 存储的，如下代码所示：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zadd myzset 1 db 2 redis 3 mysql
(integer) 3
127.0.0.1:6379&gt; object encoding myzset
&quot;ziplist&quot;
</code></pre>
<p>从结果可以看出，有序集合把 myset 键值对存储在 ziplist 结构中了。 有序集合使用 ziplist 格式存储必须满足以下两个条件：</p>
<ul>
<li>有序集合保存的元素个数要小于 128 个；</li>
<li>有序集合保存的所有元素成员的长度都必须小于 64 字节。</li>
</ul>
<p>如果不能满足以上两个条件中的任意一个，有序集合将会使用 skiplist 结构进行存储。 接下来我们来测试以下，当有序集合中某个元素长度大于 64 字节时会发生什么情况？ 代码如下：</p>
<pre><code class="language-shell">127.0.0.1:6379&gt; zadd zmaxleng 1.0 redis
(integer) 1
127.0.0.1:6379&gt; object encoding zmaxleng
&quot;ziplist&quot;
127.0.0.1:6379&gt; zadd zmaxleng 2.0 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 1
127.0.0.1:6379&gt; object encoding zmaxleng
&quot;skiplist&quot;
</code></pre>
<p>通过以上代码可以看出，当有序集合保存的所有元素成员的长度大于 64 字节时，有序集合就会从 ziplist 转换成为 skiplist。</p>
<blockquote>
<p>小贴士：可以通过配置文件中的 zset-max-ziplist-entries（默认 128）和 zset-max-ziplist-value（默认 64）来设置有序集合使用 ziplist 存储的临界值。</p>
</blockquote>
<h3>2）skiplist</h3>
<p>skiplist 数据编码底层是使用 zset 结构实现的，而 zset 结构中包含了一个字典和一个跳跃表，源码如下：</p>
<pre><code class="language-c">typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
</code></pre>
<p>更多关于跳跃表的源码实现，会在后面的章节详细介绍。</p>
<h5>① 跳跃表实现原理</h5>
<p>跳跃表的结构如下图所示： <img src="assets/2020-02-28-031228.png" alt="有序集合-跳跃表.png" /></p>
<p>根据以上图片展示，当我们在跳跃表中查询值 32 时，执行流程如下：</p>
<ul>
<li>从最上层开始找，1 比 32 小，在当前层移动到下一个节点进行比较；</li>
<li>7 比 32 小，当前层移动下一个节点比较，由于下一个节点指向 Null，所以以 7 为目标，移动到下一层继续向后比较；</li>
<li>18 小于 32，继续向后移动查找，对比 77 大于 32，以 18 为目标，移动到下一层继续向后比较；</li>
<li>对比 32 等于 32，值被顺利找到。</li>
</ul>
<p>从上面的流程可以看出，跳跃表会想从最上层开始找起，依次向后查找，如果本层的节点大于要找的值，或者本层的节点为 Null 时，以上一个节点为目标，往下移一层继续向后查找并循环此流程，直到找到该节点并返回，如果对比到最后一个元素仍未找到，则返回 Null。</p>
<h5>② 为什么是跳跃表？而非红黑树？</h5>
<p>因为跳跃表的性能和红黑树基本相近，但却比红黑树更好实现，所有 Redis 的有序集合会选用跳跃表来实现存储。</p>
<h3>4 使用场景</h3>
<p>有序集合的经典使用场景如下：</p>
<ul>
<li>学生成绩排名</li>
<li>粉丝列表，根据关注的先后时间排序</li>
</ul>
<h3>5 小结</h3>
<p>通过本文的学习我们了解到，有序集合具有唯一性和排序的功能，排序功能是借助分值字段 score 实现的，score 字段不仅可以实现排序功能，还可以实现数据的赛选与过滤的功能。我们还了解到了有序集合是由 压缩列表 (ziplist) 或跳跃列表 (skiplist) 来存储的，当元素个数小于 128 个，并且所有元素的值都小于 64 字节时，有序集合会采取 ziplist 来存储，反之则会用 skiplist 来存储，其中 skiplist 是从上往下、从前往后进行元素查找的，相比于传统的普通列表，可能会快很多，因为普通列表只能从前往后依次查找。</p>
</div>
</div>
<div>
<div style="float: left">
<a href="/专栏/Redis 核心原理与实战/13 附录：更多集合操作命令.md.html">上一页</a>
</div>
<div style="float: right">
<a href="/专栏/Redis 核心原理与实战/15 附录：更多有序集合操作命令.md.html">下一页</a>
</div>
</div>
</div>
</div>
</div>
</div>
<a class="off-canvas-overlay" onclick="hide_canvas()"></a>
</div>
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v652eace1692a40cfa3763df669d7439c1639079717194" integrity="sha512-Gi7xpJR8tSkrpF7aordPZQlW2DLtzUlZcumS8dMQjwDHEnw9I7ZLyiOj/6tZStRBGtGgN6ceN6cMH8z7etPGlw==" data-cf-beacon='{"rayId":"709973cca9e63d60","version":"2021.12.0","r":1,"token":"1f5d475227ce4f0089a7cff1ab17c0f5","si":100}' crossorigin="anonymous"></script>
</body>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-NPSEEVD756"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'G-NPSEEVD756');
var path = window.location.pathname
var cookie = getCookie("lastPath");
console.log(path)
if (path.replace("/", "") === "") {
if (cookie.replace("/", "") !== "") {
console.log(cookie)
document.getElementById("tip").innerHTML = "<a href='" + cookie + "'>跳转到上次进度</a>"
}
} else {
setCookie("lastPath", path)
}
function setCookie(cname, cvalue) {
var d = new Date();
d.setTime(d.getTime() + (180 * 24 * 60 * 60 * 1000));
var expires = "expires=" + d.toGMTString();
document.cookie = cname + "=" + cvalue + "; " + expires + ";path = /";
}
function getCookie(cname) {
var name = cname + "=";
var ca = document.cookie.split(';');
for (var i = 0; i < ca.length; i++) {
var c = ca[i].trim();
if (c.indexOf(name) === 0) return c.substring(name.length, c.length);
}
return "";
}
</script>
</html>
Reference in New Issue View Git Blame Copy Permalink