Redis 数据结构

偏执的太偏执、 2022-04-04 03:12 197阅读 0赞

五大结构实现String，hash, list，set，sortedSet  
大：数量多或单个value长。小：数量少且单个value短  
redisObject（type，encoding，ptr指针，refcount（为0回收，可共享）lru(最后访问时间，用于超过maxmemory内存回收) ）如set msg hello 两个redisObject  
各类型编码：  
String（int，raw，embstr）  
int: 可用long表示的整数，ptr指针转为整数值  
raw：大于39字节字符串，使用sds  
embstr：小于等于39 优势：一次内存分配和释放（raw分别redisObject和sds分配，两次），连续内存（redisObject和sds放在一起），embstr只读，修改转为raw

list（小ziplist，大linkedlist）  
hash（小ziplist，大字典）ziplist（key，value紧靠，两个entry）  
set（intset存放少量整数，字典value全为null）  
sorted set（小ziplist，大skiplist）ziplist（key，score紧靠，两个entry，由小到大，表头score最小）  
skiplist（score由小到大）

Redis用C字符串作字面量，不修改

SDS（简单动态字符串），方便修改,free(2) ,len(5) char\[\] ,末尾\\0 不计数  
![在这里插sds入图片描述][sds]

优势：快速获取长度（无需遍历）  
不会缓冲区溢出（先检查，可能会动态扩展，预分配一定空间避免反复扩展，缩减后不立即释放空间，避免以后扩容需重分配）  
二进制安全（不以\\0判定结束，而以len判定，这样内容中也可存\\0，可存二进制数据）

链表：list（维护表头表尾，表长）listNode（next，prev，value指针（多态，随便你value是啥））

字典：用于实现数据库和hash，dict（含两个dictht ，一个使用，一个rehash才用）  
dictht（size，used，指向dictEntry数组指针）  
dictEntry（key指针（一般指向sds），value可为指针，可为int，next基于链地址解决冲突，晚进来的加在前面O(1)）  
rehash渐进式，rehash过程中也可crud（当然新增直接入新hashtable，其余在两个hashtable上进行）太大或太小（loadFactor=used/size）

skiplist：实现sortedset 查找平均 O(log N) 最坏 O(N)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvYmV4emY_size_16_color_FFFFFF_t_70]  
zskiplist（header，tail，level（除首节点最大层数），length（除首节点节点个数））  
typedef struct zskiplistNode \{  
obj 指针  
double score; // 分值  
struct zskiplistNode \*backward; // 后退指针  
struct zskiplistLevel \{  
struct zskiplistNode \*forward; // 前进指针  
unsigned long span; // 跨度  
\} level\[\];  
\}  
层数1到32之间随机值，分数由小到大排列，同分数则按字典序排序

intset：用于只含整数且数量较少的集合  
intset（encoding（16，32，64位），length，数组（从小到大））  
升级：比如16位只能放-32768到32767，突然放入61000，那么升级，数组每个位置升为4字节  
不支持降级

ziplist（压缩列表） 实现小list，小hash，节约内存  
![在这里插入图片描述][20181214171310666.png]

zlbytes 总字节数  
zltail 最后一个entry离ziplist首部的偏移  
zllen entry数目  
zlend 标记末端  
![在这里插入图片描述][2018121417174667.png]

前一entry长度：用于反向遍历，先zltail找最后entry，然后不断向前  
encoding：确定content类型（字节数组还是整数），长度（数组多长，16位还是32位…整数）  
新加或删除entry可能连锁更新，概率低。

[sds]: /images/20220404/55053c59066244e6a4f97a06d0a0f265.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvYmV4emY_size_16_color_FFFFFF_t_70]: /images/20220404/cde9e7177a14495db3e77cc16da91867.png
[20181214171310666.png]: /images/20220404/716b2553848446e9bf512062797f5872.png
[2018121417174667.png]: /images/20220404/ad29c82ed89543fb92b5c3753d06e2cb.png