redis支持的几种数据结构

字符串

列表

set

sort-set

map

redisobj 存储结构

结构定义：

typedef struct redisObject {

unsigned type:4; // 刚刚好32 bits，对象的类型，字符串/列表/集合/哈希表

    unsigned encoding:4; // 编码的方式，Redis 为了节省空间，提供多种方式来保存一个数据

    unsigned lru:22;   // 当内存紧张，淘汰数据的时候用到

    int refcount;  // 引用计数

    void *ptr; // 数据指针

type的类型主要有：

#define REDIS_STRING 0

#define REDIS_LIST 1

#define REDIS_SET 2

#define REDIS_ZSET 3

#define REDIS_HASH 4

encoding类型主要有：

/* Objects encoding. Some kind of objects like Strings and Hashes can be

* internally represented in multiple ways. The 'encoding' field of the object

* is set to one of this fields for this object. */

#define REDIS_ENCODING_RAW 0 /* Raw representation */

#define REDIS_ENCODING_INT 1 /* Encoded as integer */

#define REDIS_ENCODING_HT 2 /* Encoded as hash table */

#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */

#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */

#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */

#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */

#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */

string存储方式

int：如果是类似于字符串"123456"的字符串，redis会选择存为整形123456，以节省存储占用。

sds（simple dynamic string）：sds用于存储字节/字符串和浮点型数据。

struct sdshdr {

   int len;

   int free;

   char buf[]; 

};

为什么使用 char buf[]代替char *buf呢？

1. 内存管理方便，如果使用char *buf需要两次内存申请，释放也需要两次，而 char buf[]只需要一次。

2. 长度为 0 的数组即 char buf[] 不占用内存

优点：

1. sds 获取字符串的长度以及剩余空间的复杂度都是 O(1)，而普通字符串都需要O(N)

append 操作优化：

追加内容的长度不超过 free 属性的值， 那么就不需要对 buf 进行内存重分配，如果超过，则申请一倍内存，比如：

append前：

struct sdshdr {

    len = 11;

    free = 0;

    buf = "hello world\0";

}

append后：

struct sdshdr {

    len = 18;

    free = 18;

    buf = "hello world again!\0                  ";     // 空白的地方为预分配空间，共 18 + 18 + 1 个字节

}

list存储方式

双链表（LinkedList）

压缩双链表（ziplist）

压缩双链表以连续的内存空间 来表示双链表，压缩双链表节省前驱和后驱指针的空间（8b）

连续内存结构：

...

entry内存结构：

<>

其中预定义的字符串长度：

#define ZIP_STR_06B (0 << 6>

#define ZIP_STR_14B (1 << 6>

#define ZIP_STR_32B (2 << 6>

整形长度：

#define ZIP_INT_16B (0xc0 | 0<<4>

#define ZIP_INT_32B (0xc0 | 1<<4>

#define ZIP_INT_64B (0xc0 | 2<<4>

#define ZIP_INT_24B (0xc0 | 3<<4>

#define ZIP_INT_8B 0xfe

ziplist 每次新增数据都会realloc，这时可能会涉及到内存重新申请和拷贝的操作，所以通常用于list长度不长和元素不大的情况，同时因为ziplist不是标准的数组结构，遍历插入删除基本O(N)，大量数据的情况下对于linkedlist没有性能上的优势，如果数据小量并且紧凑， ziplist 能够放入 CPU 缓存效率也非常高，同时内存占用非常小。

转化配置：

list-max-ziplist-entries 512 # 最大接受长度为512，超过此长度则转换为linked_list的存储模式。

list-max-ziplist-value 64 # 每个元素的大小，最大不超过64bytes，超过则转换为linked_list。

Map存储方式

hashtable

ziplist（还是数据量比较小的情况下采用，存储的方式奇位为key，偶位为value）

redis的hashtable有两个链表，主要为了能够在不中断服务的情况下扩展（expand）哈希表，使用开链法解决冲突，每次插入选择头部好处：1. 每次插入O(1)；2. 数据库系统来说，最新插入的数据往往更有可能频繁的被获取。

正常情况下，比如java的hashmap的扩容，会导致rehash和拷贝，redis的做法和golang相似，使用增量扩容，避免在扩容的时候出现服务阻塞。

redis增量扩容，第一链表拷贝至第二链表的时机：

1. 定时任务

2. curd操作

好处：

1. 在扩容期间，查询收到部分影响，但是要比停止服务要好得多

2. 在扩容期间，写操作会出现多次查询操作，效率比较低 

Set存储方式

hashtable

intset（当添加的所有数据都是整数时，一旦出现字符串型，会转为hashtable）

intset 底层本质是一个有序的、不重复的、整型的数组，支持不同类型整数。

typedef struct intset {

uint32_t encoding;// 每个整数的类型

uint32_t length;// intset 长度

int8_t contents[];// 整数数组

} intset;

encoding（只能升级不能降级）：

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

intset 搜索：二分查找Sort-Set存储方式

ziplist（和map类型）

skiplist+hashtable（通用解决方案）

hashtable 只是用在快速查找某元素在不在集合中，排序主要用skiplist

Redis支持五中数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）及zset(sortedset：有序集合)。

Redis定义了丰富的原语命令，可以直接与Redis服务器交互。实际应用中，我们不太会直接使用这些原语命令，Redis提供了Java，C/C++，C#，PHP，JavaScript，Perl，Object-C，Python，Ruby，Erlang等客户端，大多情况下我们是通过各式各样的客户端来操作Redis。但是，任何语言的客户端实际上都是对Redis原语命令的封装，了解原语命令有助于理解客户端的设计原理，知其然，知其所以然。