写在前面

在面试中关于redis经常被问到一个问题就是redis为什么快，本文就一起从其底层的数据结构实现来分析下，为什么快，哪些快，哪些慢，哪些操作会导致慢等，下面我们就开始吧！

1：为什么快？

从大的方面来说，主要有以下两点：

1：基于内存的操作，内存的读写速度非常高，大概在百万分之一秒的级别
2：底层的优秀数据结构的支持，这点最为重要

关于第一点，没有什么需要具体说明的，这是内存本身提供的天然优势，主要还是要分析2，底层数据结构的支持。

2：数据是怎么存储的？

我们知道redis是一种kv数据库，这种kv结构redis是使用哈希表 存储的，具体的数据存储在哈希桶中，其中哈希桶中entry结构是(*key,*value)的键值对，其中*key是指向具体key的指针，*value是指向具体值的指针，可能如下结构：

当有哈希冲突时通过链表解决冲突，可能像下图：

所以我们可以看到，当我们执行一个通过key查询value的操作时，找到value是很快的，时间复杂度是O(1)，更多的查询时间是消耗在从value中找到具体的我们需要的值了，所以，我们就需要具体来看下value都有哪些数据类型了，以及这些数据类型底层支持的数据结构是什么样的。

3：value数据类型以及底层数据结构

value的类型和底层数据结构关系如下图：

接下来我们看下具体每种数据结构。

3.1：简单动态字符串

TODO 补充简单动态字符串的具体实现

3.2：双向链表

双向链表是我们日常工作中非常常见的数据结构，有些类似于常用的交通工具火车，两侧都是车头，也都是车尾，参考下图：

3.3：压缩列表

压缩列表并不像数组，链表，哈希表等，是基础的数据结构，而是redis自创的一种数据结构赞创新精神！！！,有些类似于数组，但是数组中每个元素的长度是由数组中最大的那个元素长度决定的，如我们定义一个String数组，其中最大一个元素的数据长度是20字节，则其他每个元素占用内存长度都是20字节，虽然其实际的长度是小于20字节的，这就造成了内存空间的浪费，redis为了解决这个问题，就引入了压缩列表，假设我们有如下的数组：

该数组长度为5，其中索引位4的元素长度是10，所以总长度是40，但其实存储所有的元素只需要1+2+3+4+20=30，浪费了10个字节的内存空间，如果是使用压缩列表的话其结构如下：

格式是元素数，元素长度，元素，元素长度，元素。。。，其中通过每个元素长度我们就能知道下一个元素通过怎样的内存偏移量来获取了。此时的数据总长度是34，节省了6字节的内存空间。这里如果是最大元素要比其他元素长度大的多的话，则内存优化的效果会更加明显。

压缩列表数据查找，插入，删除的时间复杂度都是O(n)，所以对于底层数据结构是压缩列表的数据结构在使用上要格外小心，避免出现性能问题。

3.4：哈希表

参考数据结构之哈希算法 。

3.5：跳表

参考数据结构之跳表 。

查找，插入，删除的时间复杂度都是O(logn)，效率很好。

3.6：整数数组

用在哈希表中。

接下来我们再看下常用的操作的时间复杂度是怎样的，以此来看其快和慢。

4：常用操作分析

先来看下不同数据结构的时间复杂度。

我们通过redis提供的操作接口，命令 来分析下操作的时间复杂度。

4.1：String#get和set

127.0.0.1:6379> set name jack
OK
127.0.0.1:6379> get name
"jack"

set操作只需要将对应的kv设置到全局哈希表中，get操作从全局哈希表中获取的value值就是我们需要的目标值，并不需要额外的解析，所以二者操作的时间复杂度都是O(1)。

4.2：String#mget和mset

get和set的批量版本，m，即multi,假设批量的个数是M，则此二操作的时间复杂度是O(M)。

4.3：Hash#hget和hset

127.0.0.1:6379> hset myhash name "zhangsan"
(integer) 0     
127.0.0.1:6379> hget myhash name
"zhangsan"      

二者都是基于哈希表的操作，所以是常量时间复杂度O(1)。

4.4：Hash#hmget和hmset

hget好hset的批量版本，m，即multi，假设批量的个数是M，则此二操作的时间复杂度是O(M)。

4.5：Set#sadd

127.0.0.1:6379> sadd myset "aaa"
(integer) 1
127.0.0.1:6379> sadd myset "bbb"
(integer) 1

基于哈希的操作，时间复杂度为O(1)。

4.6：Set#srandmenber

随机返回一个元素。

127.0.0.1:6379> sadd myset "bbb"
(integer) 1
127.0.0.1:6379> SADD myset one two three
(integer) 3     
127.0.0.1:6379> srandmember myset
"three"
127.0.0.1:6379> srandmember myset
"aaa"
127.0.0.1:6379> srandmember myset
"two"

时间复杂度O(1)。

4.7：hash#hgetall

redis> HSET myhash field1 "Hello"
(integer) 1
redis> HSET myhash field2 "World"
(integer) 1
redis> HGETALL myhash
1) "field1"
2) "Hello"
3) "field2"
4) "World"

尽管是哈希结构，但是需要遍历，所以时间复杂度是O(n),实际工作中最好不要使用。

4.8：set#smembers

redis> SADD myset "Hello"
(integer) 1
redis> SADD myset "World"
(integer) 1
redis> SMEMBERS myset
1) "World"
2) "Hello"

尽管是哈希结构，但是需要遍历，所以时间复杂度是O(n),实际工作中最好不要使用。

最后我们可以通过下图来看下不同的时间复杂度和查询需要的时长的关系图：

其中除常量时间复杂度O(1)外，只有对数时间复杂度O(logn)随着数据量的增加，时间增长不是非常明显，其他的如线性时间复杂度O(n),数据量越大，性能下降的就非常厉害了，所以当某操作的时间复杂度是O(n)以及比起更加糟糕的时间复杂度时一定要格外注意，避免因为数据量过大出现性能问题。

写在后面

参考文章列表：

redis 命令手册 。

redis 数据结构之哈希算法 。

数据结构之跳表 。

数据结构之跳表 。