Redis五种数据类型是如何实现的
Redis对象类型简介
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跳跃表和字典
字符串对象
字符串对象的编码可以是int、raw或者embstr。
如果⼀个字符串的内容可以转换为long，那么该字符串就会被转换成为long类型，对象的ptr就会指向该long，并且对象类型也⽤int类型表⽰。
普通的字符串有两种，embstr和raw。embstr应该是Redis 3.0新增的数据结构，在2.8中是没有的。如果字符串对象的长度⼩于39字节，就⽤embstr对象。否则⽤传统的raw对象。从下⾯代码就可以看出
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39
robj *createStringObject(char *ptr, size_t len) {
if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
return createEmbeddedStringObject(ptr,len);
else
return createRawStringObject(ptr,len);
}
embstr的好处有如下⼏点：
embstr的创建只需分配⼀次内存，⽽raw为两次（⼀次为sds分配对象，另⼀次为objet分配对象，embstr省去了第⼀次）。
相对地，释放内存的次数也由两次变为⼀次。
embstr的objet和sds放在⼀起，更好地利⽤缓存带来的优势。
需要注意的是，redis并未提供任何修改embstr的⽅式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进⾏修改。
raw和embstr的区别可以⽤下⾯两幅图所⽰：
列表对象
列表对象的编码可以是ziplist或者linkedlist。
ziplist是⼀种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不⼤，每个元素也不⼤的时候，就采⽤ziplist存储。但当数据量过⼤时就ziplist就不是那么好⽤了。因为为了保证他存储内容在内存中的连续性，插⼊的复杂度是O(N)，即每次插⼊都会重新进⾏realloc。如下图所⽰，对象结构中ptr所指向的就是⼀个ziplist。整个ziplist只需要malloc⼀次，它们在内存中是⼀块连续的区域。
linkedlist是⼀种双向链表。它的结构⽐较简单，节点中存放pre和next两个指针，还有节点相关的信息。
当每增加⼀个node的时候，就需要重新malloc⼀块内存。
哈希对象
哈希对象的底层实现可以是ziplist或者hashtable。
ziplist中的哈希对象是按照key1,value1,key2,value2这样的顺序存放来存储的。当对象数⽬不多且内容不⼤时，这种⽅式效率是很⾼的。hashtable的是由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;
dict是⼀个字典，其中的指针dicht ht[2] 指向了两个哈希表
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
dicht[0] 是⽤于真正存放数据，dicht[1]⼀般在哈希表元素过多进⾏rehash的时候⽤于中转数据。
dictht中的table⽤语真正存放元素了，每个key/value对⽤⼀个dictEntry表⽰，放在dictEntry数组中。
集合对象
集合对象的编码可以是intset或者hashtable。
intset是⼀个整数集合，⾥⾯存的为某种同⼀类型的整数，⽀持如下三种长度的整数：
#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类型，涉及到内存的重新分配，这时插⼊的复杂度就为O(N)了。是intset不⽀持降级操作。
有序集合对象
有序集合的编码可能两种，⼀种是ziplist，另⼀种是skiplist与dict的结合。
ziplist作为集合和作为哈希对象是⼀样的，member和score顺序存放。按照score从⼩到⼤顺序排列。它的结构不再复述。
skiplist是⼀种跳跃表，它实现了有序集合中的快速查，在⼤多数情况下它的速度都可以和平衡树差不多。但它的实现⽐较简单，可以作为平衡树的替代品。它的结构⽐较特殊。下⾯分别是跳跃表skiplist和它内部的节点skiplistNode的结构体：
/*
* 跳跃表
*/
typedef struct zskiplist {
// 头节点，尾节点
struct zskiplistNode *header, *tail;
/
/ 节点数量
unsigned long length;
// ⽬前表内节点的最⼤层数
int level;
} zskiplist;
/* ZSETs use a specialized version of Skiplists */
/*
redis支持的五种数据类型* 跳跃表节点
*/
typedef struct zskiplistNode {
// member 对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 这个层跨越的节点数量
unsigned int span;
} level[];
} zskiplistNode;
head和tail分别指向头节点和尾节点，然后每个skiplistNode⾥⾯的结构⼜是分层的(即level数组)
⽤图表⽰，⼤概是下⾯这个样⼦：
每⼀列都代表⼀个节点，保存了member和score，按score从⼩到⼤排序。每个节点有不同的层数，这个层数是在⽣成节点的时候随机⽣成的数值。每⼀层都是⼀个指向后⾯某个节点的指针。这种结构使得跳跃表可以跨越很多节点来快速访问。
前⾯说到了，有序集合ZSET是有跳跃表和hashtable共同形成的。
typedef struct zset {
// 字典
dict *dict;
// 跳跃表
zskiplist *zsl;
} zset;
为什么要⽤这种结构呢。试想如果单⼀⽤hashtable，那可以快速查、添加和删除元素，但没法保持集合的有序性。如果单⼀⽤skiplist，有序性可以得到保障，但查的速度太慢O（logN）。
结尾
简单介绍了Redis的五种对象类型和它们的底层实现。事实上，Redis的⾼效性和灵活性正是得益于对于同⼀个对象类型采取不同的底层结构，并在必要的时候对⼆者进⾏转换；以及各种底层结构对内存的合理利⽤。
blog.csdn/caishenfans/article/details/44784131

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。