简要介绍33558www.Sina.com/RedisRedis种数据结构分析应用场景分析总结
对于Redis redis，它是一个用开源c语言编写的kv存储系统，是一个非常快的非关系型远程内存数据库。 它支持五种类型的数据结构： String、List、Set、Zset和hash。 此外，通过复制、持久化和客户端分片等功能，用户可以轻松地将redis扩展到能够处理数百GB数据和每秒数百万次请求的系统。 目前支持多种语言的api，用户友好。
redis还包括事务、LUA脚本和复制等功能，有两种方法：每隔一段时间将数据导入磁盘(快照模式)和将命令添加到日志(AOF模式) 如果只想用作高效的内存数据库，也可以关闭持久化功能。 哨兵(sentinel )和自动分区制(Cuuster )方式可以提高redis服务器的高可用性。
与关系数据库相比，redis命令请求不需要由查询分析器或查询优化程序处理，也避免了更新数据时发生的诸如随机读/写之类的低速操作。 直接读写存储器内的数据，数据以一定的数据结构保存。 所以那个速度很快。
五种数据结构字符串(String )与其他编程语言和其他键值存储提供的字符串非常相似。 关键帧(key )------值(value ) )字符串格式)、字符串具有get set del和自增加和自减少操作等操作命令。 redis是用c语言开发的，但c没有字符串类型，只能以指针或字符数组的形式表示一个字符串。 因此，redis以简单动态字符串SDS (简单动态字符串)为基础实现。
定义SDS对象。 此对象具有三个属性：
len buf已经占用的长度(表示此字符串的实际长度) free buf中未使用的缓冲区长度buf )字符串数据实际保存的位置，因此取字符串长度的时间复杂度为o )1)。 另外，buf ) )中，仍然采用了可以直接使用c语言的c语言的标准c字符串库函数的一部分。
空间分配原则：如果len小于IMB(1024*1024 )，则将字符串分配空间的大小增加一倍；如果len大于或等于1M，则每次分配额外的1M空间。
这提供了以下特性：
redis给文字分配区域的次数在字符串的长度n以下，用原来的c语言分配的原则必须是n。 减少分配次数可以提高附加速度，占用大量内存空间，并且不会自动释放这些空间。 二进制安全高效的字符串长度计算(时间复杂度为o )1) )高效的字符串添加操作。
“列表”(List ) redis支持关键帧表的结构，因此可以在存储关键帧值的世界中具有自己的特征。 列表结构可以有规律地存储具有操作命令(例如lpush lpop rpush rpop )的多个字符串。 在3.2版之前，列表是使用ziplist和linkedlist实现的。 在这些早期版本中，如果列表对象同时满足以下两个条件，则列表对象使用ziplist编码：
如果存储在列表对象中的所有字符串元素的长度都小于64字节，并且存储在列表对象中的元素数小于512个，则使用链接列表进行转码。
从3.2版开始，重新引入了快速列表数据结构。 所有列表的基础都是快速列表，它结合了zip列表和链接列表的优点。 根据原文解释，该数据结构意味着由【双链路列表】zip列表组成的双向链表。 那么，这两种数据结构是如何结合起来的呢？
本章主要内容
由标头、n个入口节点和压缩列表末尾标识符zlend组成的连续内存块。 然后，通过一系列编码规则提高内存利用率，主要用于存储整数和相对短的字符串。 可以看到，在插入和删除元素时，需要扩展或缩小内存一次，并执行某些数据移动操作，这样会降低更新效率。
本文详细介绍了ziplist的结构。
3359 blog.csdn.net/yellow river 007/article/details/79021049
ziplist的结构
表示双向链表，与普通链表的定义相同。 每个entry都包含一个指向前的指针，在插入或删除元素时，只需对该元素执行指向前后的指针操作。 所以插入和删除很有效率。 但是，查询的效率是o(n ) [n是要素的个数]。
在理解上述两种数据结构的基础上，让我们来看看上述“使用ziplist的双向链表”的含义。 实际上，整体上宏观上是链表结构。 但是，每个节点都以压缩列表ziplist的结构存储数据，并且每个ziplist可以包含多个条目。 也可以说quicklist节点存储的是一张数据，而不是数据。 总结：
快速列表总体上是双向链表结构，与普通链表操作一样，插入删除效率高，但查询效率为o(n )。 但是，这种链表访问两端元素的时间复杂度是o(1)
)。所以，对list的操作多数都是poll和push。每个quicklist节点就是一个ziplist，具备压缩列表的特性。在redis.conf配置文件中，有两个参数可以优化列表：
list-max-ziplist-size 表示每个quicklistNode的字节大小。默认为-2 表示8KBlist-compress-depth 表示quicklistNode节点是否要压缩。默认是0 表示不压缩 哈希(hash)redis的散列可以存储多个键 值 对之间的映射，散列存储的值既可以是字符串又可以是数字值，并且用户同样可以对散列存储的数字值执行自增操作或者自减操作。散列可以看作是一个文档或关系数据库里的一行。hash底层的数据结构实现有两种：
一种是ziplist，上面已经提到过。当存储的数据超过配置的阀值时就是转用hashtable的结构。这种转换比较消耗性能，所以应该尽量避免这种转换操作。同时满足以下两个条件时才会使用这种结构： 当键的个数小于hash-max-ziplist-entries（默认512）当所有值都小于hash-max-ziplist-value（默认64）另一种就是hashtable。这种结构的时间复杂度为O(1)，但是会消耗比较多的内存空间。集合(Set)
redis的集合和列表都可以存储多个字符串，它们之间的不同在于，列表可以存储多个相同的字符串，而集合则通过使用散列表（hashtable）来保证自已存储的每个字符串都是各不相同的(这些散列表只有键，但没有与键相关联的值)，redis中的集合是无序的。还可能存在另一种集合，那就是intset，它是用于存储整数的有序集合，里面存放同一类型的整数。共有三种整数：int16_t、int32_t、int64_t。查找的时间复杂度为O(logN)，但是插入的时候，有可能会涉及到升级（比如：原来是int16_t的集合，当插入int32_t的整数的时候就会为每个元素升级为int32_t）这时候会对内存重新分配，所以此时的时间复杂度就是O(N)级别的了。注意：intset只支持升级不支持降级操作。
intset在redis.conf中也有一个配置参数set-max-intset-entries默认值为512。表示如果entry的个数小于此值，则可以编码成REDIS_ENCODING_INTSET类型存储，节约内存。否则采用dict的形式存储。
有序集合(zset)
有序集合和散列一样，都用于存储键值对：有序集合的键被称为成员（member),每个成员都是各不相同的。有序集合的值则被称为分值（score），分值必须为浮点数。有序集合是redis里面唯一一个既可以根据成员访问元素(这一点和散列一样),又可以根据分值以及分值的排列顺序访问元素的结构。它的存储方式也有两种：
是ziplist结构。与上面的hash中的ziplist类似，member和score顺序存放并按score的顺序排列
另一种是skiplist与dict的结合。skiplist是一种跳跃表结构，用于有序集合中快速查找，大多数情况下它的效率与平衡树差不多，但比平衡树实现简单。redis的作者对普通的跳跃表进行了修改，包括添加spantailbackward指针、score的值可重复这些设计，从而实现排序功能和反向遍历的功能。
一般跳跃表的实现，主要包含以下几个部分：
表头（head）：指向头节点表尾（tail）：指向尾节点节点（node）：实际保存的元素节点，每个节点可以有多层，层数是在创建此节点的时候随机生成的一个数值，而且每一层都是一个指向后面某个节点的指针。层（level）：目前表内节点的最大层数长度（length）：节点的数量。跳跃表的遍历总是从高层开始，然后随着元素值范围的缩小，慢慢降低到低层。
跳跃表的实现原理可以参考：https://blog.csdn.net/Acceptedxukai/article/details/17333673
前面也说了，有序列表是使用skiplist和dict结合实现的，skiplist用来保障有序性和访问查找性能，dict就用来存储元素信息，并且dict的访问时间复杂度为O(1)。
应用场景 redis一般应用场景 缓存会话（单点登录）分布式锁，比如：使用setnx各种排行榜或计数器商品列表或用户基础数据列表等使用list作为消息对列秒杀，库存扣减等
五种类型的应用场景 String，redis对于KV的操作效率很高，可以直接用作计数器。例如，统计在线人数等等，另外string类型是二进制存储安全的，所以也可以使用它来存储图片，甚至是视频等。hash，存放键值对，一般可以用来存某个对象的基本属性信息，例如，用户信息，商品信息等，另外，由于hash的大小在小于配置的大小的时候使用的是ziplist结构，比较节约内存，所以针对大量的数据存储可以考虑使用hash来分段存储来达到压缩数据量，节约内存的目的，例如，对于大批量的商品对应的图片地址名称。比如：商品编码固定是10位，可以选取前7位做为hash的key,后三位作为field，图片地址作为value。这样每个hash表都不超过999个，只要把redis.conf中的hash-max-ziplist-entries改为1024，即可。list，列表类型，可以用于实现消息队列，也可以使用它提供的range命令，做分页查询功能。set，集合，整数的有序列表可以直接使用set。可以用作某些去重功能，例如用户名不能重复等，另外，还可以对集合进行交集，并集操作，来查找某些元素的共同点zset，有序集合，可以使用范围查找，排行榜功能或者topN功能。
总结
本章介绍了redis的五种数据结构和它们使用的底层存储原理，为了达到节省内存和快速访问的目的每种数据结构可能有两种存储和访问结构，在必要的时候会由一种结构转换成另一种结构，但这个转换的过程会消耗系统性能和内存空间的，所以在使用的过程中需要注意这些配置参数，开发中尽量避免达到这些峰值，使得redis能够持续的提供高效的服务。