redis数据结构，底层编码

2018-12-02 本文已影响0人 IT菜鸟学习

redis的数据结构
string，hash，list，set（集合），zset（有序集合）五种数据结构，但这个只是redis对外的数据结构。

image.png

每种数据结构都有多种不同的编码
string 类型的就包含raw、int、embstr三种不同的内部编码
，有些内部编码可以做为多种外部数据结构的内部实现。

127.0.0.1:6379> set str1 hello
OK
127.0.0.1:6379> object encoding str1 
"embstr"
127.0.0.1:6379> hset hash1 name kebi
(integer) 1
127.0.0.1:6379> object encoding hash1
"ziplist"

redis这样做的好处：

可以改进内部编码。当内部编码改变有更好编码的时候，无需改变外部的数据结构。
多种内部编码可以在不同的场景下发挥各自的优势。例如ziplist比较节省内存，但是在列表比较多的时候，性能会有所下降，这个时候Redis会根据配置将内部实现进行升级。

下面会分别介绍五种数据结构的内部编码方式

字符串的内部编码方式
字符串的内部编码方式有3中。
int：8个字节的长整型
embstr：小于等于39个的字符串。（测试小于等于44）
raw：大于39个字节的字符串。（测试大于44）
Redis会根据当前的类型和长度决定使用的内部的编码实现。
（1）整数类型示例如下：

127.0.0.1:6379> set str 1234567 
OK
127.0.0.1:6379> object encoding str
"int"

（2）短字符串示例如下：

127.0.0.1:6379> set str "hello world"
OK
127.0.0.1:6379> object encoding str
"embstr"

（3）长字符串示例如下：

127.0.0.1:6379> set str kkkkkkkkkkaaaaaaaaaabbbbbbbbbbcccccccccdeeeee
OK
127.0.0.1:6379> object encoding str
"raw"

列表的内部编码

（1） ziplist（压缩列表）

当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时所有值都小于list-maxziplist-value配置（默认为64字节），Redis会使用ziplist做为哈希的内部实现。Ziplist可以使用更加紧凑的结构来实现多个元素的连续存储，所以在节省内存方面更加优秀。

压缩列表的优点：

压缩列表ziplist结构本身就是一个连续的内存块，由表头、若干个entry节点和压缩列表尾部标识符zlend组成，通过一系列编码规则，提高内存的利用率，使用于存储整数和短字符串。

压缩列表的缺点：

每次插入或删除一个元素时，都需要进行频繁的调用realloc()函数进行内存的扩展或减小，然后进行数据”搬移”，甚至可能引发连锁更新，造成严重效率的损失。
（2） linkedlist（链表）
当列表类型无法满足ziplist要求时，redis会采用linkedlist做为列表的内部实现。
（3）quicklist（快速列表）
quicklist结构是在Redis 3.2版本中新加的数据结构，用在列表的底层实现
quicklist宏观上是一个双向链表，因此，它具有一个双向链表的有点，进行插入或删除操作时非常方便，虽然复杂度为O(n)，但是不需要内存的复制，提高了效率，而且访问两端元素复杂度为O(1)。
ziplist本身也是一个能维持数据项先后顺序的列表（按插入位置），而且是一个内存紧缩的列表（各个数据项在内存上前后相邻）。比如，一个包含3个节点的quicklist，如果每个节点的ziplist又包含4个数据项，那么对外表现上，这个list就总共包含12个数据项。

quicklist的结构为什么这样设计呢？总结起来，大概又是一个空间和时间的折中：

双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
ziplist由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。
于是，结合了双向链表和ziplist的优点，quicklist就应运而生了。
在quicklist表头结构中，有两个成员是fill和compress，其中” : “是位域运算符，表示fill占int类型32位中的16位，compress也占16位。

fill和compress的配置文件是redis.conf。

fill成员对应的配置：list-max-ziplist-size -2

当数字为负数，表示以下含义：
-1 每个quicklistNode节点的ziplist字节大小不能超过4kb。（建议）
-2 每个quicklistNode节点的ziplist字节大小不能超过8kb。（默认配置）
-3 每个quicklistNode节点的ziplist字节大小不能超过16kb。（一般不建议）
-4 每个quicklistNode节点的ziplist字节大小不能超过32kb。（不建议）
-5 每个quicklistNode节点的ziplist字节大小不能超过64kb。（正常工作量不建议）
当数字为正数，表示：ziplist结构所最多包含的entry个数。最大值为 215。
compress成员对应的配置：list-compress-depth 0

后面的数字有以下含义：
0 表示不压缩。（默认）
1 表示quicklist列表的两端各有1个节点不压缩，中间的节点压缩。
2 表示quicklist列表的两端各有2个节点不压缩，中间的节点压缩。
3 表示quicklist列表的两端各有3个节点不压缩，中间的节点压缩。
以此类推，最大为 216。

Hash的内部编码

redis.conf配置

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

ziplist(压缩列表)：当hash元素个数小于hash-max-ziplist-entries配置（默认512）
同时所有值都小于hash-max-ziplist-value配置（默认64个字节）时。redis会使用ziplist作为hash的内部实现。
ziplist使用更加紧凑的结构实现多个元素的连续存储，所以在节省内存方面比hashtable更加优秀。
hashtable（哈希表）：当哈希类型无法满足的ziplist的条件时，Redis会使用hashtable作为hash的内部实现，因为此时ziplist的读写效率会下降，而hashtabled的读写时间复杂度是O(1)。

集合set的内部编码

redis.conf配置

# Sets have a special encoding in just one case: when a set is composed
# of just strings that happen to be integers in radix 10 in the range
# of 64 bit signed integers.
# The following configuration setting sets the limit in the size of the
# set in order to use this special memory saving encoding.
set-max-intset-entries 512

intset（整数集合）：当集合中都是整数且元素个数小于set-max-intset-entries配置（默认512个）时，Redis会选用intset来作为内部实现，而减少内存使用。
hashtable （hash表）：当集合类型无法满足intset条件时，Redis来作为集合的内部实现。
下面用示例来说明：

（1）当元素个数较少且都为整数时，内部编码为intset：

127.0.0.1:6379> sadd setkey 2 3 4 5
(integer) 4
127.0.0.1:6379> object encoding setkey
"intset"

（2）当元素个数超过512个，内部编码变为hastable：

 127.0.0.1:6379>sadd setkey2 1 2 3 4 5 6 7...  511 512 513
OK
127.0.0.1:6379> object encoding setkey2
"hashtable"

（3）当某个元素不为整数时，内部编码也会变为hashtable：

127.0.0.1:6379> sadd setkey3 a b c
(integer) 3
127.0.0.1:6379> object encoding setkey2
"hashtable"

有序集合（zset）的内部编码

有序集合的内部实现有两种
redis.conf

# 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-ziplist-entries 128
zset-max-ziplist-value 64

ziplist（压缩列表）：当有序的集合个数小于zset-max-ziplist-entries配置（默认128）。
同时每个元素的值小于zset-max-ziplist-value的配置（默认64）的时候，redis会采用ziplistla作为有序集合作为内部的实现了，ziplist可以减少内存使用。
skiplist（跳跃表）：当ziplist不满足条件时，有序集合会使用skiplist作为内部实现，因为此时ziplist的效率会下降。

下面用示例来说明：

（1）当元素个数较少且每个元素较小时，内部编码为ziplist：

127.0.0.1:6379> zadd zsetkey 50 a 60 b 30 c
(integer) 3
127.0.0.1:6379> object encoding zsetkey
"ziplist"

（2）当元素个数超过128个，内部编码变为skiplist：

127.0.0.1:6379> zadd z1 1 c 1 d 2 e...1 123
(integer) 129
127.0.0.1:6379> object encoding zsetkey
"skiplist"

（3）当某个元素大于64个字节时，内部编码也会变为skiplist：

127.0.0.1:6379> zadd zsetkey 50 a 60 b 30 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
(integer) 1
127.0.0.1:6379> object encoding zsetkey
"skiplist"

ArrayList和Linklist

表中的 add() 代表 add(E e),而 remove()代表 remove(int index)'
ArrayList 对于随机位置的add/remove，时间复杂度为 O(n),但是对于列表末尾的添加/删除操作,时间复杂度是 O(1).
LinkedList对于随机位置的add/remove，时间复杂度为 O(n),但是对于列表 末尾/开头 的添加/删除操作,时间复杂度是 O(1).

转自：https://www.cnblogs.com/yangmingxianshen/p/8054094.html
https://blog.csdn.net/sunhuiliang85/article/details/74157048
http://zhangtielei.com/posts/blog-redis-quicklist.html