Redis底层数据结构

String底层数据结构

sds：simple dynamic string

• 二进制安全的数据结构

C语言字符串定义  char data[] = "xiaoming\0"（redis底层C语言实现），因为redis要应用到java，php等各种语言，例如：有时候传的字符串自身包含"\0"，xiao\0ming，如果按照C语言的string结构"\0"后面的会舍弃，所以是不安全的

• 提供内存预分配机制，避免了频繁的内存分配

K-V存储形式与HashMap非常类似，成倍扩容，渐进式动态扩容

数据不是立马迁移过去，客户端取数据时，先从原来的取，有的话取出，并复制到新的，如果没有客户端去访问数据，redis后台也会有定时去慢慢迁移。

亿级用户日活统计 bitmap

使用位运算，0,1代表两种状态来统计

例：0 1 1 0 1 0 0 1 1 1        (0,1) -->用户状态

       1 2 3 4 5 6 7 8 9 10       offset-->userId

key可以用日期表示

常用指令：

设置用户状态：setbit key offset value setbit 20220101 5 0

获取用户状态：getbit key offset getbit 20220101 5

获取状态为1的数量：bigcount 20220101

注意：userId数据量要比较大，且尽量是连续的，如果只存1和65535，最大会开辟65535对应的空间大小，这样对空间是浪费的。

List结构

没有使用链表的原因：

1. 每个指令占8byte，占内存
2. 内存会产生碎片

使用zipList和quickList（双向链表）

zipList：

 如果修改或者新增一个元素会重新复制一个ziplist，并且把原来的清除，如果数据量比较大，那就会浪费空间，所以不会让ziplist存所以数据。

借助quicklist：

将ziplist分成多个ziplist，形成每个ziplist的双向链表

 可以通过设置每个ziplist的最大容量：list-max-ziplist-size

还可以设置quicklist的数据压缩：list-compress-depth

0代表不压缩，1代表前一个和后一个不压缩，其余全压缩，2代表前两个和后两个，以此类推。

Hash结构

当数据量比较小时，或单个元素比较小时，底层用ziplist存储，数据大小和元素数量阈值可以通过设置如下参数设置

• hash-max-ziplist-entries 512 当ziplist元素个数超过512，将改成hashtable编码
• hash-max-ziplist-value 64 当元素大小超过64byte，将改成hashtable编码

Set结构 

set为无序的，如果数据都为整形时，set用inset结构存储，且是由序的

当出现下面两种情况，用hashtable存储

• 元素个数大于set-max-inset-entries    inset能存储的最大元素数
• 元素无法用整数表示

inset数据结构

 ZSet数据结构

数据结构：字典（dict）+ 跳表（skiplist），当数据量比较小时用ziplist存储

• zset-max-ziplist-entries 128  元素个数超过128，用skipkist编码
• zset-max-ziplist-value 64  单个元素大小超过64byte，用skiplist编码

 跳表原理：

 当查询8时，只需要6步

通过上一层，没隔一个元素做一次索引

假如有N个元素

第一层索引：N/2个

第二层索引：

第K层索引：

顶层如果有2个：12个元素可以分3层

*forward：指向同层的下一个节点的指针

span：两个节点之间的距离（跨几个节点）

redis每个节点的层高是随机生成的，层高越高，概率越小，与跳表原理略有所不同，目的可能是为减少索引的存储合理使用内存