Redis中的数据结构总结

Redis作为时下热门的中间件，在校招面试以及工作中都有广泛的引用，最近自己看了下《redis设计与实现》，再次做一总结.

第一部分（总结redis中的数据结构）

1.简单动态字符串SDS

Redis是以C语言作为底层实现的，并没有采取C语言以char[]且以‘\0’作为标志符的字符串形式，而是自己重新封装了自己的实现方式SDS，一个可以被修改的字符串值在底层就是用SDS来存储的。比如最常见的命令：

set msg “hello，world” 由于其中的key和value都是字符串形式，所以都已SDS存储，那么为什么会要重新封装一个SDS呢。

首先我们看一下SDS的结构：

Redis中的数据结构总结

如图保存了一个Redis的字符串，SDS中的free字段表示未分配的空间，len字段表示分配了5字节的空间（‘\0’不计算在内）

然后我们来回答为什么要重新封装一个SDS，他比C原始字符串有什么优点吗？

i>.有自带统计字符串的长度，C语言的字符串都是以字符数组的形式存在的，原始的字节数组要求长度，只能遍历数组，时间复杂度o(n),SDS的len属性就直接求出来了，时间复杂度o(1).

ii>.杜绝缓冲区溢出，C语言中的strcat函数，是用来连接连个字符串的，假如String str=“123”，此时str1=“4”想要连接到str中，但是由于疏忽并没有给str分配足够的空间，则会出现溢出；而SDS要对字符串做修改时，会首先判断空间是否充足，如不充足，则首先扩展SDS的长度，然后在修改.

iii>.减少修改字符串带来的内存重分配的次数，由于字符串的扩展和收缩都会带来内存的重分配，而内存重分配有设计一些复杂算法比较耗费时间，但是对于redis这种修改频繁，又对速度有很高要求的应用场景，所以不得不采用空间预分配和惰性空间释放来解决.

(1).空间预分配：

a.SDS的len的长度小于1MB,则给free也分配和len长度相同的空间

b.SDS的len的长度大于1MB,则给free也分配1MB的空间

这样在扩展的时候，可以根据free的长度，来减少内存重分配的次数

(2).惰性空间释放：

在对字符串进行收缩操作的时候，并不是立即释放该空间，而是将多余的空间长度保存在free里，方便下次使用，

同时可以使用特定的api来清空空间

同时Redis作为数据库，也会存储一个非文本数据，所以SDS的api都会以二进制的方式来处理存放在buf数组的数据，同时也兼容了部分C语言的函数库。