热搜：编程 Python Microsoft 编程语言 C++

浅谈一下Redis的数据结构

发布时间：2024-03-02 18:16:40 来源：网络

.

一、简单动态字符串SDS struct sdshdr {int len;int free;char[] buf; } 简单字符串结构被用于存储redis的key

一、简单动态字符串SDS

struct sdshdr {
  int len;
  int free;
  char[] buf;
}

简单字符串结构被用于存储redis的key对象和String类型的value对象

其中的free和len字段可以轻松的使得在该字符串被修改时判断是否需要扩容。

为啥呢？因为redis的协议发送一个SET请求时格式开头会带上需要插入的value的长度，这样根据free以及len可以判断此时redis分配的数组大小是多少，需不需要扩容。对比于C语言的O(n)复杂度计算数组长度更快。

扩容策略：如果字符串大小<1MB, 每次扩容为2n+1大小；如果大于1MB,每次扩容1MB。

二、链表

链表结构用于存储list类型的键值（类似index），还有发布订阅等功能也用了链表结构。

链表节点：ListNode

链表：list

代码块

typedef struct list{
	ListNode * tail;
	ListNode * head;
	unsigned long len;
	//节点值复制方法
	 void *(*dup) (void * ptr);
	//节点值释放方法
	 void *(*free) (void * ptr);
	//节点值对比方法
	int (*match)(void * ptr, void * key);
}

list+ListNode的链表结构

三、字典

哈希表的结构：

字典的结构：

typedef struct dict{
	dictType *type;
  void *privdata;
  dictht *ht[2];
  int rehashIndx;	
}

ht[2]: 需要两个hashTable的原因是在进行rehash的操作时，需要使用另一个hashTable。

rehashIndx:在不进行rehash时值为-1，在渐进rehash过程中，这个值代表了rehash进行到的dictEntry的索引。

在hash时将会根据key取哈希&sizeMark来获得dictEnrty数组的下标索引，当数组中非空则将dictEntry元素插入到链表第一个位置。

随着链表的长度越来越长，对于字典的查询速度也会越慢，这时候就需要rehash。

rehash将会用到另一个空哈希表ht[1]，将里面的table数组大小增加，再将原来的键值重新hash放入新的DictEntry中。rehash完毕后，把ht[1]变为ht[0], 再重新开辟一个空间作为ht[1]。

四、跳跃表

跳跃表用作有序集合键的底层实现以及在集群节点用作内部数据结构

后退指针：后退指针用于从表尾遍历节点。

object：保存的是一个指向对象的指针。

score分值：关乎节点的排序，如果分值相同则成员对象较大的排在后面。

zskiplist：虽然通过多个节点就可以组成跳跃表，但是使用zskiplist中的length、level字段就可以在O(1)复杂度返回跳跃表的长度以及层级。

五、整数集合

encoding:可支持存储INSET_ENC_INT16、INSET_ENC_INT32、INSET_ENC_INT64（int16_t、int32_t、int64_t）三种位数的整数。

content: 在这个数组中按照大小顺序存放整数，并且元素不会出现重复项。

集合升级：当集合需要插入一个比原有类型更大的整数时，需要先给数组的每个元素重新分配空间，首先先扩大数组空间到相应的大小，再将原来位置上的整数从后往前重新进行类型转换放到相应的索引上。每次升级都需要对底层元素进行转型并移动，时间复杂度为O(N)。升级使得这个集合更为节省内存，并且可以使得使用者不必关注c语言底层创建数组时指定类型位数不足而导致的插入异常问题。

整数集合不支持降级。