【起】Redis基础篇——基本数据结构之ZSet，Bitmap…

距离过年那会闲在家更新的 MySQL 系列已经过去一段时间了&＃xff0c;这段时间一直在忙其他的&＃xff0c;所以博客的更新也就搁置了&＃xff0c;但是一直在想着要更新啥内容比较好&＃xff0c;刚好朋友给了我一本 Redis 的书籍&＃xff0c;我就打算看完结合官方的文档总结一下&＃xff0c;分享给大家&＃xff0c;如果有什么不对的地方请指正。

Redis 系列&＃xff0c;我想以“起承转合”的形式来更新&＃xff0c;不过不一定是四篇噢&＃xff0c;因为篇幅有限&＃xff0c;太长怕你们没有耐心看完&＃xff0c;可能《起》篇就分为几篇博文来叙述了&＃xff0c;我也会对其进行规整&＃xff0c;方便大家看完能更好的吸收&＃xff0c;毕竟写文章的我能得到各位观看我的文章&＃xff0c;是我的荣幸&＃xff0c;我必须得对大家负责的嘛~

话归正题&＃xff0c;Redis 应该很多人都有用过&＃xff08;没用过应该看这篇也能看得懂&＃xff0c;但是一些基本理论就得自己上网百度啦&＃xff09;。至于 Redis 是什么&＃xff0c;有什么好处&＃xff0c;怎么用&＃xff0c;那就继续往下看吧~本文会侧重于让大家对Redis 基本数据类型的操作命令&＃xff0c;底层存储结构以及其应用场景得到一定的认知。

附上基础篇的脑图&＃xff08;上传平台有压缩&＃xff0c;有兴趣可以到我的公众号【6曦轩】领取原图&＃xff09;

今天这一篇章给大家介绍一下 Redis 的基本数据类型&＃xff08;高阶的暂不介绍&＃xff09;。

篇幅有点长&＃xff0c;我分了几篇来写&＃xff0c;这篇是继前面两章节之后的&＃xff0c;主要介绍 Zset 以及 Bitmap。

Redis 基本数据类型&＃xff08;ZSet&＃xff0c;Bitmap…&＃xff09;

ZSet 有序集合

存储类型

sorted set&＃xff0c;有序的 set&＃xff0c;每个元素有个 score。
score 相同时&＃xff0c;按照 key 的 ASCII 码排序。
数据结构对比&＃xff1a;

操作命令

添加元素
zadd myzset 10 java 20 php 30 ruby 40 cpp 50 python

获取全部元素
zrange myzset 0 -1 withscores
zrevrange myzset 0 -1 withscores

根据分值区间获取元素
zrangebyscore myzset 20 30

移除元素
也可以根据 score rank 删除
zrem myzset php cpp

统计元素个数
zcard myzset

分值递增
zincrby myzset 5 python

根据分值统计个数
zcount myzset 20 60

获取元素 rank
zrank myzset java

获取元素 score
zsocre myzset java

也有倒序的 rev 操作&＃xff08;reverse&＃xff09;

存储&＃xff08;实现&＃xff09;原理

同时满足以下条件时使用 ziplist 编码&＃xff1a;

• 元素数量小于 128 个

• 所有 member 的长度都小于 64 字节

在 ziplist 的内部&＃xff0c;按照 score 排序递增来存储。插入的时候要移动之后的数据。

对应 redis.conf 参数&＃xff1a;
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

超过阈值之后&＃xff0c;使用 skiplist&＃43;dict 存储。

• 问题&＃xff1a;什么是 skiplist&＃xff1f;

我们先来看一下有序链表&＃xff1a;

在这样一个链表中&＃xff0c;如果我们要查找某个数据&＃xff0c;那么需要从头开始逐个进行比较&＃xff0c;直到找到包含数据的那个节点&＃xff0c;或者找到第一个比给定数据大的节点为止&＃xff08;没找到&＃xff09;。也就是说&＃xff0c;时间复杂度为 O(n)。同样&＃xff0c;当我们要插入新数据的时候&＃xff0c;也要经历同样的查找过程&＃xff0c;从而确定插入位置。

而二分查找法只适用于有序数组&＃xff0c;不适用于链表。

假如我们每相邻两个节点增加一个指针&＃xff08;或者理解为有三个元素进入了第二层&＃xff09;&＃xff0c;让指针指向下下个节点。

这样所有新增加的指针连成了一个新的链表&＃xff0c;但它包含的节点个数只有原来的一半&＃xff08;上图中是 7, 19, 26&＃xff09;。在插入一个数据的时候&＃xff0c;决定要放到那一层&＃xff0c;取决于一个算法&＃xff08;在 redis 中 t_zset.c 有一个 zslRandomLevel 这个方法&＃xff09;。

现在当我们想查找数据的时候&＃xff0c;可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时&＃xff0c;再回到原来的链表中的下一层进行查找。比如&＃xff0c;我们想查找 23&＃xff0c;查找的路径是沿着下图中标红的指针所指向的方向进行的&＃xff1a;

1. 23 首先和 7 比较&＃xff0c;再和 19 比较&＃xff0c;比它们都大&＃xff0c;继续向后比较。

2. 但 23 和 26 比较的时候&＃xff0c;比 26 要小&＃xff0c;因此回到下面的链表&＃xff08;原链表&＃xff09;&＃xff0c;与 22 比较。

3. 23 比 22 要大&＃xff0c;沿下面的指针继续向后和 26 比较。23 比 26 小&＃xff0c;说明待查数据23 在原链表中不存在

在这个查找过程中&＃xff0c;由于新增加的指针&＃xff0c;我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。这就是跳跃表。

• 为什么不用 AVL 树或者红黑树&＃xff1f;

因为 skiplist 更加简洁。

源码&＃xff1a;server.h

typedef struct zskiplistNode {sds ele; /* zset 的元素 */double score; /* 分值 */struct zskiplistNode *backward; /* 后退指针 */struct zskiplistLevel {struct zskiplistNode *forward; /* 前进指针&＃xff0c;对应 level 的下一个节点 */ unsigned long span; /* 从当前节点到下一个节点的跨度&＃xff08;跨越的节点数&＃xff09; */} level[]; /* 层 */
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail; /* 指向跳跃表的头结点和尾节点 */ unsigned long length; /* 跳跃表的节点数 */ int level; /* 最大的层数 */
} zskiplist;typedef struct zset {dict *dict;zskiplist *zsl;
} zset;


随机获取层数的函数&＃xff1a;

源码&＃xff1a;t_zset.c

int zslRandomLevel(void) {int level &＃61; 1;while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level &＃43;&＃61; 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}


应用场景

• 排行榜
  id 为 6001 的新闻点击数加 1&＃xff1a;zincrby hotNews:20190926 1 n6001
  获取今天点击最多的 15 条&＃xff1a;zrevrange hotNews:20190926 0 15 withscores

其他数据结构简介

https://redis.io/topics/data-types-intro

BitMaps

Bitmaps 是在字符串类型上面定义的位操作。一个字节由 8 个二进制位组成。

set k1 a

获取 value 在 offset 处的值&＃xff08;a 对应的 ASCII 码是 97&＃xff0c;转换为二进制数据是 01100001&＃xff09;
getbit k1 0

修改二进制数据&＃xff08;b 对应的 ASCII 码是 98&＃xff0c;转换为二进制数据是 01100010&＃xff09;

setbit k1 6 1
setbit k1 7 0
get k1


统计二进制位中 1 的个数
bitcount k1

获取第一个 1 或者 0 的位置

bitpos k1 1
bitpos k1 0


BITOP 命令支持 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种参数&＃xff1a;

BITOP AND destkey srckey1 … srckeyN &＃xff0c;对一个或多个 key 求逻辑与&＃xff0c;并将结果保存到 destkey

BITOP OR destkey srckey1 … srckeyN&＃xff0c;对一个或多个 key 求逻辑或&＃xff0c;并将结果保存到 destkey

BITOP XOR destkey srckey1 … srckeyN&＃xff0c;对一个或多个 key 求逻辑异或&＃xff0c;并将结果保存到 destkey

BITOP NOT destkey srckey&＃xff0c;对给定 key 求逻辑非&＃xff0c;并将结果保存到 destkey

应用场景&＃xff1a;

• 用户访问统计
• 在线用户统计
• Hyperloglogs

Hyperloglogs&＃xff1a;提供了一种不太准确的基数统计方法&＃xff0c;比如统计网站的 UV&＃xff0c;存在一定的误差。- --------
HyperLogLogTest.java

• Streams

5.0 推出的数据类型。支持多播的可持久化的消息队列&＃xff0c;用于实现发布订阅功能&＃xff0c;借鉴了 kafka 的设计。

有问题&＃xff1f;可以给我留言或私聊
有收获&＃xff1f;那就顺手点个赞呗~

当然&＃xff0c;也可以到我的公众号下「6曦轩」&＃xff0c;

回复“学习”&＃xff0c;即可领取一份
【Java工程师进阶架构师的视频教程】~

回复“面试”&＃xff0c;可以获得&＃xff1a;
【本人呕心沥血整理的 Java 面试题】

回复“MySQL脑图”&＃xff0c;可以获得
【MySQL 知识点梳理高清脑图】

还有【阿里云】【腾讯云】的购买优惠噢~具体请联系我

曦轩我是科班出身的程序员&＃xff0c;php&＃xff0c;Android以及硬件方面都做过&＃xff0c;不过最后还是选择专注于做 Java&＃xff0c;所以有啥问题可以到公众号提问讨论&＃xff08;技术情感倾诉都可以哈哈哈&＃xff09;&＃xff0c;看到的话会尽快回复&＃xff0c;希望可以跟大家共同学习进步&＃xff0c;关于服务端架构&＃xff0c;Java 核心知识解析&＃xff0c;职业生涯&＃xff0c;面试总结等文章会不定期坚持推送输出&＃xff0c;欢迎大家关注~~~