一 字符串
底层使用SDS的数据结构来保存字符串，而不是用C语言中的字符串。SDS即simple dynamic string，结构如下：
sdsstr数据结构及示例
-
len: 已经使用的字段的长度 -
free: 未使用的字段的长度 -
buf: 字节数组
而C语言中的字符串，就是一个单纯的以\0结尾的数组，
与C语言中的字符串相比，SDS有以下几点优势：
-
计算长度的时间复杂度为o(1)，而不是C字符串的o(n)
C字符串的格式就是一个以\0结束的数组，如果要获取长度需要遍历，而sds使用len保存了这个数据。 -
不用考虑内存溢出等问题，内部已经封装好了
C字符串扩展字符串时要自己分配内存，否则内存会溢出，而sds已经对长度的检测做了封装了。 -
扩展字符串或者缩减字符串不需要重新分配内存
C字符串中扩展和缩减字符串都需要重新分配内存，但是sds不需要，因为它有未使用的字节长度，所以其实是可以伸缩的。 -
二进制安全
C字符串以\0结尾，因此不能保存内部可能出现\0的二进制数据。虽然sds也是\0结尾的，但是实际读取时会依赖于长度len来读取，不需要担心\0的问题。
C字符串与SDS的区别
二 链表
redis中的链表它就是一个普通的双向链表，没有什么花里胡哨的操作，列表的结构体叫list，列表节点的结构体叫listNode：
链表
dup, free, match 三个操作链表相关的函数
三 hash表(字典)
3.1 结构
redis中的数据库（也就是键与值的对应关系）和散列表都是基于字典来实现的
底层结构与Java中的HashMap类似，桶链结构：
redis中的字典
dictht即字典对应的结构体名称，而dictEntry是字典中中链表的结构体名称
-
table: dictEntry数组，实际保存数据 -
size: dictEntry的长度 -
sizemask: 总是为size - 1，用于把节点映射到桶的下标 -
used: 实际保存的数据量
hash算法：murmurhash
3.2 扩容
触发条件，以下两个任意满足一个：
- 负载因子 >= 1 且 没有正在执行BGSAVE或者BGREWRITEAOP命令
- 负载因子 >= 5
扩容方式：每次都取比当前数据量used*2大的最小的2的整数次幂
3.3渐渐式 rehash
扩容时不会立即把数据rehash到新的hash表中去，而是在每次操作对应数据时才rehash那一项
四 跳跃表
redis中的跳跃表
redis中的跳跃表
感觉跟一个普通的跳跃表没什么区别
五 整数集合
当redis中集合只包含整数数据时，会使用整数集合来保存
redis中的整数集合
集合的元素类型会依据元素最大绝对值来使用long，int，short，或者byte
六 压缩列表ziplist
ziplist分为 头-体 两部分，头部数据包含：
-
zlbytes: 整个结构体占用的空间 -
zltail: 到最后一个元素的偏移量，方便从后面查找 -
zllen: 元素的数量
中间元素的数据结构，有四个字段：
- 前一个元素的大小：方便倒顺查找
- 当前元素的编码类型
- 当前元素的大小：通过这个值可以定位到下一个元素的位置
- 当前元素的内容
此外ziplist用一个单字节的值zlend = 255来标记结尾
ziplist
七 redis中各种数据类型对应的数据结构
7.1 对象类型与编码
redis中使用redisObject保存所有对象的数据：
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;
-
type: 对象数据类型，只能取redis支持的五种数据类型 -
encoding: 对象的数据结构，也就是上面说的那些数据结构 -
refcount: redis使用引用记数法做内存回收 -
ptr: 数据地址
例如执行SET msg "hello world"命令后，redis底层将多了两个redisObject对象，一个对象保存了键的数据，另一个保存了值的数据，而type字段标记了这两个对象保存的数据类型。
7.2 字符串类型对应的数据结构
redis中字符串类型可以使用以下三种数据结构保存：
-
int: 数字类型。如果字符串值实际上是一个数字，且能用long表示，则使用数字类型。 -
embstr: 也就是上面说的sds字符串。如果字符串的值的长度 <= 32，则使用这种类型。 -
raw: 也是上面说的sds字符串。如果字符串值的长度 > 32，则使用这种类型。
embstr与raw的区别是：embstr会为redisoObject和sds字符串一次性分配内存空间，而raw则会分两次分别为它们分配内存空间。也就是说embstr的redisObject和sds两个对象在物理上是连续的，而raw不是。
7.3 列表类型对应的数据结构
-
ziplist: 当列表中元素的个数 <= 512，并且每个元素的长度 <= 64时，使用ziplist -
linkedlist: 当元素个数 > 512 或者至少有一个长度 > 64 的元素时，使用linkedlist
64和512这两个值可以使用list-max-ziplist-value和list-max-ziplist-entries来设置
7.4 散列表类型的数据结构
-
ziplist: 所有键值对的键和值的长度都 <= 64，并且键值对个数 <= 512 -
hashtable: 也就是字典，不满足上面的条件时使用字典
使用ziplist时，底层是按照 键 - 值 - 键 - 值 - 键 - 值这样交替摆放来实现的
这里的64和512这两个值可以使用hash-max-ziplist-value和hash-max-ziplist-entries来设置
7.5 集合类型的数据结构
-
intset: 集合中的元素都是整数，且个数 <= 512 -
hashtable: 不满足上述条件时使用hashtable
512这个上限可使用set-max-intset-entries 来修改
7.6 有序集合的数据结构
-
ziplist: 集合中元素个数 <= 128 且每个元素的长度 <= 64 -
skiplist: 不满足上述条件后使用
使用ziplist时的结构：值-分数-值-分数-值-分数
如果使用的是skiplist，还会再使用字典保存元素与分数的对应关系
网友评论