Redis基本数据结构
前言
Github：https://github.com/HealerJean
1、Redis使用场景
1、缓存，几乎在所有大型的网站都有使用，可以设置键值过期时间
2、计数器应用，这个我们公司就有用到，用来拦截访问次数的。
3、排行榜系统，Redis提供了list和Zset有序集合数据结构，合理使用这个就可以构建各种排行榜系统
4、消息队列，这个在netty和websocket的时候有使用过，通过coverAndSend进行队列的监听并发送
2、数据结构和编码
| 命令 | 说明 | 解释 |
|---|---|---|
keys * |
查看当前库的所有数据 | |
dbsize |
查看当前库有几个数据 | |
flushdb |
将当前库数据清除 | |
flushall |
清除所有库的信息 | |
select 0、1、...15 |
移动仓库（一共16个） | |
move keyName 2 |
将数据移动到其他库中,例如3库 | |
type keyName |
查看数据类型 | |
object encoding keyName |
查看内存编码 | |
ttl keyName |
查看过期时间 | -1永不过期 -2已经过期 |
expire keyName 10 |
设置k1过期时间,为10秒 | |
persist keyName |
将过期时间清除，永不过期 | |
exists keyName |
看看是否存在keyName |
2.1、string
解释：这里的字符串千万不要以为真的是字符串，可以是字符串，也可以是数字（整数，浮点数，甚至可以是二进制)
2.1.1、常用命令
| 命令 | 说明 | 解释 |
|---|---|---|
set keyName keyValue |
添加数据 | |
incr keyName |
数据递增递（只能是数字，不能是字符串） | |
incrby keyName 4 |
增加4 | |
decr keyName |
数据递增递（只能是数字，不能是字符串） | |
decrby keyName 4 |
减少4 | |
mset keyName1 keyValue1 keyName2 keyValue2 |
一次添加多个变量多条数据 | |
mget keyName1 keyName2 |
一次读取多个数据 | |
del str |
删除数据 | |
append keyName keyValue |
追加数据 | |
getrange keyName 0 -1 |
显示全部 | |
getrange keyName 0 3 |
包头不包尾 | |
setrange keyName 1 xxx |
在序列1插入字符串xxx | |
strlen keyName |
查看数据长度大学 | |
setex keyName 10 abc |
设置过期时间和值 |
2.1.2、使用场景：
计数，共享session，限速，用户信息
2.1.3、数据结构
String类型的数据结构存储方式有三种
int、raw、embstr。那么这三种存储方式有什么区别呢？
数字类型：Redis中规定假如存储的是「整数型值」，比如set num 123这样的类型，就会使用 int的存储方式进行存储
若是「字符串长度小于等于32个字节」就会将encoding改为embstr来保存字符串。
存储的「字符串是一个字符串值并且长度大于32个字节」就会使用SDS（simple dynamic string）方式进行存储，并且encoding设置为raw
SDS称为「简单动态字符串」，对于SDS中的定义在Redis的源码中有的三个属性int len、int free、char buf[]。
Redis使用SDS作为存储字符串的类型肯定是有自己的优势，SDS与c语言的字符串相比，SDS对c语言的字符串做了自己的设计和优化，具体优势有以下几点：
（1）c语言中的字符串并不会记录自己的长度，因此「每次获取字符串的长度都会遍历得到，时间的复杂度是O(n)」，而Redis中获取字符串只要读取len的值就可，时间复杂度变为O(1)。
（2）「c语言」中两个字符串拼接，若是没有分配足够长度的内存空间就「会出现缓冲区溢出的情况」；而「SDS」会先根据len属性判断空间是否满足要求，若是空间不够，就会进行相应的空间扩展，所以「不会出现缓冲区溢出的情况」。
（3）SDS还提供「空间预分配」和「惰性空间释放」两种策略。在为字符串分配空间时，
分配的空间比实际要多，这样就能「减少连续的执行字符串增长带来内存重新分配的次数」。 具体的空间预分配原则是：「当修改字符串后的长度len小于1MB，就会预分配和len一样长度的空间，即len=free；若是len大于1MB，free分配的空间大小就为1MB」。
当字符串被缩短的时候，SDS也不会立即回收不适用的空间，而是通过free属性将不使用的空间记录下来，等后面使用的时候再释放。
（4）SDS是二进制安全的，除了可以储存字符串以外还可以储存二进制文件（如图片、音频，视频等文件的二进制数据）；而c语言中的字符串是以空字符串作为结束符，一些图片中含有结束符，因此不是二进制安全的。
| c语言字符串 | SDS |
|---|---|
| 获取长度的时间复杂度为O(n) | 获取长度的时间复杂度为O(1) |
| 不是二进制安全的 | 是二进制安全的 |
| 只能保存字符串 | 还可以保存二进制数据 |
| n次增长字符串必然会带来n次的内存分配 | n次增长字符串内存分配的次数<=n |
2.2、list
2.2.1、常用命令
| 命令 | 说明 | 解释 |
|---|---|---|
lpush/rpush keyName 1 2 4 5 6 |
l进入r出，左进右出 | |
lpushx/rpushx keyName valus |
只能插入已经存在的key,且一次只能插入一次 | |
lset/rset keyName 1 x |
从左到右/从右到左，根据索引替换 | |
lpop/rpop keyName |
从左/右出 | |
blpop/brpop timeout keyName |
阻塞版本,等几秒内返回，如果等于0将一直阻塞下去 | |
2.2.2、使用场景
1、消息队列：， lpush （左侧放）和brpop （右侧拿）就可以实现消息队
2.2.3、数据结构
Redis中的列表在3.2之前的版本是使用
ziplist和linkedlist进行实现的。在3.2之后的版本就是引入了quicklist。
linkedlist是一个双向链表，他和普通的链表一样都是由指向前后节点的指针。插入、修改、更新的时间复杂度尾O(1)，但是查询的时间复杂度确实O(n)。
2.3、hash
2.3.1、常用命令
| 命令 | 说明 | 解释 |
|---|---|---|
hset keyName name healerjean |
添加数据 | |
hmset keyName name HealerJean age 26 |
给一个变量添加多个值 | |
hdel keyName name |
删除相关字段 | |
hget keyName name |
获取数据 | |
hmget keyName name age |
获取一个map的多个值 | |
hgetall keyName |
查看map的所有数据 | |
hlen keyName |
取得hash的长度 |
2.3.2、使用场景
1、存储用户信息，更加直观，节省空间
2.3.3、数据结构
Hash对象的实现方式有两种分别是
ziplist、hashtable，其中hashtable的存储方式key是String类型的，value也是以key value的形式进行存储。
字典类型的底层就是hashtable实现的，明白了字典的底层实现原理也就是明白了hashtable的实现原理，hashtable的实现原理可以于HashMap的是底层原理相类比。
压缩列表（ziplist）是一组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据。
压缩列表是列表键和哈希键底层实现的原理之一，「压缩列表并不是以某种压缩算法进行压缩存储数据，而是它表示一组连续的内存空间的使用，节省空间」，压缩列表的内存结构图如下：
2.4、set
2.3.1、常用命令
| 命令 | 说明 | 解释 |
|---|---|---|
sadd keyName a b c |
添加数据 | |
srem keyName a b |
删除元素 | |
scard keyName |
计算元素个数 | |
smembers keyName |
获取所有元素 | |
sismember keyName a |
是否存在 | |
2.3.1、使用场景
1、存储不重复的数据
2.3.3、数据结构
Set的底层实现是「ht和intset」，ht（哈希表）前面已经详细了解过，下面我们来看看inset类型的存储结构。
inset也叫做整数集合，用于保存整数值的数据结构类型，它可以保存int16_t、int32_t 或者int64_t 的整数值。
2.5、zset
有序集合：看到这个可能会有一点陌生，确实，我也刚开始看到时候头大呢，他和索引下标排序作为依据不同，他给每个元素设置一个分数，作为排序的依据，它给我们提供了获取指定的分数和元素范围查询，计算成员排名等功能。
2.5.1、常用命令
| 命令 | 说明 | 解释 |
|---|---|---|
zadd keyName 251 healerjean |
添加数据 | |
zadd keyName 1 tom 25 healer |
添加多个数据 | |
zrem keyName healerjean |
删除元素 | |
zscore keyName healerjean |
计算某个成员的分数 | |
zrank keyName healejean |
返回用户排名 | |
zcard keyName |
计算成员个数 | |
zincrby keyName 9 healejean |
增加成员的分数 | |
zrange keyName 0 2 |
返回指定排名范围的成员 | |
zrangebyscore keyName 200 221 |
返回指定分数范围的成员 | |
zcount keyName 100 200 |
返回制定分数范围的成员个数 | |
2.5.2、使用场景
1、排行榜系统
2.5.3、数据结构
ZSet是有序集合，从上面的图中可以看到ZSet的底层实现是
ziplist和skiplist实现的，ziplist上面已经详细讲过，这里来讲解skiplist的结构实现。
skiplist也叫做「跳跃表」，跳跃表是一种有序的数据结构，它通过每一个节点维持多个指向其它节点的指针，从而达到快速访问的目的。
skiplist由如下几个特点：
1、有很多层组成，由上到下节点数逐渐密集，最上层的节点最稀疏，跨度也最大。
2、每一层都是一个有序链表，至少包含两个节点，头节点和尾节点。
3、每一层的每一个每一个节点都含有指向同一层下一个节点和下一层同一个位置节点的指针。
4、如果一个节点在某一层出现，那么该以下的所有链表同一个位置都会出现该节点。
2.5.3.1、skiplsit
SkipList的设计初衷是作为替换平衡树的一种选择。
我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。
但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，Skip需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。
查询：
比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤:
1、从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1
2、然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0
3、在结点17上，level==0索引到19,查找完毕。
4、如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败
插入：
其实插入节点的关键就是找到合适的插入位置，即从所有小于待插入节点key值的节点中，找出最大的那个，所以插入节点的过程如下:
- 查找合适的插入位置，比如上图中要插入key为17的结点，就需要一路查找到12,由于12 < 17,而12的下一个结点19 > 17,因而满足条件
- 创建新结点，并且产生一个在1~MAX_LEVEL之间的随机level值作为该结点的level
- 调整指针指向
移除
- 查找到指定的结点，如果没找到则返回
- 调整指针指向
- 释放结点空间
