集大成者Redis
最后更新于
这有帮助吗？
最后更新于
这有帮助吗？
Redis的快主要表现在，它接受到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。
Redis是内存数据库，所有操作都是在内存中完成，内存的访问速度本身就很快
Redis中的键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，高效的数据结构是Redis快速处理数据的基础
底层数据结构共6种：
简单动态字符串
双向链表
压缩列表
哈希表
跳表
整数数组
从上图可以看出，String类型的底层实现只有一种数据结构，就是简单动态字符串，List、Hash、Set、Sorted Set底层都有两种实现结构，它们的特点是一个键对应了一个集合的数据，这些数据结构都是值的底层实现。
为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。
一个哈希表其实就是一个数组，数组的每个元素称为一个哈希桶，所以一个哈希表由多个哈希桶组成，每个哈希桶中保持了键值对数据。哈希桶中实际上并不保存值本身，而是指向具体值的指针。
如下图所示，哈希桶中的entry元素中保存了*key和*value指针，分别指向了实际的键和值，这样即使值是一个集合，也可以通过*value指针被查找到。
这个哈希表中保存了所有的键值对，称为全局哈希表，有了它只需要O(1)的时间复杂度来快速查找到键值对。
某一时刻，可能哈希表的操作变慢了，因为存在哈希冲突问题和refresh可能带来操作阻塞。
随着数据量的增加，哈希冲突不可避免，Redis使用链表法（同一个桶中多个元素用一个链表来保存）来解决冲突。
如上图所示，entry1、entry2、entry3都需要保存在哈希桶3中，导致了哈希冲突，因此使用*next指针来链接它们。
哈希冲突链上的元素只能通过指针逐一查找来操作，随着数据的增大，冲突变多，链表过长，进而导致这个链表上元素的查找耗时长，效率低下。
为了解决链表过长导致查找效率低下这个问题，Redis对哈希表做refresh操作（增加现有桶的数量），让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中元素数量，减少单个桶中的冲突。
为了使refresh操作更高效，Redis默认使用两个全局哈希表（哈希表1和哈希表2）：
刚插入数据时，默认使用哈希表1，此时哈希表2并没有被分配空间
随着数量逐步增多，Redis开始执行refresh
给哈希表2分配更大空间（哈希表1的2倍）
把哈希表1中的数据重新映射并拷贝到哈希表2中（这里涉及大量数据拷贝，优化：渐进式，每处理一个请求，从哈希表1的第一个索引位置开始，将所有entry拷贝到哈希表2中）
释放哈希表1的空间
refresh中第二步的优化操作，如上图所示，巧妙的将一次性大量拷贝的开销，分摊到了多次处理请求的过程中。
Redis的键和值是通过哈希表组织的：
String类型的数据，找到哈希桶就能直接增删改查，操作复杂度O(1)
集合类型的数据
通过全局哈希表查找到对应的哈希桶位置
在集合中再增删改查
集合类型的数据：
操作效率与集合底层数据结构有关，使用哈希表实现的集合要比使用链表实现的集合访问效率高
操作效率与操作本身的执行特点有关，读写一个元素的操作要比读写所有元素的效率高
总共有5种底层的数据结构：
数据结构
操作特征
操作复杂度
整数数组
顺序读写，通过下标访问
O(n)
双向链表
顺序读写，通过指针逐个访问
O(n)
哈希表
通过计算哈希值访问
O(1)
压缩列表
可快速定位头尾
O(n)
跳表
通过多级索引访问
O(logn)
类似数据，数组中每一个元素都对应保存一个数据，不同点在于表头有zlbytes（列表长度）、zktail（列表尾的偏移量）、zllen（类别中entry个数），在列表尾部zlend（列表结束符）。
在压缩列表中：
查找第一个和最后一个元素：通过表头三个字段和长度直接定位，时间复杂度O(1)
查找其他元素：逐个查找，时间复杂度O(n)
有序链表只能逐一查找元素，导致操作缓慢，跳表在链表的基础上，增加多级索引，通过索引位置的几个跳转，实现数据的快速定位，时间复杂度O(logn)。
集合类型的操作很多：
读写单个集合元素：HGET、HSET
操作多个元素：SADD
对整个集合进行遍历：SMEMBERS
单元素操作是基础，范围操作非常耗时，统计操作通常高效、例外情况只有几个。
每一种集合类型对单个数据实现的增删改查操作：
Hash类型的HGET、HSET、HDEL：O(1)
Set类型的SADD、SREM、SRANDMEMBR：O(1)
操作的复杂度由集合采用的数据结构决定。
集合类型支持同时对多个元素进行增删改查，此时时间复杂度由当元素操作的时间复杂度和元素个数决定：
Hash类型的HMGET、HMSEZT：O(m)，同时操作m个元素
Set类型的SADD
集合类型中的遍历操作，可以返回集合中所有数据：
Hash类型的HGETALL
Set类型的SMEMBERS
也可以返回一个范围内的部分数据：
List类型的LRANGE：O(n)
ZSet类型的ZRANGE：O(n)
2.8版本，增加HSCAN操作，渐进式遍历，避免了一次性返回所有元素导致Redis阻塞。
集合类型对集合中所有元素个数的记录。例如LLEN和SCARD，时间复杂度O(1)，因为当集合类型采用压缩列表、双向链表、整数数组时，这些数据结构中会专门记录元素的个数。
某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。
对于List类型的LPOP、RPOP、LPUSH、RPUSH操作时在列表的头尾进行增删元素，通过偏移量直接定位，时间复杂度是O(1)。
