一、概述Redis是开源的，用ANSIC语言编写的，遵守BSD协议，支持网络，可以基于内存，可以持久化日志类型，Key-Value数据库，与Memcached类似，但优于Memcached的高性能key-value数据库。下面详细介绍一下redis中五大数据结构的底层实现。二、简单的动态字符串1、概述Redis是一个用ANSIC语言编写的开源键值数据库。我们可能主观上认为Redis中的字符串是用C语言的传统字符串来表示的，但实际上，Redis并没有直接使用C语言的传统字符串表示，而是构建了一个抽象类型，叫做简单动态字符串（simpledynamicstringSDS）,并使用SDS作为Redis的默认字符串表示：redis>SETmsg"helloworld"SDS定义：structsdshdr{//记录buf数组中使用的字节数//等于SDS保存字符串的长度intlen;//记录buf数组中未使用的字节数intfree;//字节数组，用于保存字符串charbuf[];}图片来源：《Redis设计与实现》我们看上面SDS数据类型的定义：len保存了SDSbuf[]数组保存的字符串的长度保存字符串freej的每个元素记录了buf数组 2中未使用的字节数。与C语言相比 一般来说，SDS除了在数据库中保存字符串值外，还可以作为缓冲区域（buffer）：包括AOF模块中的AOF缓冲区和client态中的输入缓冲区.后面介绍Redis的持久化时会介绍。三、链表1、概述链表提供了高效的节点重排能力和顺序节点访问方式，可以通过增加或删除节点灵活地调整链表的长度。链表在Redis中被广泛使用。例如，列表键的底层实现之一是链表。当一个listkey包含大量元素，或者list包含的元素是比较长的字符串时，Redis会使用链表作为listkey的底层实现。每个链表节点由一个listNode结构表示（adlist.h/listNode）：typedefstructlistNode{//前节点structlistNode*prev;//后节点structlistNode*next;//节点值void*value;}listNode链表数据结构：typedefstructlist{//表头节点listNode*head;//表尾节点??listNode*tail;//链表包含的节点个数unsignedlonglen;//节点值复制函数void(*free)(void*ptr);//节点值释放函数void(*free)(void*ptr);//节点值比较函数int(*match)(void*ptr,void*key);}list;结束：链表有前节点和后节点的引用，获取这两个节点的时间复杂度为O(1)。非循环：头节点的prev指针和尾节点的next指针都指向NULL，链表的访问以NULL结束。 带链表长度计数器：通过len属性获取链表长度的时间复杂度为O(1)。多态性：链表节点使用void*指针保存节点值，可以保存各种类型的值。4.字典1.概述字典，又称符号表或关联数组，或映射，是一种用于存储键值对的抽象数据结构。字典中的每个键key都是唯一的，可以通过key查找或修改值。C语言中并没有内置这个数据结构的实现，所以字典仍然是Redis自己构建的。哈希表结构定义：typedefstructdict{//哈希表数组dictEntry**table;//哈希表大小unsignedlongsize;//哈希表大小掩码，用于计算索引值//始终等于size-1unsignedlongsizemask;//哈希表中已有的节点个数unsignedlongused;}dictht哈希表由一个数组表组成，表中的每个元素指向dict.h/dictEntry结构体，dictEntry结构体定义如下：typedefstructdictEntry{//keyvoid*key;//valueunion{void*val;uint64_tu64;int64_ts64;}v;//指向下一个哈希表节点组成链表structdictEntry*next;}dictEntrykey用于保存key，val属性用来保存value，value可以是指针，uint64_t整数，也可以是int64_t整数。请注意，还有一个指向下一个哈希表节点的指针。我们知道哈希表最大的问题就是哈希冲突。如何解决哈希冲突有开放地址法和链地址法。这里使用链地址法。通过next指针，可以将多个哈希值相同的键值对连接在一起，解决哈希冲突。五、跳表1.概述跳表（skiplist）是一种有序的数据结构，在每个节点中维护多个指向其他节点的指针，从而达到快速访问节点的目的。跳转表是一种随机数据。跳表有序地保存层次链表中的元素，其效率可与平衡树相媲美。查找、删除、添加等操作都可以在对数期望时间内完成。而且相比平衡树，跳表的实现要简单直观得多。Redis只在两个地方使用了跳表，一个是实现有序的集合键，另一个是作为集群节点中的内部数据结构。Redis中跳表节点定义如下：typedefstructzskiplistNode{//layerstructzskiplistLevel{//forwardpointerstructzskiplistNode*forward;//spanunsignedintspan;}level[];//backwardpointerstructzskiplistNode*backward;//scoredoublescore;//memberObjectrobj*obj;}zskiplistNode多个跳表节点构成一个跳表：typedefstructzskiplist{//表头节点和表尾节点structzskiplistNode*header,*tail;//表中节??点个数unsignedlonglength;//个数oflayersinthetable最大节点的层数intlevel;}zskiplist;头指针和尾指针分别指向跳表的头节点和尾节点；length属性记录节点数；level属性记录层数最高的点的层数；展示了完整的跳表和单个节点的详细结构图：2.特点跳表有以下特点：由很多层组成，每一层都是一个有序链表。最底层（Level1）的链表包含所有元素，如果一个元素出现在Leveli的链表中，那么它也会出现在Leveli下面的链表中。每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下一级元素。六、整数集合1、概述《Redis 设计与实现》定义整数集合如下：》整数集合是集合构造的底层实现之一，当一个集合只包含整数，且这个集合中的元素个数不大时，redis会使用整型集合intset作为集合的底层实现。”我们可以这样理解整数集，它其实是一个特殊的集合，里面存放的数据只能是整数，数据量不能太大。typedefstructintset{//编码方式uint32_tencoding;//集合包含的元素个数uint32_tlength;//数组int8_tcontents[];}intset;我们观察一个完整的整数集合结构图：encoding：用于定义整数集合的编码方法length：用于记录整数集合中的变量个数contents：用于存储元素数组，虽然我们可以在intset定义数组为int8_t的数据结构图，但实际上数组中存储的元素类型取决于encoding2，特点Integercollection是集合的底层实现之一。整数集合的底层实现是一个数组。该数组以有序且不重复的格式存储集合元素。必要时，程序会根据新添加的元素类型更改数组。类型升级操作为整数集合带来了操作上的灵活性，并尽可能节省了内存。2.整数集合只支持升级操作，不支持降级操作。的底层实现之一。当一个列表键只包含少量的列表项，并且每个列表项要么是一个小整数，要么是一个比较短的字符串，那么Redis会使用一个压缩列表作为列表键的底层实现。一个压缩列表的组成如下： zlbytes：用于记录整个压缩列表占用内存的字节数zltail：记录列表结束节点到起始地址之间的字节数压缩列表zllen：记录压缩列表中包含的字节数节点数entryX：表示列表中包含的每个节点zlend：用于标记压缩列表的结束2.特点压缩列表是一种顺序数据结构为节省内存而开发的压缩列表作为列表键和哈希键的底层实现之一，压缩列表可以包含多个节点，每个节点可以保存一个字节数组或整数值。向压缩列表中添加新节点可能会导致链更新操作。
