redis灵魂拷问：聊一聊redis底层数据结构

redis能具有很好的性能表现，一个重要的原因就是redis底层的数据结构的使用非常巧妙，今天，我们来聊一聊这些数据结构。

基本数据类型和数据结构对应

我们知道，redis有5种数据类型，包括字符串、列表、集合、有序集合和字典。同时redis底层的数据结构有6种，包括动态字符串、双向链表、压缩列表(ziplist)、hash表、跳表(skip list)和整数数组。

下面我们就看一下对应关系：

1.毋庸置疑，字符串类型使用的底层数据结构就是动态字符串。

2.关于列表,如果同时满足下面条件，就使用压缩列表，否则使用双向链表。

列表中单个元素小于64字节

列表中元素个数少于 512

3.关于集合，如果同时满足下面条件，就使用有序整数数组，否则使用hash表。

集合中元素都是整数类型

集合中元素个数不超过512

4.关于有序集合，如果同时满足下面2个条件，就使用压缩列表，否则使用跳表。

集合中元素都小于64字节

集合中元素个数小于128个

注意：有序集合还有一个hash表用于保存集合中元素的分数，做ZSCORE操作时，查询的就是这个hash表，所以效率很高。看下t_zset.c文件中这段注释：

* The elements are added to a hash table mapping Redis objects to scores. * At the same time the elements are added to a skip list mapping scores * to Redis objects (so objects are sorted by scores in this "view").

5.关于字典类型，如果同时满足下面2个条件，就使用压缩列表，否则使用hash表。

字典中每个entry的key/value都小于64字节

字典中元素个数小于512个

关于压缩列表

压缩列表并不是基础的数据结构，而是redis自己实现的，压缩列表跟数组相似，在内存中也是一块儿连续的内存空间，结构如下：

可以看到，在这块连续内存空间中，表头有3个字段，zlbytes表示压缩列表长度，zltail表示表尾的偏移量，zllen则表示列表中元素的个数。所以，压缩列表时间复杂度跟数组一样，都是o(n)。它的优势是实现了压缩存储。

关于hash表

hash表这种数据结构我们并不陌生，尤其是我们java程序员，HashMap可以说是面试的高频考题。其实redis中的hash表思想跟java中HashMap非常相似，我们一起看一下。

1.全局hash表

大家知道hash是时间复杂度最低的数据结构，复杂度是o(1), 底层使用一个数据存放hash桶。redis为了提高查询效率，使用了一个全局hash表，支持快速查询，而hash的key和value保存了指向实际key和value的指针*key和*value。

2.hash冲突

redis处理hash冲突的方法使用的是链表法，即如果2个key的hashcode一样，则在同一个hash桶中用一个链表组织起来，链表查找的时间复杂度是o(n),所以当hash桶中的元素越来越多时，查找性能会下降。这时redis就会做rehash。

3.rehash操作

redis会申请一个新的hash表，大小一般是当前hash的2倍，然后把就hash表的元素拷贝到新的hash表中，之后释放就hash表的空间。跟java中HashMap不一样的是，redis是单线程的，所以不用考虑并发问题。

当然，如果redis一次性拷贝这么多的元素，肯定造成线程阻塞，访问效率急剧下滑。所以，redis使用了渐进式的拷贝，就是每当访问一个entry时，顺带把这个entry拷贝到新的hash表中。

关于跳表

上面我们讲了，redis把所有的元素都组织在一个hash表中，所以对于字符串类型，查找效率直接就是o(1),非常快。但是通过key查找到对应的value后，对于value是压缩列表、整形数组、双向链表的情况，时间复杂度都是o(n),性能还是比较差的。为了提高性能，redis引入了跳表这种数据结构。

跳表这种数据结构，结构看起来跟B+树非常像，见下图：

下面是一颗B+树：

下面是一个跳表：

上面的跳表第一层是一级索引，第二层是二级索引。从上图中看出，如果我们不加索引，查找10这个数字需要查询10次，使用了二级索引，查找10这个数字需要5次，而使用一级索引，需要查询3次。跳表插入、删除、查询的时间复杂度是o(logN)，效率还是很高的。但是跳表需要存储额外的索引节点，会增加额外的空间开销，所以也是空间换时间的一种数据结构。

总结

了解了redis底层的数据结构，我们使用的时候也就心里有数了。

对于redis的list数据类型，它用到了压缩列表和双向链表，时间复杂度是o(n)，我们做随机读写是不太合适的，但是pop和push效率高，作为队列是很好的选择。

数组和压缩列表虽然查询复杂度高，但是都是连续的内存空间，对内存存储和缓存还是非常友好的。

最后，个人对redis理解有限，欢迎大佬们批评指正。