Redis数据结构及如何用好这些数据结构 Redis数据结构及如何用好这些数

这篇文章延续精简的风格，争取能让大家8min内读完并有所收获。
概述一周前的文章精简的介绍了Redis核心原理及Redis是如何工作的，这一章回归到Redis的本质上来（存储）。Redis之所以如此受欢迎，一方面是性能强劲，另一方面就是支持多种常见的数据结构，甚至能完成一定的数据运算工作，灵活性大大提升。
Redis的常用四大数据结构类型，将一一介绍
1）String
2）List
3）Hash
4）Set

文章图片
Redis数据结构

在文章Redis核心原理中介绍了，Redis字典的KV都是由redisObject组成的，每种Redis数据类型都是由不同的编码方式和真实的底层数据类型（ptr）实现，本文先介绍底层数据实现

SDS

文章图片
Redis string底层实现

struct sdshdr {
// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;
// 记录 buf 数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串
char buf[];
};

1）获取字符串长度的复杂度是O(1)
2）执行append操作时，如果空间不足则自动分配新空间，不会导致buf溢出
3）当字符串长度小于1MB时，将分配与len相同大小的未使用空间（如图所示），目的是在空间占用和空间重分配之间取得平衡

LINKEDLIST

文章图片
Redis链表实现 1）list是双向链表，RPUSH LPUSH由此实现
2）获取链表长度为O(1)

HASH TABLE

文章图片
Redis 哈希表实现 1）获取hash表size/used的复杂度为O(1)
2）有两张hash表组成，如果没有rehash状态下，rehashidx为-1，且其中的一张表是空的。当rehash时，为了不影响redis的性能，同时使用两张表渐进式的完成rehash：设置rehashidx为0，当查询或修改key时把KV转移到新表上去，直至旧表为空，设置rehashidx为-1，完成迁移
3）为什么hash table的长度是2的N次幂？因为bucket = hashcode & (len-1)，当len为2的N次幂时len-1=1111。。因此原有的对象只有少部分会被重新分配到新的bucket中去，因为(len-1) -> （2*len-1）时只有最高位的0变成了1，会减少迁移的工作量，提高效率
INT SET

文章图片
Redis的整数集合 1）获取set length的复杂度为O(1)
2）encoding表明取值范围及内存占用，因此Redis并不适合将少量过大的数和大量小数值存在一起，会造成空间浪费
ZIPLIST

文章图片
Redis的压缩表 1）ziplist是链表和哈希表的底层实现之一
2）ziplist采用更紧凑的编码，减少内存使用
以下是Redis的数据结构全貌 String

文章图片
Redis字符串对象 List

文章图片
ziplist实现的List

文章图片
linked list实现的List 1）当列表中的object数量小于512个时，redis使用ziplist这种占用空间更小的结构
Hash

文章图片
ziplist实现的哈希对象

文章图片
hashtable实现的哈希对象 1）当哈希表中的object数量小于512个时，Redis使用ziplist这种占用空间更小的结构。虽然复杂度为O(N)，但由于object数量少，不会对CPU造成影响
Set

文章图片
intset只包含数值类型的set 【Redis数据结构及如何用好这些数据结构】

文章图片
其它set 1）当一个set中全是数字时，采用intset为底层，占用空间小，因为尽量不要把少数string和大量int存储在一个set里
总结 1）使用哈希表、列表及集合时，尽量不要使用big data及添加过多的数据，因为这样会导致存储结构从ziplist变为hash table、linkedlist等空间占用更大的数据结构
2）如无必要的情况下，一个集合中不要将string和int混合存储，这会导致内存占用变大
3）String不要过长，小于39字符时，使用embstr编码格式，占用更少内存
4）set可以用来做数据运算，如交、并等大量数据的运算
参考文档 Redis设计与实现
Redis原理及应用