java|冷知识（数据结构如何造就Redis的快（））程序人生|redis|数据结构|后端

作为一种键值数据库，为啥Redis能有这么突出的表现呢？一方面，这是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本身就很快。另一方面，这要归功于它的数据结构。键值对(key-value对)是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，高效的数据结构是Redis快速处理数据的基础。
Redis中的键的类型只能为String（字符串），值支持五种数据类型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Sorted Set（有序集合，也叫Zset）。键与值构成一个键值对，即key-value对，key-value对是Redis中数据存储的最小单位，因此Redis也被叫做Key-value数据库。
Redis怎样存储键值对为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对(key-vaue)。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。如果值是集合类型的话，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。这也就是说，不管值是String，还是集合类型，哈希桶中的元素都是指向它们的指针。
这里的哈希表与JDK是实现的HashMap基本相同，关于JDK中的HashMap是如何实现的，可参见彻底理解HashMap及LinkedHashMap，具体来说，Redis中的哈希表就是一个Entry数组，entry元素中保存了key和value指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过*value指针被查找到。如下图所示。

文章图片
Redis用一个哈希表保存了所有的键值对，这个哈希表被称为全局哈希表。哈希表的最大好处很明显，就是让我们可以用O(1)的时间复杂度来快速查找到键值对。
既然使用了哈希表，那么就哈希冲突与rehash就是不可避免的，那么Redis是如何解决的呢？对于哈希冲突，Redis采用的是链式哈希法，同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

文章图片
随着操作的不断执行，哈希表保存的键值对会逐渐地增多，哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，Redis会对哈希表作rehash操作。
为了使rehash操作更高效，Redis默认使用了两个全局哈希表：哈希表1和哈希表2。一开始，当你刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，Redis开始执行rehash，这个过程分为三步：

给哈希表2分配更大的空间，例如是当前哈希表 1 大小的两倍；
把哈希表1中的数据重新映射并拷贝到哈希表2中；
释放哈希表1的空间

以上过程看似简单，但是第二步涉及大量的数据拷贝，如果一次性把哈希表1中的数据都迁移完，会造成Redis线程阻塞，无法服务其他请求。此时，Redis就无法快速访问数据了。
为了避免这个问题，Redis采用了渐进式rehash的方案。
渐进式rehash 简单来说就是在第二步拷贝数据时，Redis仍然正常处理客户端请求，每处理一个请求时，从哈希表1中的第一个索引位置开始，将这个索引位置上的所有entries拷贝到哈希表2中；等处理下一个请求时，再顺带拷贝哈希表1中的下一个索引位置的entries。整个过程如下图所示。

文章图片
这样就把之前的一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。
其实，渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，Redis本身还会有一个定时任务在执行rehash，如果没有键值对操作时（即没有get/set操作），这个定时任务会周期性地（例如每100ms一次）搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。
对于值是String类型的键值对，找到哈希桶定位到了entry之后，就能直接对值进行操作了，所以，哈希表的O(1)查找时间复杂度也就是查找到最终value的时间复杂度了。但是如果键值对中的值是复杂的集合类型，即使找到了entry，拿到了*value指针，还要在集合中作进一步操作，接下来看下当键值对的值是复杂类型时，Redis是如何保证操作的高效率的。
Redis中“值”的数据结构 Redis中的值支持五种数据类型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Sorted Set（有序集合，也叫Zset）。其实这些只是 Redis键值对中值的数据的保存形式，只是Redis对这种保存形式的命名，与我们常说的字符串、链表、队列等数据结构不可以混为一谈。重点要关注它们的底层实现，它们的底层实现其实就是我们熟知的一些数据结构了。
简单来说，底层数据结构一共有6种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示。

文章图片
可以看到，String类型的底层实现只有一种数据结构，也就是简单动态字符串。而List、Hash、Set和 Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型。
6种底层数据结构中，哈希表和双向链表很常见，操作很简单。下面重点讨论下另外4种数据结构。
压缩列表压缩列表实际上类似于一个数组，是在数组的基础上进行改造的一种数据结构，首先我们了解下数组的结构，当我们创建一个数组时，通常向内存申请的都是一段连续的内存空间，然后申请的内存空间大小取决创建数组时指定的长度和存储数据类型，申请好的数组每一段存储元素的空间都是相同的，也正是这种连续相等的空间才能保证我们能根据数组下标查找到对应的下标元素。但数组的问题在于空间浪费，例如申请一个Long类型的数组，但实际存储的都是byte类型的数据，每个存储空间都浪费了内存。Redis的内存资源尤其珍贵，所以就有必要针对数组的空间浪费进行优化，这也就是压缩列表的初衷了。

文章图片
压缩列表是按实际的数据大小来分配数据空间的。如上图所示，给每个元素增加一个Length属性，在遍历节点之后就知道每个节点的长度(占用内存的大小)，就可以很容易地计算出下一个节点在内存中的位置。压缩列表在表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量和列表中的entry个数；压缩列表在表尾还有一个zlend，表示列表结束。在压缩列表中，如果要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是O(1)。而查找其他元素时，只能逐个查找，此时的复杂度是O(N) 。

文章图片
如上图，展示了一个总长为80字节，包含3个节点的压缩列表。如果我们有一个指向压缩列表起始地址的指针p，那么表尾节点的地址就是P+60。
Redis的List底层使用压缩列表本质上是将所有元素紧挨着存储，所以分配的是一块连续的内存空间，虽然数据结构本身没有时间复杂度的优势，但是这样节省空间而且也能避免一些内存碎片。
整数数组整数数组就是指保存整数数据类型的数组结构，其实通过理解压缩列表的设计意图后我们可以知道一件事情，就是在创建数组前指定存储的数据类型不会产生空间的浪费。不过虽然同样是整数，但是也会有占用大小的不同，就像Java中的int和long类型一样，他们虽然都是整数类型，但是实际占用的空间大小却不一样，而Redis里面也有这种整数类型的区别。
在Redis里面包含int8_t、int16_t、int32_t或者int64_t的整数值，几种不同类型的整数占用的空间大小也不一样int8_t、int16_t、int32_t、int64_t分别占用1字节、2字节、4字节、8字节。正因为这种区分所以就有了整数数组升级的概念。
假如我们初次保存的数据为int8_t的整数，那么创建数组的时候就指定了数组的每个元素空间大小为1字节的大小，但是如果后面要添加int16_t或int32_t、int64_t整数时，原来的int8_t整数数组的元素空间是无法容纳的，所以就必须对整数数组进行升级，保证新的元素可以正常的保存起来。

文章图片
整数数组最大的优点就是节省内存，因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N)。
动态字符串 Redis里采用的是SDS（Simple Dynamic String，简单动态字符串），作为Strig类型数据的存储结构，相比于传统字符串SSD具备两个特点，一是遍历比传统字符串快；二是SDS不会对数据添加任何结束标记，不损坏数据原本表达的意义。
SDS相对于传统字符串，它保存了字符串数据长度属性，所以在获取字符串值的时候，只需要通过字符串长度计算出实际存储值的内存地址位置，就可以直接获取数据，整个操作复杂度为O(1)，而传统的字符串必须逐个遍历数据，直到遇到一个结束标记符才能读取到数据，整个操作复杂度为O(N)。

文章图片
SDS不会对保存的数据进行任何添加标记，比如说传统字符串分割两个数据的边界就是通过某种符号(\0这样的标识)来作为数据的结束标记，而只要用到特殊标记那么就有可能损坏掉原本数据所表达的意义。比如下面这个这个案例中，本身数据中就有包含’\0’的内容，如果数据存储规则中也使用了’\0’作为数据结束标记的话，那么最终所获取的数据只有"Hello"。

文章图片
SDS保证保存进去的数据是什么样子，拿出的的数据就是什么样子。这种方式可以保证存储任何类型的数据都不会被修改、破损，也正是因为这种特性所以Redis里可以保存图片、音频、文字各种数据。
跳表(skiplist) 【java|冷知识（数据结构如何造就Redis的快（））】有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表，关于跳表的详细探讨，参见Redis为什么用跳表而不用平衡树这篇文章。
跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树。Redis 中的有序集合（Sorted Set）就是用跳表来实现的。查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。跳表的查找复杂度是O(logN)。例如下图所示，查找16，只需要遍历6个结点即可，相对于链表需要遍历的结点数量少了许多。

文章图片
Redis中的有序集合支持的核心操作主要有下面这几个：

插入一个数据；
删除一个数据；
查找一个数据；
按照区间查找数据（比如查找值在[100, 356]之间的数据）；
迭代输出有序序列。

文章图片
其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。对于按照区间查找数据这个操作，跳表可以做到O(logN) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。
skiplist与平衡树、哈希表的比较：

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到最小值之后，对第1层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目可用参数来调节（跳表在频繁插入删除过程中会通过某种策略维护两个索引结点之间的数据结点不过多和过少，类似于AVL树通过左旋右旋维护平衡性），每个节点包含的指针数目可以小于2，内存占用上比平衡树更有优势。
查找单个key，skiplist和平衡树的时间复杂度都为O(log N)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

对于为什么Redis使用skiplist而不用平衡树这个问题，Redis的作者antirez是这么说的

文章图片
他从内存占用、对范围查找的支持和实现难易程度这三个方面作了解释。
不同操作的复杂度现在可以按照查找的时间复杂度给这些数据结构分下类。

文章图片
集合类型的操作类型很多，有读写单个集合元素的，例如 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阻塞。
某些特殊情况，例如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于List类型的LPOP、RPOP、LPUSH、RPUSH这四个操作来说，在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有O(1)，可以实现快速操作。
Redis之所以能快速操作键值对，一方面是因为O(1)复杂度的哈希表被广泛使用，包括String、Hash和Set，它们的操作复杂基本由哈希表决定，另一方面，Sorted Set也采用了O(log N)复杂度的跳表。不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是O(N)。
当然，我们不能忘了复杂度较高的List类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是O(N)。因此要因地制宜地使用List类型。例如，既然它的POP/PUSH效率很高，那么就将它主要用于队列或栈场景，而不是作为一个可以随机读写的集合。