Redis——相关数据结构
2017-07-19 本文已影响11人
远o_O
strings：字符串
- SDS（simple dynamic string）：自己构建的一种简单动态字符串的抽象类型，并且是Redis的默认字符串表示。
struct sdshdr{
int len;//保存的字符串长度
int free;//未使用的字节数量
cahr buf[];//字节数组
}
- 常数复杂度获取字符串长度
- 杜绝缓存区溢出
- 减少修改字符串时带来的内存重分配次数
- 二进制安全
- 兼容部分C字符串函数
- C字符串：作为字符串字面量，用在一些无须对字符串值进行修改的地方，例如打印日志。
LinkedList：链表
- 链表在Redis中的应用非常广泛，列表键list的底层实现之一就是链表。
- 特性：
- 双端
- 无环
- 带表头指针和表尾指针
- 带链表长度计数器
- 多态：可以保存不同类型的值
map：字典、映射
-
场景：
-
Redis的数据库就是使用字典来作为底层实现的，对数据库的增删该查操作也构建在对字典的操作之上的。
-
字典还是哈希键的底层实现之一， 键值对较多or元素都是比较长的字符串时会选用。
-
特性：
-
Redis中的字典使用hash表作为底层实现，每个字典带有两个哈希表，一个平时使用，一个仅在进行rehash时使用。
-
使用MurmurHash算法计算key的哈希值
-
使用链地址法解决hash冲突——单向链表
-
进行扩展和收缩时，rehash是渐进式完成的。
