位置:首页  >   数据库  > redis底层数据结构总结

redis底层数据结构总结

redis有五种对象的类型

REDIS_STRING  字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象


底层数据结构共有八种
编码常量 编码对应的底层数据结构
1、REDIS_ENCODING_INT long类型的整数
2、REDIS_ENCODING_EMBSTR embstr编码的简单动态字符串
3、REDIS_ENCODING_RAW 简单动态字符串
4、REDIS_ENCODING_HT 字典
5、REDIS_ENCODING_LINKEDLIST 双端链表
6、REDIS_ENCODING_ZIPLIST 压缩列表
7、REDIS_ENCODING_INTSET 整数集合
8、REDIS_ENCODING_SKIPLIST 跳跃表和字典


1.字符串对象
编码可以为 int、embstr或者raw。
如果一个字符串的内容可以转换为long,那么该字符串就会被转换成为long类型,对象的ptr就会指向该long,并且对象类型也用int类型表示。
普通的字符串有两种,embstr和raw。embstr应该是Redis3.0新增的数据结构,在2.8中是没有的。如果字符串对象的长度小于39字节,就用embstr对象。否则用传统的raw对象。

2.列表对象
编码可以是ziplist或者linkedlist。
ziplist是一种压缩链表,它的好处是更能节省内存空间,因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大,每个元素也不大的时候,就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性,插入的复杂度是O(N),即每次插入都会重新进行realloc。
linkedlist是一种双向链表。它的结构比较简单,节点中存放pre和next两个指针,还有节点相关的信息。当每增加一个node的时候,就需要重新malloc一块内存。

当列表对象可以同时满足以下两个条件时, 列表对象使用 ziplist 编码:
列表对象保存的所有字符串元素的长度都小于 64 字节;
列表对象保存的元素数量小于 512 个;
不能满足这两个条件的列表对象需要使用 linkedlist 编码。
ps:
因为压缩列表比双端链表更节约内存, 并且在元素数量较少时, 在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中;
随着列表对象包含的元素越来越多, 使用压缩列表来保存元素的优势逐渐消失时, 对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面


3.哈希对象
编码可以是ziplist或者hashtable。
ziplist中的哈希对象是按照key1,value1,key2,value2这样的顺序存放来存储的。当对象数目不多且内容不大时,这种方式效率是很高的。
hashtable的是由dict这个结构来实现的,dict是一个字典,其中的指针dicht ht[2] 指向了两个哈希表。dicht[0]是用于真正存放数据,dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。
dictht中的table用语真正存放元素了,每个key/value对用一个dictEntry表示,放在dictEntry数组中


4.集合对象
编码可以是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不支持降级操作。

当集合对象可以同时满足以下两个条件时, 对象使用 intset 编码:
集合对象保存的所有元素都是整数值;
集合对象保存的元素数量不超过 512 个;
不能满足这两个条件的集合对象需要使用 hashtable 编码。
ps:
第二个条件的上限值是可以修改的, 具体请看配置文件中关于 set-max-intset-entries 选项的说明。


5.有序集合对象
有序集合的编码可能两种,一种是ziplist,另一种是skiplist与dict的结合。
ziplist作为集合和作为哈希对象是一样的,member和score顺序存放。按照score从小到大顺序排列。
skiplist是一种跳跃表,它实现了有序集合中的快速查找,在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单,可以作为平衡树的替代品。
当有序集合对象可以同时满足以下两个条件时, 对象使用 ziplist 编码:
有序集合保存的元素数量小于 128 个;
有序集合保存的所有元素成员的长度都小于 64 字节;
不能满足以上两个条件的有序集合对象将使用 skiplist 编码。
ps:
以上两个条件的上限值是可以修改的, 具体请看配置文件中关于 zset-max-ziplist-entries 选项和 zset-max-ziplist-value 选项的说明。

文章属性
精彩评论