Redis是一个键值对数据库（key-valueDB），数据库的值可以是字符串、集合、列表等多种类型的对象，而数据库的键则总是字符串对象。
以下内容摘自（但不仅限于，其他地方引用有相应标注）：Redis命令参考Redis设计与实现（第一版）Redis设计与实现（第二版）Redis设计与实现Redis内部数据结构详解之跳跃表(skiplist)Redis内部数据结构详解之字典(dict)Redis中5种数据结构的使用场景介绍
前言
谈文章里的一些叫法？
宏观上：我们看到的是一些基本数据类型，如我们常用的哈希，列表，集合等；微观上：这此数据都是由Redis的底层（或称内部）数据结构来支撑的，比如字典，跳跃表；
我们管这种宏观的基本数据类型，比如哈希叫哈希（类型）键，我们管有序集合叫有序集合键；
Redis的每一种数据类型，比如字符串、列表、有序集，它们都拥有不只一种底层实现（Redis内部称之为编码，encoding）
关于文章想带来什么？
宏观的基本数据类型VS底层数据结构的关系如何；
底层数据结构长什么样子（整数集合、压缩列表进一步划分，属于内存映射数据结构，本文不作详细描述，后续可以专门分析下它们是如何相比其他数据结构节约内存的）；
更多地，燃起对数据结构的一些兴趣；
Redis六种内部数据结构
Sds(sds)
双端链表（linkedlist）
字典(dict)
跳跃表(skiplist)
整数集合(intset)
压缩列表(ziplist)
1.Sds
Sds（SimpleDynamicString，简单动态字符串）是Redis底层所使用的字符串表示，几乎所有的Redis模块中都用了sds。Sds在Redis中的主要作用有以下两个：
实现字符串对象（StringObject）；
在Redis程序内部用作char*类型的替代品；
主要特点：
Redis的简单动态字符串SDS对比C语言的字符串char*，有以下特性：
可以在O(1)的时间复杂度得到字符串的长度
可以高效的执行append追加字符串操作
二进制安全
应用场景：
其他模块（几乎每一个）都用到了sds类型值：用来保存数据库中的字符串值
SDS还被用作缓冲区（buffer）：客户端传入服务器的协议内容，AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是由SDS实现的
数据结构：
其中，类型sds是char*的别名（alias），而结构sdshdr则保存了len、free和buf三个属性
typedefchar*sds;structsdshdr{//buf已占用长度intlen;//buf剩余可用长度intfree;//实际保存字符串数据的地方charbuf[];};
为了易于理解，我们用一个Redis执行实例作为例子，解释一下，当执行以下代码时，Redis内部发生了什么：
redisSETmsg"helloworld"OKredisAPPENDmsg"again!"(integer)18redisGETmsg"helloworldagain!"
1.键值对的键和值都以SDS对象保存：键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串"msg"的SDS。键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串"helloworld"的SDS。
SET命令创建并保存helloworld到一个sdshdr中，这个sdshdr的值如下：
structsdshdr{len=11;free=0;buf="helloworld\0";}
3.当执行APPEND命令时，相应的sdshdr被更新，字符串会被追加到原来的之后，同时Redis为buf创建了多于所需空间一倍的大小：
structsdshdr{len=18;free=18;buf="helloworldagain!\0";//空白的地方为预分配空间，共18+18+1个字节}
2.双端链表
链表作为数组之外的一种常用序列抽象，是大多数高级语言的基本数据类型，因为C语言本身不支持链表类型，大部分C程序都会自己实现一种链表类型，Redis也不例外——实现了一个双端链表结构。
主要特点：
节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为(O(1))，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为(O(1))；
链表带有记录节点数量的属性，所以可以在(O(1))复杂度内返回链表的节点数量（长度）；
应用场景：
除了实现列表类型以外，双端链表还被很多Redis内部模块所应用
事务模块使用双端链表依序保存输入的命令；
服务器模块使用双端链表来保存多个客户端；
订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
事件模块使用双端链表来保存时间事件（timeevent）；
数据结构：
双端链表的实现由listNode和list两个数据结构构成：
其中，是双端链表的节点：
typedefstructlistNode{//前驱节点structlistNode*prev;//后继节点structlistNode*next;//值void*value;}listNode;
而则是双端链表本身：
typedefstructlist{//表头指针listNode*head;//表尾指针listNode*tail;//节点数量unsignedlonglen;//复制函数void*(*dup)(void*ptr);//释放函数void(*free)(void*ptr);//比对函数int(*match)(void*ptr,void*key);}list;
注意，的value属性的类型是void*，说明这个双端链表对节点所保存的值的类型不做限制。
Redis列表使用两种数据结构作为底层实现：1.双端链表2.压缩列表因为双端链表占用的内存比压缩列表要多，所以当创建新的列表键时，列表会优先考虑使用压缩列表作为底层实现，并且在有需要的时候，才从压缩列表实现转换到双端链表实现。
3.字典
Redis的字典使用哈希表作为底层实现（双哈希表），一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
主要特点：
Redis的字典是使用一个桶bucket，通过对key进行hash得到的索引值index，然后将key-value的数据存在桶的index位置，Redis处理hash碰撞的方式是链表，两个不同的keyhash得到相同的索引值，那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候，字典不免会退化成多个链表，效率大大降低，Redis采用rehash的方式对桶进行扩容来解决这种退化。
参考：
小结：
Redis中的字典数据结构使用哈希表来实现，用来存储key-value键值元素；
字典使用两个哈希表，一般只使用ht[0]，只有当Rehash时候才使用ht[1]；
Redis使用MurmurHash2算法来计算键的哈希值；
哈希表采用链表的方式解决键碰撞问题；
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。
应用场景：
字典在Redis中的应用广泛，使用频率可以说和SDS以及双端链表不相上下，基本上各个功能模块都有用到字典的地方。其中，字典的主要用途有以下两个：1.实现数据库键空间（keyspace）；2.用作Hash类型键的底层实现之一；
实现数据库键空间Redis是一个键值对数据库，数据库中的键值对由字典保存：每个数据库都有一个对应的字典，这个字典被称之为键空间（keyspace）。
OK
在数据库中创建一个键为"msg"，值为"helloworld"的键值对时，这个键值对就是保存在代表数据库的字典里面的。
用作Hash类型键的底层实现之一Redis的Hash类型键使用以下两种数据结构作为底层实现:
字典；
压缩列表；
当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。举个例子，website是一个包含个键值对的哈希键，这个哈希键的键都是一些数据库的名字，而键的值就是数据库的主页网址：
redisHSETwebsiteRedis"
本文编辑：佚名
转载请注明出处:网站地址 http://www.cqwpz.com/kcyzl/11336322.html