Redis基础与高级数据结构
一、string
- 基本原理：字符数组，动态字符串，预分配冗余空间减少内存频繁分配
- 扩容原理：长度<1MB时2倍扩容，长度>1MB时一次扩1MB，字符串最大长度512MB
- 数据结构：
- struct SDS<T> { T capacity; T len ; byte flags; byte[] content;}
- 长度特别短embstr结构，长度超过44字节时raw的结构
- embstr内存上连续一次内存分配，raw内存上不连续二次内存分配，Redis对象头指针指向String内存地址
- 44字节改变结构：64-Redsi对象头（16字节）-String对象头（3字节）-字符串末尾NULL（1字节）=44字节
二、list
基本结构：ziplist、quicklist（个数大于512或长度超过64）
-
ziplist数据结构：
zlbytes zltail_offset zllengt entry ... entry zlend 总字节数 最后个元素到第一个的偏移量 元素个数 元素1 ... 元素n 列表结束符 - ziplist是一块连续的空间，元素之间紧挨着储存
- entry的结构:struct entry{int<var> prevlen; int<var> encoding; optional byte[] content;},prevlen为前一个元素的长度，encodeing为编码类型，用于标识内容类型和长度，如果对于小的整数来说，encoding低位中就保存内容，不用保存在content中
- entry中的prevlen，当存储的字符串长度小于254字节，使用1字节表示长度，
大于254个字节，使用5个字节标识长度，ziplist添加和删除节点会引发联机更新的问题
-
quicklist数据结构：
- 之前采用linklist后由于指针大小和每次内存单独分配，改用quicklist
- ziplist默认长度为8KB，默认不压缩，可以配置使用LZF算法进行压缩
三、hash
1.基本结构：ziplist、数组+链表（个数大于512或长度超过64）
2.扩容方式：为追求性能采用渐进式rehash策略，同时保留新旧2个hash结构
3.扩容原理：哈希扩容的时候会有卡顿，所有同时保留现有哈希和扩容缩容后的哈希，在原哈希没有找到再另一个哈希再进行查找，在定时任务以及后续的hash操作指令中渐渐的将旧数组的元素迁移到新数组。
四、set
1.数据结构：intset、哈希的特殊结构，所有的value都是NULL（个数大于512）
intset结构，动态调整类型为uint16~uint64的数组
| encoding | length | value | value | ... | value |
|---|
五、zset
1.数据结构：ziplist、哈希（存储key-value）+跳跃列表（提供排序）（个数大于512或长度超过64）
2.quicklist数据结构：
- 最多64层，容纳2的64次方个元素
- 插入元素采用随机算法，理论上第一层概率为50%，第二层25%，以此类推，redis中晋升25%，因此跳跃列表会比较扁平
- source值一样的时候会比较value的值
- rank的实现是因为在节点的指针中存放了一跳经过的跨度
六、位图
1.基本结构：位数组
2.使用场景：用户的一年签到记录
3.基本操作：
- getbit、setbit、bitcount（指定位置范围）、bitpos（指定范围内）
- bitfield多个位操作set、get、incrby（默认配置会出现折返。也可以设置失败或者饱和截断）
七、HyperLogLog
1.基本结构：稀疏矩阵、HyperLogLog（2的14次方个桶用于调和平均，所以占12KB）
2.使用场景：提供不精确的去重计数方案，标准误差为0.81%，可以统计每天访问系统的UV数据
3.基本操作：pfadd、pfcount、pfmerge（多个pf计数累加）
八、布隆过滤器
1.基本结构：位数组、无偏hash函数
2.使用场景：推荐算法中的是否已经看过该文档、邮件过滤、爬虫记录已经爬过的URL，会有一定误判，但是不存在一定不存在，存在不一定一定存在。
3.基本使用：bf.add、bf.exists 、bf.mexists
4.参数调优：
- 使用bf.reserve设置key、error_rate、inital_size
- error_rate错误率，错误率越低空间越大
- inital_size预计元素个数，超了误判率会变高
九、地理位置GeoHash（了解）
1.算法原理：GeoHash将二维的经纬度数据映射到一维的整数（反向从证书还原有损），所有的坐标都存储在zset中，score是坐标52位整数，所以可以查看附件的元素（实际会复杂一些）
2.基本使用：geoadd、geodist（距离）、geopos（经纬度）、geohash（位置编码）、georadiusbymemeber(位置附近)、georadius(经纬附近)
3.注意事项：
- 集群数据量不建议超过1MB，这样迁移可能会卡顿
- 建议使用单机，Geo数据按照国家、省等进行拆分
十、listpack（了解）
1.产生背景：为了取代ziplist，不会有级联更新的问题，每个节点单独存在
2.数据结构：
| total_bytes | size | entry | ... | entry | end |
|---|---|---|---|---|---|
| 总字节数 | 元素个数 | 元素1 | ... | 元素n | 列表结束符 |
- entry的结构:struct entry{int<var> encoding;optional byte[] content;int<var> length;},length为当前元素的长度，不再是前一个元素长度，由于在entry的末端，所以与ziplist相比可以直接计算最后一个元素的位置，encodeing为编码类型，可以是1~5个字节中的任一长度
- 现在暂时应用于Stream中，并没有完全的替换ziplist的结构
十一、基数树 rax（了解）
1.数据结构：与zset不同的是zset基于score进行排序，rax基于key进行排序（字典序），rax是基数树radix tree的特殊结构，与基数树不同的是节点可以进行压缩存多个字符
2.使用场景：使用在Stream机构中用于存储消息队列
