reids基础数据结构

一.整体

1.RedisDb

redis内部的所有键值对是两个hash结构，维护了键值对和过期时间

• dict *dict
• dict *expire

2.对象头

• int type
• int encoding
• int lru
• int refcount
• void *ptr

二.string

SDS动态字符串，可以修改。结构体中维护了数组的容量和长度，在占用字节数较小时采用embstr（使用malloc分配一次内存，对象头和数据连续存储）的形式存储，在长度较大时采用raw形式（malloc分配两次内存，对象头和数据分开存储）存储。

扩容策略：长度小于1M时加倍扩容，长度大于1M时每次扩容增加1M

常用指令：

• set
• get
• exists
• del
• expire
• incr、incrby

三.list

快速列表：连续存储元素的ziplist通过指针连接起来组成快速列表。

基本操作：

• rpush
• rpop
• lpush
• lpop
• lindex() ,获取第几个元素
• ltrim()，保留范围内的数据

1.ziplist

一块连续的内存空间，元素之间紧凑存储，没有冗余间隙。元素体维护着前一个元素的长度（长度小于254时占用一个字节，超过时占用5个字节）、编码、数据，可以存储不同类型的数据，通过编码优化存储占用。

注意点：

• 增加元素，每增加一个元素就要扩展内存，并将之前的内容进行拷贝。所以ziplist会限定大小，超出时就会新增ziplist
• 级联更新，前一个元素的长度发生增长并切好超过了254，并且导致下一个元素的长度增加恰好也超过254,如此向下传递到的更新效应

2.quicklist

通过将ziplist通过前后指针连接起来形成的双向链表。

注意点：

• 新增ziplist，单个ziplist大小超过8k字节时，就会新起一个ziplist
• 压缩深度：0:不压缩，1:首尾不压缩

四.hash

类似与hashmap，内部是数组加链表的结构，不过内部结构维护了两个hash结构。因为redis为了高性能在rehash时采用了渐进式的rehash方式（查询时同时查询两个hash结构）。

基本操作：

• set
• get
• hgetall
• hlen
• hmset
• hincryby

注意点：

• 元素数大于数组数时就会扩容
• 元素数低于数组数的10%就会扩容

五.set

相当于hashset，无序键值对，元素的value为NULL。

基本操作：

• sadd
• smember
• sismember，是否存在
• scard，获取元素个数
• spop，弹出一个

六.zset

内部结构是hash字典和跳跃列表，字典存储value和score的对应关系，跳跃列表提供按照score来排序的功能。

基本操作：

• zadd
• zrange
• zrevrange
• zcard
• zscore
• zrank
• zrankbyscore
• zrem

跳跃列表基本操作实现：

1.查找

从header的最高层开始查找，直到找到本层最后一个比目标score小的元素，然后进入到下一层，重复上一步骤，直到找到目标元素或遍历到最底层。

2.插入

• 查找待插入位置，记录搜索路径
• 新建节点，分配随机层数
• 将搜索路径上的节点和新节点通过前后指针连接起来
• 如果节点的高度大于最高高度，更新最高高度

3.删除

• 查找待删除元素，记录搜索路径
• 重排搜索路径上的前后指针
• 最高高度变化的话更新最高高度

4.更新

先删除后增加

5.元素排名

根据value获取score后，将搜索路径上的span跨度值相加就是元素排名。