3.30--Redis之常用数据结构--SDS(总结篇)------加油呀

时间:2021-02-15 01:18:28

数据结构:
3.30--Redis之常用数据结构--SDS(总结篇)------加油呀

结构中的每个成员变量分别介绍下:
1.len,记录了字符串长度。这样获取字符串长度的时候,只需要返回这个成员变量值就行,时间复杂度只需要 O(1)。
2.alloc,分配给字符数组的空间长度。这样在修改字符串的时候,可以通过 alloc - len 计算出剩余的空间大小,可以用来判断空间是否满足修改需求,如果不满足的话,就会自动将 SDS 的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用 SDS 既不需要手动修改 SDS 的空间大小,也不会出现缓冲区溢出的问题。
3.flags,用来表示不同类型的 SDS。一共设计了 5 种类型,分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64
4.buf[],字符数组,用来保存实际数据。不仅可以保存字符串,也可以保存二进制数据。

1.O(1)复杂度获取字符串长度

  1. C 语言的字符串长度获取 strlen 函数,需要通过遍历的方式来统计字符串长度,时间复杂度是 O(N)。
    2.Redis 的 SDS 结构因为加入了 len 成员变量,那么获取字符串长度的时候,直接返回这个成员变量的值就行,所以复杂度只有 O(1)。

2.二进制安全

SDS 不需要用 “\0” 字符来标识字符串结尾了,而是有个专门的 len 成员变量来记录长度,所以可存储包含 “\0” 的数据
使得 Redis 不仅可以保存文本数据,也可以保存任意格式的二进制数据。

3.不会发生缓冲区溢出

  1. Redis 的 SDS 结构里引入了 alloc 和 len 成员变量,这样 SDS API 通过 alloc - len 计算,可以算出剩余可用的空间大小,这样在对字符串做修改操作的时候,就可以由程序内部判断缓冲区大小是否足够用。
    2.当判断出缓冲区大小不够用时,Redis 会自动将扩大 SDS 的空间大小

在扩容 SDS 空间之前,SDS API 会优先检查未使用空间是否足够,如果不够的话,API 不仅会为 SDS 分配修改所必须要的空间,还会给 SDS 分配额外的「未使用空间」。

这样的好处是:下次在操作 SDS 时,如果 SDS 空间够的话,API 就会直接使用「未使用空间」,而无须执行内存分配,有效的减少内存分配次数

4.节省内存空间

SDS 结构中有个 flags 成员变量,表示的是 SDS 类型。

这 5 种类型的主要区别就在于,它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

SDS 设计不同类型的结构体,是为了能灵活保存不同大小的字符串,从而有效节省内存空间

Redis 在编程上还使用了专门的编译优化来节省内存空间,即在 struct 声明了 attribute ((packed))

它的作用是:告诉编译器取消结构体在编译过程中的优化对齐,按照实际占用字节数进行对齐。
因为默认情况下,编译器是使用「字节对齐」的方式分配内存

采用 attribute ((packed)) 属性定义结构体,这样一来,结构体实际占用多少内存空间,编译器就分配多少空间