相关资料下载：http://www.bjpowernode.com/?cnblogs

1、redis基础

1）redis 中的数据类型有哪些？

Redis 有 5 种基础数据结构，分别为：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合)。

Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)，这点让人非常意外。 当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。

Redis 的哈希相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值NULL。 当集合中最后一个元素移除之后，数据结构自动删除，内存被回收。

zset 类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。

2）为什么说redis能够快速执行

• 绝大部分请求是纯粹的内存操作（非常快速）
• 采用单线程,避免了不必要的上下文切换和竞争条件
• 非阻塞IO - IO多路复用

2、Redis中的五种数据结构

1）string (字符串)

redis是使用C语言开发，但C中并没有字符串类型，只能使用指针或符数组的形式表示一个字符串，所以redis设计了一种简单动态字符串(SDS[Simple Dynamic String])作为底实现：

定义SDS对象，此对象中包含三个属性：

1. len buf中已经占有的长度(表示此字符串的实际长度)
2. free buf中未使用的缓冲区长度
3. buf[] 实际保存字符串数据的地方

所以取字符串的长度的时间复杂度为O(1)，另，buf[]中依然采用了C语言的以\0结尾可以直接使用C语言的部分标准C字符串库函数。

空间分配原则：当len小于IMB（1024*1024）时增加字符串分配空间大小为原来的2倍，当len大于等于1M时每次分配 额外多分配1M的空间。

由此可以得出以下特性：

• redis为字符分配空间的次数是小于等于字符串的长度N，而原C语言中的分配原则必为N。降低了分配次数提高了追加速度，代价就是多占用一些内存空间，且这些空间不会自动释放。
• 二进制安全的
• 高效的计算字符串长度(时间复杂度为O(1))
• 高效的追加字符串操作。

2）list (列表)

redis对键表的结构支持使得它在键值存储的世界中独树一帜，一个列表结构可以有序地存储多个字符串，拥有例如：lpush lpop rpush rpop等等操作命令。在3.2版本之前，列表是使用ziplist和linkedlist实现的，在这些老版本中，当列表对象同时满足以下两个条件时，列表对象使用ziplist编码：

• 列表对象保存的所有字符串元素的长度都小于64字节
• 列表对象保存的元素数量小于512个
• 当有任一条件 不满足时将会进行一次转码，使用linkedlist。

而在3.2版本之后，重新引入了一个quicklist的数据结构，列表的底层都是由quicklist实现的，它结合了ziplist和linkedlist的优点。按照原文的解释这种数据结构是【A doubly linked list of ziplists】意思就是一个由ziplist组成的双向链表。那么这两种数据结构怎么样结合的呢？

3）ziplist的结构

由表头和N个entry节点和压缩列表尾部标识符zlend组成的一个连续的内存块。然后通过一系列的编码规则，提高内存的利用率，主要用于存储整数和比较短的字符串。可以看出在插入和删除元素的时候，都需要对内存进行一次扩展或缩减，还要进行部分数据的移动操作，这样会造成更新效率低下的情况。

4）linkedlist的结构

意思为一个双向链表，和普通的链表定义相同，每个entry包含向前向后的指针，当插入或删除元素的时候，只需要对此元素前后指针操作即可。所以插入和删除效率很高。但查询的效率却是O(n)[n为元素的个数]。

了解了上面的这两种数据结构，我们再来看看上面说的“ziplist组成的双向链表”是什么意思？

实际上，它整体宏观上就是一个链表结构，只不过每个节点都是以压缩列表ziplist的结构保存着数据，而每个ziplist又可以包含多个entry。也可以说一个quicklist节点保存的是一片数据，而不是一个数据。

总结：

1、整体上quicklist就是一个双向链表结构，和普通的链表操作一样，插入删除效率很高，但查询的效率却是O(n)。不过，这样的链表访问两端的元素的时间复杂度却是O(1)。所以，对list的操作多数都是poll和push。

2、每个quicklist节点就是一个ziplist，具备压缩列表的特性。

出　　处：https://www.cnblogs.com/linkeke/p/15723896.html