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

一、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为实际存储的内容
层，每个层包含前进指针与跨度
前进指针指向右方的节点
跨度是跳跃几个节点

跳跃表查找：

如上如，要找到o2：

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

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

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

五、整数集合

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

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

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

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

六、压缩列表

七、对象

属性：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条件，必须同时满足：

列表字符串长度都小于64字节（list-max-ziplist-value）
列表元素数量小于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：只能用于有序集合键；

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

相关推荐