Redis对象类型（类型常量：对象名称）
- REDIS_STRING： 字符串对象
- REDIS_LIST： 列表对象
- REDIS_HASH： 哈希对象
- REDIS_SET： 集合对象
- REDIS_ZSET： 有序集合对象
Redis对象的底层数据结构（编码常量：编码所对应的底层数据结构）
- REDIS_ENCODING_INT： long 类型的整数
- REDIS_ENCODING_EMBSTR： embstr 编码的简单动态字符串
- REDIS_ENCODING_RAW： 简单动态字符串
- REDIS_ENCODING_HT： 字典
- REDIS_ENCODING_LINKEDLIST： 双向链表
- REDIS_ENCODING_ZIPLIST： 压缩列表
- REDIS_ENCODING_INTSET： 整数集合
- REDIS_ENCODING_SKIPLIST：跳跃表和字典
一个Redis对象的结构
/*
* Redis 对象
*/
typedef struct redisObject {
// 类型
unsigned type:4;
// 不使用(对齐位)
unsigned notused:2;
// 编码方式
unsigned encoding:4;
// LRU 时间（相对于 server.lruclock）
unsigned lru:22;
// 引用计数
int refcount;
// 指向对象的值
void *ptr;
} robj;
先介绍Redis的数据结构
1.简单动态字符串SDS
- redis实现了一个SDS结构(简单动态字符串)类型来替代C语言中的原生字符串，结构如下：
struct sdshdr {
//记录buf中字符串的实际长度
int len;
//记录buf数组空闲长度
int free;
//字节数组,用于保存字符串
char buf[];
};
- SDS结构和C语言原生字符串类型相比有以下优点：
1、因为存储了字符串长度,可以常数复杂度获取字符串长度。
2、同样由于存储了字符串实际长度和buff空闲长度,字符串变化时不需要每次都重新分配内存, 同时也避免了字符串长度变化可能导致的缓冲区溢出和内存泄漏。
3、二进制安全, SDS的设计由于根据字符串长度来判断字符串的末尾,因此中间可以存储任何数据包括空字符。 - embstr和raw都是SDS结构，相比于raw使用embstr编码redis对象好处：
1、创建只需要分配一次内存，而使用raw编码则需要2次(一次为sds分配内存，另一次为object分配内存，embstr编码省去了第一次)。
2、释放内存的次数也由2次变为1次。
3、embstr编码对象的object和sds放在一起，更好的利用缓存带来的优势。
2.整数集合 INTSET
- 有序无重复的数组, 可以通过二分法进行查找操作。
3.Hash表 HT
- redis的hash算法是MurmurHash算法(这种算法优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快), 处理冲突使用链地址法。随着操作不断进行,当hash表保存的键值对过多或过少时,需要对hash表的槽位数组进行扩展或收缩以获得更好的性能和内存利用率,这个操作称为rehash。redis中的rehash就是通过创建一个临时的字典,将正在使用的字典中的所有键值对复制到临时字典中(这个过程需要重新计算hash值和索引值,因此称为rehash),最后释放老的字典,并将其指针指向临时字典。当数据量比较小的时候,这个过程可以一次性完成，但是数据量大的时候,庞大的计算量可能导致整个服务停止,因此redis采用了渐进式rehash(写时复制),就是同时维护两个hash表hd[0]和hd[1],设置rehash_idx设置为0，在0< rehash_idx < 槽位数组长度时, 对hash表的任何操作除了执行正常的操作过程以外，还会将hd[0]槽位数组rehash_idx索引上的所有键值对rehash到hd[1],这个过程中的查找会同时使用两个表进行操作,同时所有的添加键值对操作只会在hd[1]上进行,保证了hd[0]只减不增。rehash完成后,hash表指针指向hd[1],释放hd[0]内存。
4.压缩列表 ZIPLIST
- 为节约内存开发，由一系列特殊编码的连续内存块组成的顺序型数据结构，每个压缩列表节点可以保存一个字节数组或一个整数值。其由3部分构成：
----------------------------------------
| prev_entry_length | encoding | content |
----------------------------------------
- 其中content为实际数据,encoding存储了content的具体数据类型,prev_entry_length则保存了前一个节点的占用的内存长度,通过这个值就可以定位到前一个节点。在压缩列表中为了节省内存可能会造成连锁更新,因此存在一定的性能隐患,但是由于本身出现的概率就比较小,在节点数量不多的情况下这种影响可以忽略不计。
5.双向链表 LINKEDLIST
- 就是含有前驱和后继节点的普通双向链表，其保存头节点、尾节点和链表长度，可以接获取链表长度。
6.跳表 SKIPLIST
跳跃表是一种有序的数据结构，支持平均O(logN)的时间复杂度,平均O(N)的空间复杂度的节点查找,其效率可以和平衡树媲美，同时实现简单,而且由于不需要reblance操作,在高并发情况下表现更加出色。
Redis的5种数据类型及底层数据结构
1.字符串对象 String
- 字符串的编码可以是int、raw或embstr。
- 优先级：如果一个字符串的内容可以转换为long类型，那么该字符串就会被转换成long类型，Redis对象的ptr就会指向该long类型的对像，并且对象编码常量也用int。
- 而普通的字符串有2种，embstr或raw编码。如果字符串对象的长度小于等于32字节，就使用embstr编码。否则用传统的raw编码。
- embstr是一种短字符串的优化,其存储还是使用SDS结构,但raw编码会调用两次内存分配函数来分别创建redisObject结构和SDS结构,而embstr编码则通过调用一次内存分配函数来分配 一块连续的空间,空间中依次包含redisObject和SDS结构。
2.列表对象 List
- 列表对象的编码可以是ziplist或linkedlist。
- zpilist是压缩列表，需要使用连续的内存区域。当列表对象元素不多，元素体积不大时，Redis就采用ziplist存储。当数据量过大时，无法保证找到那么大的连续内存空间；而且插入的复杂度变为O(n)，每次插入都会重新realloc(动态内存调整，意思是当前内存无法存入更多数据时，申请分配新的连续内存)，而实际ziplist只需要一次malloc(动态内存分配，也就是初始化内存时分配一块合适的，此后不用再调整)。此时就使用linkedlist来存储对象，每当增加一个节点的时候，就需要重新malloc一块内存。
3.哈希对象 Hash
- 哈希对象的编码可以使用ziplist或hashtable。
- ziplist中的哈希对象按照key1，value1，key2，value2的顺序存放。当对象数目不多内容不大时，这种方式效率很高。
- ht是由dict结构来实现的
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
4.集合对象 Set
- 集合对象的编码可以是intset或者hashtable。只有当Set中的所有元素均为整数类型时才会使用intset。
- intset是一个整数集合，里面存的是某种同一类型的整数，支持如下3种长度的整数：
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
- intset是一个有序集合，查找元素的复杂度为O(logN)，但插入时不一定为O(logN)，因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数，这时要插入一个int32_t，那么为了维持集合中数据类型的一致，那么所有的数据都会被转换成int32_t类型，涉及到内存的重新分配(realloc)，这时插入的复杂度就为O(N)了。intset不支持降级操作。
5.有序集合对象 ZSet
- 有序集合对象的编码可以是ziplist或者skiplist与hastable的结合。
- ziplist作为集合和作为哈希对象是一样的，不同的是哈希对象是key，value顺序存放，而有序集合是member和score顺序存放。按照score从小到大排序。
- skiplist是跳表，它实现了有序集合中的快速查找，大多数情况下它的查询速度可以和平衡树差不多。但是它实现比较简单，可以作为平衡树的替代品。
- 单一用hashtable，那可以快速查找、添加和删除元素，但没法保持集合的有序性。如果单一用skiplist，有序性可以得到保障，但查找的速度太慢O(logN)。
原文：https://blog.csdn.net/caishenfans/article/details/44784131
参考：https://www.jianshu.com/p/f8ccf8806095
