《Redis设计与实现》1.数据结构域对象

快来打我* 2023-02-11 03:24 124阅读 0赞

**一、SDS**：simple dynamic string

*  int len：已使用的buf长度
 *  int free：未使用的长度
 *  char buf\[\]：存储字符串

**二、链表**：双向链表，包含head、tail指针，head的prev为null，tail节点的next为null

**三、字典**：类似于java hashmap，rehash过程是渐进式的，内部维护一个是否正在rehash的标识，维护一个rehash

**四、跳跃表**：

*  header头结点
 *  tail尾结点
 *  level跳跃表最大节点层数
 *  length跳跃表长度

每个节点随机层高，并保存score分值，backward后退指针，obj存储对象。

*  score分值，跳跃表按照score排序。如下图从2—>5—>6
 *  backward后退指针，第二个节点指向第一个节点，第一个几点指向NULL
 *  obj为实际存储的内容
 *  层，每个层包含前进指针与跨度
 *  前进指针指向右方的节点
 *  跨度是跳跃几个节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhb3hpbGFveGlf_size_16_color_FFFFFF_t_70][]

跳跃表查找：

如上如，要找到o2：

1.  找到头结点，第一个前进指针不为空的层L4（可直接从跳跃表信息level中获取）
2.  比对L4指针节点与o2的大小，o3>o2，则降层到L3
3.  判断头结点的L3前进指针节点与o2的大小，o2>o1，跳跃到前进指针节点
4.  判断o1的L3前进指针节点，o2 = o2，找到节点

插入：例如插入ox，score为3

1.  用查找发找到ox的位置，也就是在o1之后
2.  随机为ox增加层高，从L1开始，将其与o1相连，待随机层高超过o1，则向前遍历节点，找到存在同层的节点直到header（xNode），然后新节点的同层指xNode该层的前进指针，将xNode的前进指针指向该新节点。

**五、整数集合**

*  encoding保存整数的位数，16、32、64
 *  length元素个数
 *  contents数组内容

升级：当在16位的整数数组中，insert一个32位的数字，则需要升级

1.  分配空间，先分配足够的空间，然后将新进来的数字放到对的位置上
2.  然后将原本的数字倒着放置到对应的位置上

如下往16位的数组中插入60000

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhb3hpbGFveGlf_size_16_color_FFFFFF_t_70 1][]

**六、压缩列表**

**七、对象**

属性：type、encoding、ptr、refcount、lru

type：REDIS\_STRING字符串对象、REDIS\_LIST列表对象、REDIS\_HASH哈希对象、REDIS\_SET集合对象、REDIS\_ZSET有序集合对象

**1.字符串对象**

**编码格式：int、raw、embstr**

大于32字节，使用SDS保存，编码设置为raw；小于32字节，也是用SDS保存，编码格式embstr

*  raw需要分配2次内存，分别是redisObject与sds。
 *  embstr分配一次内存，直接包含redisObject与SDS，是连续的。

embstr比raw的优势：

*  embstr需要分配一次内存，而raw需要两次
 *  embstr只需要释放一次内存，而raw需要两次
 *  embstr的redisObject与SDS存储在连续的空间里，可以更好利用缓存

**2.列表对象**

**编码格式：ziplist、linkedlist（双端链表）**

ziplist条件，必须同时满足：

1.  列表字符串长度都小于64字节（list-max-ziplist-value）
2.  列表元素数量小于512（list-max-ziplist-entries）

**3.哈希对象**

**编码格式：ziplist、hashtable**

ziplist条件同上。

**4.集合对象**

**编码格式：intset、hashtable**

intset条件，都为整数，且不超过512

**5.有序集合对象**

**编码格式：ziplist、skiplist**

实际是字典dict与跳跃表zsl都保存了一份，保留了查找的O(1)，也保留了范围O(logN)。

DEL、EXPIRE、RENAME、TYPE、OBJECT：可适用于任何key；

SET、GET、APPEND、STRLEN：只能用于字符串键；

HDEL、HSET、HGET、HLEN：只能用于哈希键；

RPUSH、LPOP、LINSERT、LLEN：只能用于列表键；

SADD、SPOP、SINSERT、SCARD：只能用于集合键；

ZADD、ZCARD、ZRANK、ZSCORE：只能用于有序集合键；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhb3hpbGFveGlf_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521162527811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhb3hpbGFveGlf,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhb3hpbGFveGlf_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521162527825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhb3hpbGFveGlf,size_16,color_FFFFFF,t_70