redis之所以快,除了他是基于内存存储的,还有优秀的IO框架外更离不了其底层高性能数据结构的设计。现在我们来细细品一下redis的高新能数据结构是如何设计的。
redis有五种数据结构,分别是String,list(列表),Set(集合),Hash(哈希),Zset(有序结合)。这五种数据结构代表的是他的Value值的数据结构。今天我们来看redis的String类型。动态字符串SDS。
由于C语言函数哭的字符串是以NULL为结束符,而获取BNULL结尾字符串的长度是通过strlen把标准库函数,这个函数的复杂度为O(n)所以这是redis无法忍受的,所以redis就自己实现了SDS,可变的动态字符串。
struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位,不理睬它
byte[] content; // 数组内容
}
也就是我们上文说的为了扩容的时候的性能问题,在扩容的时候当没有预留空间的话,每次都要进行copy的工作,创建一个新的content数组然后copy数据,原来的数据被回收。这个过程是很耗费性能的。所以加了预留空间的话但添加不大的数据量的时候可以减少扩容次数。(其中hashMap的数组扩容加负载因子为0.75,也是类似的道理(遵循0.75的计算像是根据泊松分布))
我们可以注意到他的长度都是泛型来表示的那么为什么不使用int 或者 long 等类型呢。Redis 为了对内存做极致的优化,不同长度的字符串使用不同的结构体来表示。那这么一个判断选择类型的的过程岂不是也是浪费性能(时间换空间的概吧)。
struct RedisObject {
int4 type; // 4bits
int4 encoding; // 4bits
int24 lru; // 24bits
int32 refcount; // 4bytes
void *ptr; // 8bytes,64-bit system
} robj;