网站建设都需要哪些书,建设银行网站打不开,禅城网站建设联系电话,自己做国外网站买衣服1.绪论
我们知道redis是由c语言实现的#xff0c;c语言中是自带字符串的#xff0c;但是为什么redis还要再实现自己的动态字符串呢#xff0c;这种动态字符串的底层数据结构是怎样的呢?接下来我们带着这些问题来看一看redis中的动态字符串sds。
2.sds的组成
struct __at…1.绪论
我们知道redis是由c语言实现的c语言中是自带字符串的但是为什么redis还要再实现自己的动态字符串呢这种动态字符串的底层数据结构是怎样的呢?接下来我们带着这些问题来看一看redis中的动态字符串sds。
2.sds的组成
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 *///整个sds字符串的大小uint16_t alloc; /* excluding the header and null terminator *///表示是5种sds字符串中的哪一种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[];
};
可以看出redis中sds是一个动态数组它由长度sds占据内存大小sds的类型加一个数组组成。如果用图表示如下 可以看出redis的sds和java中的ArrayList是类似的。
3.sds的优点
为什么redis需要重新实现一个字符串呢主要有如下的几点考虑
3.1.常数时间复杂度获取字符串长度
普通字符串以\0结尾而sds存取了整个字符串占据多少个字符。所以普通字符串需要用o(n)的复杂度获取到字符串长度而sds以o(1)的复杂度获取到字符串长度
3.2.存储特殊符号\0
sds能够存储特殊符号\0当时c语言原生的字符串以\0结尾不能存储\0保证二进制安全
3.3.内存动态分配防止杜绝缓冲区溢出
c语言原生字符串内存一但分配大小便固定比如在调用append key命令的时候会实现字符串拼接的功能如果超出缓冲器大小会超出分配内存大小而报错 但是sds实现了动态扩展的功能在拼接前会检查内存是否够用如果不够用便会进行动态扩容而如果数组的剩余空间过多便会进行缩容。
3.3.1 动态扩容
当新的字符串占用空间超出分配内存空间时会进行动态分配并且会提前考虑预分配一部分空间防止内存的频繁分配问题。
3.3.2 动态缩容
当已使用内存小于分配内存的部分比例时会进行动态缩容并且采用惰性释放的策略不使用的数据并不会立即清除而是等待有新的字符串写入的时候进行覆盖。
3.4.节约内存
在高版本的redis中将存储字符数值分成了5类分别是sdshdr5 、sdshdr8 、sdshdr16 、sdshdr32 、sdshdr64 redis会根据存储的字符内容来判断采用哪个中字符串尽显存储数据。比如如果用户写入的字符串只包含abcd这种英文字母每个字符串用一个字节便能存储。sds便会考虑采用sdshdr8来进行存储.
4.总结
可以看出redis的sds其实就相当于java中的ArrayList都具有动态扩容缩容等功能。
5.参考
[1] 黄建宏 redis设计与实现
[2] https://juejin.cn/book/7144917657089736743/section/7144917738698326019
