redis基本数据类型及其实现

仅供学习交流,如有错误请指出,如要转载请加上出处,谢谢

Redis是一个使用ANSI C编写的开源、支持网络、基于内存、可选持久性的键值对存储数据库(来自wiki),它提供丰富的数据结构类型:字符串(Strings),列表(Lists),哈希(Hashed),集合(Sets),有序集合(Sorted sets)来满足数据存储的需求,下面分别对这五大数据类型及其实现进行详述

字符串(String)

实现的数据结构

1. REDIS_ENCODING_INT(long类型整数)

场景:SET的value为整数
指令:SET msg 123

2. REDIS_ENCODING_RAW(大于32字节的字符串)

场景:SET的value为大于32字节的字符串
指令:SET msg LongString......

注意:SDS是redis内部构建基于字符串的数据结构(不是直接使用C字符串),它由free(未分配空间),len(字符串长度或已使用长度),buf(存储字符数组)三部分组成,降低操作字符串的复杂度
,len属性解决了不需要遍历整个字符串才能获取,free属性降低了内存重新分配的次数

3. REDIS_ENCODING_EMBSTR(小于32字节的字符串)

场景:SET的value为小于32字节的字符串
指令:SET msg hello

注意:对于字符串存储,对于raw编码模式,需要调用两次连续分配内存函数构建RedisObject和SDS这两块内存,而embstr的编码只需要一次性的内存分配一块连续的内存空间即可,

列表(Lists)

实现的数据结构

1. REDIS_ENCODING_ZIPLIST(压缩列表)

场景:(1)列表保存的元素都少于64个字节 (2)列表保存的元素数量少于512个
指令:RPUSH msg 'a' 'b' 'c'

注意:ZipList是redis基于小数值和短字符串而构建的数据结构,由zlbytes(压缩列表占用的字节数),zltail(压缩列表尾节点到起始地址的偏移量),zllen(节点数),entryx(压缩列表的各个节点),zlend(压缩列表的尾端标记值)

2. REDIS_ENCODING_LINKEDLIST(链表)

场景:(1)列表保存的元素都大于64个字节 (2)列表保存的元素数量大于512个
指令:RPUSH msg 'a' 'b' 'c' ......

注意:LinkedList是类似于java中的LinkedList,由一个双向链表构成,自带长度计数器和表头表尾指针,在对于增加删除时能高效的进行调整(前后指针重新指定)

哈希(Hashes)

实现的数据结构

1. REDIS_ENCODING_ZIPLIST(压缩列表)

场景:(1)哈希对象中的键值对的长度都小于64字节 (2)哈希对象中的键值对的数量小于512个
指令:HSET msg name "andy"

注意:利用压缩列表实现键值对,实现方法是:key在前,value在后,形成一个链

2. REDIS_ENCODING_HASHTABLE(哈希表)

场景:(1)哈希对象中的键值对的长度都大于64字节 (2)哈希对象中的键值对的数量大于512个
指令:HSET msg name "andy" age "24" ......

注意:HashTable也叫字典表,是整个redis的核心,类似于java中的HashTable,但是在其特殊的应用场景下,做出了一些改进,比如渐进式的rehash等等

集合(Sets)

实现的数据结构

1. REDIS_ENCODING_INTSET(整数集合)

场景:(1)集合中的元素为整数 (2)集合中的元素个数小于512个
指令:SADD msg 1 2 3

注意:IntSet是redis存储整数集合的数据结构,有encoding(编码,保存的位数类型),length(长度)和contents(整数数组)构成,可以灵活的根据整数的存储位数来选择相应的存储方式来节省内存

2. REDIS_ENCODING_HASHTABLE(哈希表)

场景:(1)集合中的元素不为整数 (2)集合中的元素个数大于512个
指令:SADD msg "a" "b" "c"

有序集合(Sorted Sets)

实现的数据结构

1. REDIS_ENCODING_ZIPLIST(压缩表)

场景:(1)有序集合中的元素小于128个 (2)有序集合中所有元素的集合都少于64个字节
指令:ZADD a 8 b 5

2. REDIS_ENCODING_SKIPLIST(跳跃表)

场景:(1)有序集合中的元素大于128个 (2)有序集合中所有元素的集合有多于64个字节
指令:ZADD a 8 b 5 ......

注意:跳跃表是一种有序的数据结构,它通过每个节点指向其它多个节点的指针,来到达最快的访问节点速度,由header(表头节点),tail(表尾节点),level(节点最大层数),length(节点数),简单的实现就是通过一个有序的链表,表示为第一层,再取其中头结点和尾节点,中间随机多个不重复节点组成新的链表,即为第二层,如下重复下去,直到到达随机(1-32层)的阈值,这样到达中间的节点的复杂度将会大大的降低。上图中是还使用了哈希来获取元素的分数值来进行排序。

参考

http://www.redis.cn/topics/data-types.html
https://read.douban.com/ebook/7519526/(数据库的设计与实现)