沧州网站制作报价,长春市经济开发区人才网,邢台网站网页设计公司,郴州出现一例无症状感染者Redis系列之底层数据结构SDS
实验的环境
Redis 6.0VSCode 1.88.1
什么是SDS?
SDS#xff1a;Simple Dynamic String#xff0c;翻译为简单动态字符串。SDS是一种用于存储二进制数据的数据结构#xff0c;具有动态扩容的特点#xff0c;代码位于src/sds.h和src/sds.c
…Redis系列之底层数据结构SDS
实验的环境
Redis 6.0VSCode 1.88.1
什么是SDS?
SDSSimple Dynamic String翻译为简单动态字符串。SDS是一种用于存储二进制数据的数据结构具有动态扩容的特点代码位于src/sds.h和src/sds.c
SDS的总体数据结构大致如图在源码里sds包括几个部分len、alloc、flags、buf其中 sdshdr是头部buf是真实存储数据的地方在存储的数据后面会跟一个\0所以数据加上\0就是所谓的buf len保存了SDS字符串的长度buf[]保存数据的地方alloc分别以uint8, uint16, uint32, uint64表示整个SDSflags始终为一字节, 以低三位标示着头部的类型, 高5位未使用
查看源码sds.h可以看到SDS里面有几种不同的头部其中sdshdr5实际并未使用到所以实际上有四种不同的头部
/* Note: sdshdr5 is never used, we just access the flags byte directly.* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 3 lsb of type, and 5 msb of string length */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* used */uint8_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* used */uint16_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* used */uint32_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* used */uint64_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};为什么要使用SDS
Redis是用C语言写的为什么不直接就用C语言里的char来定义字符串
获取字符串长度
由于有len属性所以获取SDS字符串的长度只需要读取len属性所以时间复杂度为O(1)。如果直接使用C语言中的字符串来实现获取字符串的长度需要遍历计数时间复杂度为O(n)。
避免缓存区溢出
在C语言中如果使用strcat函数来进行两个字符串的拼接如果没有分配足够长度的内存空间就会造成缓存区溢出。而对于SDS数据类型在进行字符串修改的时候会根据记录的len属性检查内存空间是否满足需求如果不满足会进行相应空间的扩展所以不会出现缓存区溢出
减少字符串内存重新分配次数
在C语言中字符串是不会记录字符串的长度的所以一旦修改了字符串就需要重新分配内存因为如果没有重新分配字符串长度增大时会造成内存溢出区溢出长度减小时会造成内存泄漏。而对于SDS来说因为有长度熟悉len和alloc属性的存在SDS实现了空间预分配和惰性空间释放两种策略来减少重新分配内存
空间预分配SDS对空间进行扩展的时候扩展的内存比实际需要的多这样可以减少字符串增长操作所需的内存重新分配次数惰性空间释放SDS对字符串进行缩短操作时不会立即进行内存重新分配来回收缩短后多余的内存空间而是使用alloc将这些字节数量记录下来等待后续使用
二进制安全
在C语言中是以空字符串作为字符串结束的标识但是一些特殊的字符串可能就包括空字符串的所以容易丢失数据不能正确存取。而SDS是根据len属性以处理二进制的方式来处理buf里的数据所以保存数据更加安全
兼容部分C字符串函数
SDS可以重用C语言库string.h中的一部分函数
C字符串和SDS对比
C字符串SDS获取字符串长度时间复杂度为O(n)获取字符串的长度时间复杂度为O(1)不安全可能会造成缓冲区溢出安全不会造成缓冲区溢出修改字符串n次就需要进行n次内存分配修改字符串长度n次最多需要n次内存分配只能保存文本数据可以保存文本数据或者二进制数据可以使用所有string.h库中的函数可以使用一部分string.h库中的函数
