[数据结构与算法]redis底层数据结构及其应用

redis底层数据结构

我们都知道redis有5种数据结构：String、list、hash、set、zset
但是作为一名优秀的程序员，不仅仅知道这5种数据结构，还要知道这5种数据结构底层的实现原理

String

127.0.0.1:6379> set key 111
OK
127.0.0.1:6379> object encoding key
"int"

当对一个key设置值为整形的时候，通过查看底层编码，其是一个int类型

127.0.0.1:6379> set key ewrw11
OK
127.0.0.1:6379> object encoding key
"embstr"

当存储的类型不是整形的时候，其类型是embstr

127.0.0.1:6379> set key qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
OK
127.0.0.1:6379> object encoding key
"raw"

当操作的字节数超过44bit时，其数据结构是raw

127.0.0.1:6379> set key qwe
OK
127.0.0.1:6379> object encoding key
"embstr"
127.0.0.1:6379> append key 123
(integer) 6
127.0.0.1:6379> object encoding key
"raw"

当对其中一个字符进行append操作时，其数据结构变成raw，即使其长度没有超过44bit

SDS
redis底层对于String数据结构底层并没有用c语言中的char数组结构，而是自己定义了一个数据结构SDS，SDS称为「简单动态字符串」，对于SDS中的定义在Redis的源码中有的三个属性int len、int free、char buf[]

len：表示字符串的长度
free：表示所剩空间大小
buf：表示保存字符串的每一个字符

优点：
1、使用该数据结构能够保证数据的安全性，如果采用char的话，c中会使用’ \0 '表示该字符串的结束，如果redis要存储的字符串中存在该字符，就会导致该字符以后的数据丢失；自定义的SDS数据结构不会以该字符作为结尾，而是使用len来表示字符的结尾。
2、使用SDS数据结构查询字符串的长度时间复杂度为O(1)，使用char的时间复杂度为O(n)
3、当对数据进行操作的时候，发现存储的空间不足时，就会进行扩容，扩容的长度是新操作字符串的长度的2倍，通过free还能对空闲空间进行一个管理

list

list底层使用的数据结构是ziplist和quicklist，在老版本中用linkedlist取代quicklist

ziplist
压缩列表

压缩列表并不是采用某种压缩算法来对数据进行压缩，而是通过一整块连续的空间来存储数据，节省空间

压缩列表中每一个节点表示的含义如下所示：

1. zlbytes：4个字节的大小，记录压缩列表占用内存的字节数。
2. zltail：4个字节大小，记录表尾节点距离起始地址的偏移量，用于快速定位到尾节点的地址。
3. zllen：2个字节的大小，记录压缩列表中的节点数。
4. entry：表示列表中的每一个节点
5. zlend：表示压缩列表的特殊结束符号’0xFF’。

再压缩列表中每一个entry节点又有三部分组成，包含previous_entry_ength、encoding、content。

• previous_entry_ength表示前一个节点entry的长度，可用于计算前一个节点的真实地址，因为他们的地址是连续的。
• encoding：这里保存的是content的内容类型和长度。
• content：content保存的是每一个节点的内容。

quicklist（listedlist）
我们来看看listedlist和quicklist的数据结构

listedlist和quicklist是采用双向链表，每一个节点都有指向前一个节点和后一个节点的指针，头节点head的prev和尾节点的next都指向null，所以该双向链表是一个无环的数据结构

Redis中链表的特性：

1、每一个节点都有指向前一个节点和后一个节点的指针。
2、头节点和尾节点的prev和next指针指向为null，所以链表是无环的。
3、链表有自己长度的信息，获取长度的时间复杂度为O(1)。

hash

hash采用ziplist和hashtable

ziplist数据结构在上文中已经讲解过

hashtable
如果理解HashMap的数据结构的话，hashtable的数据结构就很好理解了，两种数据结构相差无几，两者在新增时都会通过key计算出数组下标，不同的是计算法方式不同，HashMap中是以hash函数的方式，而hashtable中计算出hash值后，还要通过sizemask 属性和哈希值再次得到数组下标。

我们知道hash表最大的问题就是hash冲突，为了解决hash冲突，假如hashtable中不同的key通过计算得到同一个index，就会形成单向链表（「链地址法」），如下图所示：

在字典的底层实现中，value对象以每一个dictEntry的对象进行存储，当hash表中的存放的键值对不断的增加或者减少时，需要对hash表进行一个扩展或者收缩。

这里就会和HashMap一样也会就进行rehash操作，进行重新散列排布

扩展后的大小是扩展前的大小的二倍的第一个2的整数幂

渐进式rehash
假如在rehash的过程中，数据量是非常大的，那一次性操作完会导致其他的数据操作阻塞，出现卡顿的情况，所有redis进行rehash操作的时候会在后台进行渐进式的rehash，分多次进行，知道都操作完成。

在rehash的过程中，如果进行增操作的时候，会在新表中进行添加，修改的时候两个表都会进行修改，删除的时候，在老表中进行删除

set

set底层的数据结构是hashtable和intset

hashtable上文中已经讲解过了，接下来看下intset数据结构

intset
inset也叫做整数集合，用于保存整数值的数据结构类型，它可以保存int16_t、int32_t 或者int64_t 的整数值。

在整数集合中，有三个属性值encoding、length、contents[]，分别表示编码方式、整数集合的长度、以及元素内容，length就是记录contents里面的大小。

在整数集合新增元素的时候，若是超出了原集合的长度大小，就会对集合进行升级，具体的升级过程如下：

1、首先扩展底层数组的大小，并且数组的类型为新元素的类型。
2、然后将原来的数组中的元素转为新元素的类型，并放到扩展后数组对应的位置。
3、整数集合升级后就不会再降级，编码会一直保持升级后的状态。

zset

zset底层是采用ziplist和skiplist的数据结构
ziplist数据结构上边已经讲过

skiplist（跳跃表）
该数据结构是一个有序的数据结构，通过每一个节点维持多个指向其他节点的指针，从而达到快速访问节点的目的。

skiplist有以下几种特点：
1、有很多组层，每一层的节点密集，最上层的节点数最为稀疏
2、每一个节点都会指向同一层的下一个节点以及下一层的相同位置的节点
3、每一层都是一个有序链表，至少有头节点和尾节点两个节点
4、如果一个节点在某一层出现，那么该以下的所有链表同一个位置都会出现该节点

在跳跃表的结构中有head和tail表示指向头节点和尾节点的指针，能快速的实现定位。level表示层数，len表示跳跃表的长度，BW表示后退指针，在从尾向前遍历的时候使用。
BW下面还有两个值分别表示分值（score）和成员对象（各个节点保存的成员对象）。

跳跃表的实现中，除了最底层的一层保存的是原始链表的完整数据，上层的节点数会越来越少，并且跨度会越来越大。

跳跃表的上面层就相当于索引层，都是为了找到最后的数据而服务的，数据量越大，条表所体现的查询的效率就越高，和平衡树的查询效率相差无几。

应用

String:

#分布式锁
127.0.0.1:6379> setnx key true
(integer) 1
127.0.0.1:6379> setnx key true
(integer) 0
127.0.0.1:6379> del key
(integer) 1
#防止程序意外终止导致死锁
127.0.0.1:6379> set ww true ex 10 nx
OK

计数器

127.0.0.1:6379> incrby key 1000
(integer) 1000
127.0.0.1:6379> get key
"1000"
127.0.0.1:6379> incr key
(integer) 1001

hash:

商品购物车

127.0.0.1:6379> hset key1 phone 1
(integer) 1
#批量操作
127.0.0.1:6379> hmset key1 erji 1 word 1 pc 2
OK
127.0.0.1:6379> hget key1
(error) ERR wrong number of arguments for 'hget' command
127.0.0.1:6379> hget key1 phone
"1"
#获取商品的数量
127.0.0.1:6379> hlen key1
(integer) 4
#获取所有的商品信息
127.0.0.1:6379> hgetall key1
1) "phone"
2) "1"
3) "erji"
4) "1"
5) "word"
6) "1"
7) "pc"
8) "2"

list:

微博消息和微信公众号消息

127.0.0.1:6379> lpush msg:all msg1 msg2 msg3
(integer) 3
127.0.0.1:6379> lrange msg 0
(error) ERR wrong number of arguments for 'lrange' command
127.0.0.1:6379> lrange msg 0 -1
(empty list or set)
127.0.0.1:6379> lrange msg:all 0 -1
1) "msg3"
2) "msg2"
3) "msg1"

set

#添加
127.0.0.1:6379> sadd key1 1 2 3
(integer) 3
127.0.0.1:6379> sadd key2 2 3
(integer) 2
#求交集
127.0.0.1:6379> sinter key1 key2
1) "2"
2) "3"
#求并集
127.0.0.1:6379> sunion key1 key2
1) "1"
2) "2"
3) "3"
#求差集
127.0.0.1:6379> sdiff key1 key2
1) "1"
#查看key的成员
127.0.0.1:6379> smembers key1
1) "1"
2) "2"
3) "3"
#查看成员个数
127.0.0.1:6379> scard key1
(integer) 3
#判断某个值是否在某个key里
127.0.0.1:6379> sismember key1 1
(integer) 1
127.0.0.1:6379> sismember key1 5
(integer) 0
#从集合中选出n个元素，元素不删除
127.0.0.1:6379> srandmember key1 2
1) "1"
2) "3"
#从集合中选出n个元素，在集合中删除
127.0.0.1:6379> spop key2
"2"
127.0.0.1:6379> spop key2
"3"

微信抽奖小程序
sadd key1 m1 m2 …
smembers key1
srandmember key1 n/spop key1 n

微信微博点赞、收藏、标签

微博微信关注模型
通过交集查询共同好友
通过差集查看可能认识的人

zset

通过zset操作热搜排行榜
当有读者点击该条新闻时，将该热点分数自增
zincrby redian1 1 新闻1
查看前10热搜 ：zvevrange按照分数倒叙排列
zrevrange redian1 0 9 withscores

7日榜单计算
zunionstore redian7day 7 redian1 redian2 redian3 redian4 … redian7
通过下面一条命令查看7日内前10条热点数据
zrevrange redian7day 0 9 withscores

海量数据统计（日活）

bitmap

# setbit key 用户id 0/1    （1 : 上线，0 ： 下线）
127.0.0.1:6379> setbit rihuo 1 1
(integer) 0
127.0.0.1:6379> setbit rihuo 10 1
(integer) 0
127.0.0.1:6379> getbit rihuo 1
(integer) 1
127.0.0.1:6379> bitcount rihuo
(integer) 2