Redis外部数据结构与内部数据结构

外部数据结构与内部数据结构

外部数据结构除了常用的5种：字符串String，哈希表Hash，列表List，集合Set，有序集合Sort Set，还有数据结构bitmap，HyperLogLog，Geo,Streams。外部结构对外使用，根据数据类型的不同，Redis内选用不同的内部结构。

Redis数据结构

这样设计的好处是改变内部编码对外部没有影响（包装者模式），外部的数据结构和命令无需改变，多种内部数据结构可以发挥各自的优势。

外部数据、内部数据结构查看指令：

> set name zhangsan
OK
> type name
string
> object encoding name
embstr

1.string

int 8个字节的长整型
embstr 小于44个字节的字符串
raw 大于44个字节小于512M的字符串

int

当value是整型时，内部就会使用int。

embstr与raw

embstr编码将创建字符串对象所需的空间分配的次数从raw编码的两次降低为一次。因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能更好地利用缓存带来的优势。并且释放embstr编码的字符串对象只需要调用一次内存释放函数，而释放raw编码对象的字符串对象需要调用两次内存释放函数。

2.hash

当filed的个数少于512，且没有value大于64字节时，内部编码为ziplist
当filed的个数大于512，或者value大于64字节时，内部编码为hashtable

> hmset rank 1 yuwei 2 yuwei2 3 yuwei3
OK
> object encoding rank
ziplist
> hset rank 4 "Redis modules can access Redis built-in data structures both at high level, by calling Redis commands, and at low level, by manipulating the data structures directly."
1
> object encoding rank
hashtable

ziplist

list、hash、Sort Set三种外部结构，在某些情况下内部数据结构都使用了ziplist，因为ziplist充分体现了Redis对于存储效率的追求。

一个普通的双向链表，每一个节点都会占用一块内容，各个节点通过指针连接，这种方式会产生大量的内存碎片，而且地址指针会占用额外的内存空间。ziplist将列表中的每一项存放在一块连续的地址空间内，所以一个ziplist只占一块大的内存。

hashtable

和Java中的HashMap一样。

3.list

3.2之前
- 当列表list中的元素个数少于512，且没有value大于64字节时，内部编码为ziplist
- 当列表list中的元素个数大于512，或者value大于64字节时，内部编码为linkedlist

3.2 之后

都使用quicklist

> rpush ques 123 234
2
> object encoding ques
quicklist

linkedlist

双向链表，没啥说的。

quicklist

quicklist结合了双向列表linkedlist和ziplist的特点，它是一个双向无环链表，它的每一个节点都是一个ziplist，所有的节点都用quicklist存储，省去了临界时的格式转换。

4.set

当集合set中的元素都是整数且元素个数小于512(默认时)使用intset
其它条件使用hashtable

> sadd ques 1 2 3
3
> object encoding ques
intset
> sadd ques aaa
1
> object encoding ques
hashtable

intset

Set特殊内部编码，它是一个有序的整形数组，再内存分配上和ziplist有些类似，是连续的一块内存空间。

5.Sort Set

元素个数少于128(默认为128)，且没有value大于64字节时，内部编码为ziplist
元素个数大于128(默认为128)，或者value大于64字节时，内部编码为skiplist

> zadd ques 1 zhangsan 2 lisi
2
> object encoding ques
ziplist
> zadd ques 3 "Redis modules can access Redis built-in data structures both at high level, by calling Redis commands, and at low level, by manipulating the data structures directly."
1
> object encoding ques
skiplist

skiplist

跳表skiplist

Sorted set实现多维排序

Sorted set默认只使用一个因子进行排序，如果想要实现根据多个因子进行排序，比如外卖综合排序需要考虑距离，评分，价格，就需要将多个排序因子转换为一个排序因子，result = function(x, y, z)。

6.bitmap

bitmap实现了Redis的Bloom Filter（布隆过滤器）。

bitmap并不是一个真实的数据机构，它本质是String数据结构，不过操作的粒度是bit。String最大的长度是512M，所以bitmap允许存储2^32个bit。

bloomFilter

Bloom Filter用于判断一个元素是否存在于集合中，他的空间效率和时间效率远超过一般的算法，不过会有一定的误识别率（3%）。

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。

Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

7.Geo

GEO功能在Redis3.2版本提供，使用Geo可以在Redis中存储地理坐标，用来实现诸如附近位置、摇一摇这类依赖于地理位置信息的功能.

和bitmap一样，Geo并不是一个数据结构，本质上是Sort Set，并且使用GeoHash技术进行填充。

8.HyperLogLog

HyperLogLog 是用来做基数统计的算法，基数统计的意思是一个集合中不重复元素的个数。即使元素的数量或体积特别大，计算基数所需要的空间是固定的，而且很小。

> PFADD hll a b c d e f g
1
> object encoding hll
raw

9.Streams

Streams是Redis5.0以后引入的数据结构，Streams就是Redis实现的内存版kafka。