Redis数据结构(一)

SDS简单动态字符串

结构:

1:SDS是在C语言字符串的基础上,构造的一种简单的动态字符串(simple daynamic string)。SDS结构体包含三个变量,len用来记录长度,free用来记录未使用字节的数量,buf存储实际的字符串数组。
2:SDS不以‘\0’为结束符,而是以len的长度标识
这里写图片描述

优点

1:O(1)获取字符串长度。sdshdr结构体中,直接存储了字符串的长度。因此直接以sdshdr.len读取字符串长度就可以了,相对于C语言的遍历。
2:防止缓冲区溢出。因为sds自动记录了字符串的长度,当需要扩充某个字符串时,会先检测长度是否满足。不满足,会先扩充sdshdr.buf的长度。而C语言,strcat会直接拼接两个string,后面的string可能会占用已经占用的内存区域。
3:减少字符串改变带来的内存重分配次数。简单一点说,当扩充字符串时,sds会给它多分配一些额外的内存。当缩减字符串时,并没有立即将其归回,而是用sdshdr.free记录。
4:二进制安全。直白点,就是不以’\0’为结束符,而是记录其二进制数据,即’\0’对应的00000000。结束是以sdshdr.len来标识的
5:可以重用部分C语言的函数。但因为结束机制不一样,也只是部分而已。

用处

1:redis中常见的字符串值都是用sds实现的。例如,常用的键。

双向链表

结构

1:节点(struct ListNode),包含前节点和后置节点两个指针域。
链表(struct List),包含头,尾节点。以及相关的操作函数。
这里写图片描述

这里写图片描述

###优点
1:新增和删除元素非常方便。很大部分来自链表的优点
2:其中的value字段,可以用来存储其他的类型,非常方便扩展

用处

1:redis中List数据类型就是用这个实现的

字典

结构

1:首先说明下,字典也是由其他的数据结构构造的。它包括,哈希节点,哈希表,字典三个部分。哈希表连接哈希节点,字典包含两个哈希表。
2:哈希节点,包含三个域。键,值,下个节点的指针。其中下个节点是为解决哈希冲突的。
这里写图片描述
3:哈希表,包含四个域。dictht.table,是一个数组,对应的值就是哈希表节点。dictht.size,总大小。sizemask,用来计算索引值。used,记录已经使用多少。
这里写图片描述
4:字典,包含四个域。其中,ht就是指向上面的哈希表的。
这里写图片描述
5:完整的结构,未进行rehash,存在冲突。
这里写图片描述

优点

1:有效解决了哈希冲突,通过dictEntry的next指针,将具有同一索引的值链接起来。
2:很方便就行rehash。我们知道到哈希表大小不足时,就很容易造成哈希冲突。此时便需要扩容。dict.ht[2]其中一个就是用来扩容的,当dictht.size == used时,便将dict.ht[1]扩大到used*2,再将dict.ht[0]缓慢哈希到dict.ht[1]。完成后,将dict.ht[0]指向dict.ht[1],将dict.ht[1]置为空即可。

坚持原创技术分享,您的支持将鼓励我继续创作!