Redis底层数据结构详解_redis数据结构

Redis底层数据结构详解

我们知道Redis常用的数据结构有五种，String、List、Hash、Set、ZSet，其他的集中数据结构基本上也是用这五种实现的，那么，这五种是Redis提供给你的数据结构，这五种数据结构式怎么实现的，你知道么？底层的底层，你有了解过吗？

这些是五种数据结构底层使用的数据结构，我们可以看到，有很多底层使用了两种数据结构，比如set在元素较少，且都是数字的情况下会使用整数列表，数据增加会变成哈希表。那么这些底层的数据结构，你又了解多少呢？

这个问题我们先放一下，你有没有一个疑问，这些底层都有着不同的数据结构，那么redis整体的数据结构是什么呢？举个例子，我们现在有一个key对应的value是list类型的，对应的是一个双向链表，那么，我首先要找到这个key，才可以找到这个双向链表噻？

全局哈希表

其实，在redis中，是有一个大的哈希表的，所谓哈希表就是类似的长数组，上面每一个空间，我们都可以看做一个哈希桶。

每一个key经过Redis内部的hash算法之后都会算出一个位置，这个位置对应一个哈希桶。注意，这个过程可是很快的哈，O(1)的时间复杂度，因为只是计算出一个内存地址，直接寻址就可以了。然后这个key就存到了这个hash桶上面了，这个哈系桶上面保存的是引用，不是真实的对象，就好像哈希桶里面保存的是这个key家的地址（内存地址）。这样就可以用O(1)的时间复杂度完成查找操作了，因为用key去查找value的时候，只需要在经过依次hash能马上找到哈希桶，就能定位到这个键值对的内存地址了。

那么有一个问题，hash算法不能保证所有的key经过算法出来的值都不一样，就是会有哈希冲突的存在，就是两个key放到了同一个桶中，这可怎么办呢？

Redis使用了链表来解决这个问题，就是两个在一个桶中的元素，会用一个next指针连在一起，经过hash之后找到一个键值对之后，对比不是，根据next指针再找下一个比对即可。

那么当元素越来越多之后，一个哈希桶所对应的链表会越来越长，我们知道链表上的遍历时间复杂度是O(n)，会严重影响性能，Redis这种追求快的数据库是绝对不能够容忍的，那么要怎么处理，就是rehash操作。

rehash和渐进式rehash操作

redis会在内部从新建一个长度为原始长度2倍的空哈希表，然后原哈希表上的元素重新rehash到新的哈希表中去，然后我们使用新的哈希表即可。

那么，这样还是有问题，要知道redis中存储的数据可能是成百万上千万的，我们重新rehash一次未免太耗时了吧，因为redis中操作大部分是单线程的，这个过程可能会阻断其他操作很长时间，这是不能忍受的，那么要怎么处理呢。

redis是采用了渐进式rehash的操作，就是会有一个变量，指向第一个哈希桶，然后redis每执行一个添加key，删除key的类似命令，就顺便copy一个哈希桶中的数据到新的哈希表中去，这样溪水长流的操作，不会影响什么性能，直到所有的数据都被重新hash到新的哈希表中。

那么在这个过程中，当然再有写的操作，会直接把数据放到新的哈希表中，保证旧的肯定有copy完的时候，如果这段时间对数据库的操作较少，也没有关系，redis内部也有定时任务，每隔一段时间也会copy一次。

压缩表

压缩表是一种Redis开发用来节省内存的顺序性存储的表结构，我们知道数组这种数据结构，每一个空间的大小都是一样的，这样我们存储较小元素节点的时候就会造成内存的浪费，而压缩链表可以做到每一个元素的节点的大小都不一样。

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

跳表

关于跳表，我写了一篇专门的文章介绍，地址 https://yanghang.blog.csdn.net/article/details/116432604

最后附上Redis底层数据结构的查询时间复杂度

写在最后，推荐《Redis的设计与实践》这本书，还有蒋德钧的《Redis核心技术与实战》专栏。如果想系统的学习Redis的人，不妨看一下。