Redis底层数据结构

数据类型相关命令

-- OBJECT命令查看数据的底层类型
127.0.0.1:6379> OBJECT help
 1) OBJECT <subcommand> [<arg> [value] [opt] ...]. Subcommands are:
 2) ENCODING <key>
 3)     Return the kind of internal representation used in order to store the value
 4)     associated with a <key>.
 5) FREQ <key>
 6)     Return the access frequency index of the <key>. The returned integer is
 7)     proportional to the logarithm of the recent access frequency of the key.
 8) IDLETIME <key>
 9)     Return the idle time of the <key>, that is the approximated number of
10)     seconds elapsed since the last access to the key.
11) REFCOUNT <key>
12)     Return the number of references of the value associated with the specified
13)     <key>.
14) HELP
15)     Print this help.

-- 直接调试某个key的结构信息
127.0.0.1:6379> DEBUG object k1
Value at:0x7f0e36264c80 refcount:1 encoding:embstr serializedlength:3
lru:7607589 lru_seconds_idle:23

redisObject

Redis是个<k,v>型的数据库，其中key通常是string类型字符串，而value在底层就是统一的redisObject对象。1. Redis底层数据结构

2.Redis面向应用层的结构：

数据类型对应关系

Redis中上层数据类型和底层真正存储数据的数据结构，对应关系：

1. redis7最大的区别是使用listpack替换了ziplist
2. 中上层的数据类型，一个类型会对应到底层不同的数据结构，随着存储的内容大小、长度变化而变化。 

数据结构详解

1. String

根据不同的键值，选择不同的编码方式（不同的底层数据结构）， int | embstr | raw

1、value可以转换成数值，使用int类型。

• ptr指针位置直接存储数值
• if 数字<1000, 直接使用预先创建的对象（预先创建的RedisObject对象），节省创建新对象的内存空间

2、value是字符串，且长度<44字节， 使用embstr类型

• embstr将对象自己和sds保存在一起
• 分配一块连续的内存空间保存对应的SDS, 连续的内存空间，可以提高读取速率

（SDS：simple Dynamic String 简单动态字符串）

3、raw类型：兜底策略

• 单独创建一个SDS， 然后将指针指向它

2. HASH

-- hash底层数据结构是根据hash元素长度和大小判断的， 直接修改这两个值的配置
-- hash-max-listpack-entries：限制键值对个数，默认512
-- hash-max-listpack-value:限制value里值的大小，默认64字节
127.0.0.1:6379> config set hash-max-listpack-entries 3
OK
127.0.0.1:6379> config set hash-max-listpack-value 8
OK

对应底层两种存储结构：hashtable、listpack

1. hash底层更多的是使用listpack来存储value。
2. 如果value里的数据比较少，就用listpack；如果数据比较多，就用hashtable。大部分情况都是listpack。 依据配置决定。
3. 对于同一个hash数据，listpack结构可以升级为hashtable结构，但是hashtable结构不会降级成为listpack。

Redis6中使用的底层数据结构是ziplist, Redis7升级成了listpack,  这两种结构的区别：

ziplist

        一种内存紧凑型的数据结构（指针都没存），占用一块连续的内存空间，不仅可以利用CPU缓存，而且会针对不同长度的数据，进行响应的编码。

这些entry就可以认为是保存hash类型的value当中的一个键值对。

每个entry可以分为3个 部分：

• previous_entry_length:记录前一个节点的长度，占1个或5个字节。
  • 如果前一个节点的长度 < 254字节，则采用一个字节来保存长度值。
  • 如果前一个节点的长度 >= 254字节，则采用5个字节来保存这个长度值。第一个字节是0xfe，后面四个字节才是真实长度数据。
• encoding：编码属性，记录content的数据类型。表明content是字符串还是整数，以及content的长度。
• contents：负责保存节点的数据，可以是字符串或整数。

总结说明：对一个ziplist，要找第一个元素和最后一个元素，比较容易，可以通过头部的三个字段直接找到。但是，如果想要找到中间某一些元素(比如Redis的list数据类型的LRANGE指令)，那么就只能依次遍历(从前往后单向遍历)。所以ziplist不太适合存储太多的元素。

listpack

核心解决ziplist的连锁更新问题。

连锁更新：ziplist结构中讲到，entry中记录了前一个节点的长度， 当出现头部新增加的节点（new节点）长度和下一个节点（e1， 原previous_entry_length占1个字节）记录的不一致时，就要整体进行更新。

listpack整体结构：

        核心是entry原本记录前一个entry的长度，现在改为记录自己的长度。这样，就不会再因为前一个entry变化而影响自己的长度。

3. List

-- 对应redis.conf中的配置
-- 每个list中包含的节点大小或个数。正数表示个数，负数-1到-5表示大小。
127.0.0.1:6379> config set list-max-listpack-size 2
OK

Redis是根据value中数据的大小判断底层数据结构的。数据比较“小”的list类型，底层用listpack保存。数据量比较"大"的list类型，底层用quicklist保存。

quiklist

Redis有了listpack存储结构，为什么还要quiklist的呢？ listpack类似数组结构，适合元素查询，但是增、删操作性能相对较低.

quicklist大体上可以认为是一个链表结构。里面的每个节点是一个quicklistNode。结合了链表和数组的优点。

（图说明：*entry指向listpack节点， 一个quiklistNode中有一个entry指针）

说明：quicklist的整体结构其实在Redis很早的版本中就已经成型了。区别在于quicklistNode中间保存的数据结构。 在Redis6以前是ziplist，到Redis7中改为了listpack。

4. SET

# -- 如果set的数据都是不超过64位的数字(一个long数字).就使用intset存储
set-max-intset-entries 512

# -- 如果set的数据不是数字，并且数据的大小没有超过下面设定的阈值，就用listpack存储
# -- 如果数据大小超过了其中一个阈值，就改为使用hashtable存储。
set-max-listpack-entries 128
set-max-listpack-value 64

Redis底层综合使用intset+listpack+hashtable存储set数据。set数据的子元素也是<k,v>式的entry。其中，key就是元素的值，value是null。

intset

intset数据结构定义：

5. ZSET

# Similarly to hashes and lists, sorted sets are also specially encoded
in
# order to save a lot of space. This encoding is only used when the
length and
# elements of a sorted set are below the following limits:
zset-max-listpack-entries 128
zset-max-listpack-value 64

1. Redis底层综合使用listpack + skiplist两种结构来保存zset类型的数据。
2. 当zset数据的value数据量比较小时，使用listpack结构保存。value数据量比较大时，使用skiplist结构保存。

        zset的特点：按照score进行排序； 检索。为了提交检索速度和移动元素做排序的要求，skiplist结构是一种链表+多级索引的结构。

skiplist结构：

多级索引提高了检索速度，但是维护索引成本也相对较高了，适合读多写少的场景。

相关数据结构

SDS

Redis根据字符串长度不同，封装了多种不同的SDS结构。通常保存字符串，用一个buf[]就够了。但是Redis在这个数组的基础上，封装成了SDS结构。

通过添加的这些参数，可以更方便解析字符串。例如，如果用数组方式保存字符串，那么读取完整字符串就只能遍历数组里的各个字节数据，时间复杂度O(N)。但是SDS中预先记录了len后，就可以直接读取一定长度的字节，时间复杂度O(1)，效率更高。

另外，C语言中通常用字节数组保存字符串，那么还需要定义一个特殊的结束符\0表示这一个字符串结束。但是在Redis中，如果value中就包含\0这样的字符串，就会产生歧义。但是有SDS后，直接读取完整字节，也就不用管这些歧义了。