基本数据类型

String（字符串）、List（列表）、Hash（哈希）、Set（集合）和Sorted Set（有序集合）

底层数据结构

动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组

可以看到String类型下只要一种数据结构，但是List（列表）、Hash（哈希）、Set（集合）和Sorted Set（有序集合）每个都有2种数据结构，所以也被称之为集合类型。它们均是一个键对应了一个集合的数据

Redis中KV如何保存

1. 一个哈希表来保存所有键值对。

   一个哈希表，也是一个数组，数组的每个元素称为一个哈希桶。一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。
   但是哈希表中保存对键值对并不是真实保存对数据，而是指向数据的指针。这样一来不管是字符串还是聚合类型查找所需的时间复杂度均是O(1)。

2. 哈希冲突

   一般来说，哈希桶的个数通常要少于key的数量，这也就是说，难免会有一些key的哈希值对应到了同一个哈希桶中。
   当数据量越来越大时，哈希冲突是不可避免的问题。
   Redis解决哈希冲突的方式，就是链式哈希。就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。
   
   使用链式哈希也有一定当缺陷，就是当链表越来越长时，查询速度也会极具下降。

3. Rehash

   为了解决上述带来当问题，Redis会对哈希表做rehash操作。rehash也就是增加现有的哈希桶数量，让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。
   Redis默认使用了两个全局哈希表：哈希表1和哈希表2。一开始，当你刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，Redis开始执行rehash，这个过程分为三步：

   • 给哈希表2分配更大的空间，例如是当前哈希表1大小的两倍；
   • 把哈希表1中的数据重新映射并拷贝到哈希表2中；
   • 释放哈希表1的空间。
     这样就完成了从哈希表1切换到哈希表2，用增大的哈希表2保存更多数据，而原来的哈希表1留作下一次rehash扩容备用。

   ---

   但是如果一次性拷贝全部数据会带来线程阻塞，这样就无法正常提供服务了。所以redis采取了渐进式rehash。也就是当请求进来时，从哈希表1中依次把这个哈希桶链表下的元素复制到哈希表2中（一个请求一次）。
   
   对于String类型来说，找到哈希桶就能直接增删改查了，所以，哈希表的O(1)操作复杂度也就是它的复杂度了。
   但是，对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。

4. 集合数据操作效率

   集合数据中到数据结构主要有5种：双向链表、压缩列表、哈希表、跳表和整数数组
   和String类型不同，一个集合类型的值，第一步是通过全局哈希表找到对应的哈希桶位置，第二步是在集合中再增删改查。
   哈希表就是数组加链表，整数数组和双向链表也很常见，它们的操作特征都是顺序读写，也就是通过数组下标或者链表的指针逐个元素访问，操作复杂度基本是O(N)，
   压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段zlbytes(列表长度)、zltail(列表尾的偏移量)和zllen(列表中的entry个数)，压缩列表在表尾还有一个zlend，表示列表结束。
   在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是O(1)。而查找其他元素时，只能逐个查找，复杂度就是O(N)了。
   

   有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，跳表的查找复杂度为O(logN)。
   

5. 数据结构时间复杂度

6. 不同操作的复杂度

集合类型的操作类型很多，有读写单个集合元素的，例如HGET、HSET，也有操作多个元素的，例如SADD，还有对整个集合进行遍历操作的，例如SMEMBERS。这么多操作，它们的复杂度也各不相同。而复杂度的高低又是选择集合类型的重要依据。

第一，单元素操作，是指每一种集合类型对单个数据实现的增删改查操作。例如，Hash类型的HGET、HSET和HDEL，Set类型的SADD、SREM、SRANDMEMBER等。这些操作的复杂度由集合采用的数据结构决定，例如，HGET、HSET和HDEL是对哈希表做操作，所以它们的复杂度都是O(1)；Set类型用哈希表作为底层数据结构时，它的SADD、SREM、SRANDMEMBER复杂度也是O(1)。

这里，有个地方你需要注意一下，集合类型支持同时对多个元素进行增删改查，例如Hash类型的HMGET和HMSET，Set类型的SADD也支持同时增加多个元素。此时，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。例如，HMSET增加M个元素时，复杂度就从O(1)变成O(M)了。

第二，范围操作，是指集合类型中的遍历操作，可以返回集合中的所有数据，比如Hash类型的HGETALL和Set类型的SMEMBERS，或者返回一个范围内的部分数据，比如List类型的LRANGE和ZSet类型的ZRANGE。这类操作的复杂度一般是O(N)，比较耗时，我们应该尽量避免。

不过，Redis从2.8版本开始提供了SCAN系列操作（包括HSCAN，SSCAN和ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。这样一来，相比于HGETALL、SMEMBERS这类操作来说，就避免了一次性返回所有元素而导致的Redis阻塞。

第三，统计操作，是指集合类型对集合中所有元素个数的记录，例如LLEN和SCARD。这类操作复杂度只有O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计，因此可以高效地完成相关操作。

第四，例外情况，是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于List类型的LPOP、RPOP、LPUSH、RPUSH这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有O(1)，可以实现快速操作。

Redis之所以能快速操作键值对，一方面是因为O(1)复杂度的哈希表被广泛使用，包括String、Hash和Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set也采用了O(logN)复杂度的跳表。不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是O(N)。这里，我的建议是：用其他命令来替代，例如可以用SCAN来代替，避免在Redis内部产生费时的全集合遍历操作。
当然，我们不能忘了复杂度较高的List类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是O(N)。因此，我的建议是：因地制宜地使用List类型。例如，既然它的POP/PUSH效率很高，那么就将它主要用于FIFO队列场景，而不是作为一个可以随机读写的集合。