Redis基本数据类型

Redis基本数据类型：String（字符串）、List（列表）、Set（集合）、ZSet（排序集合）、Hash（哈希）

底层数据结构有：动态字符串、 双向链表、压缩列表、跳表、整数数组

Redis全局哈希键值结构

键和值用了什么结构

为了实现从键到值的快速访问，Redis使用一个全局哈希来保存所有的key，value。一个哈希表就是一个数组，数组中每个元素称为一个哈希桶。

在下图中可以看到，哈希桶中不管是String还是集合，entry元素都保存了 *key 和 *value指针，即时是一个集合也可以以O(1)的时间复杂度根据key查到。我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。

Redis全局表的rehash

Redis解决哈希冲突的方式是使用链式哈希，链式哈希 就是指 同一个哈希桶中的多个元素用一个链表来保存，他们之间依次用指针连接。

Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：

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

渐进式rehash

在第二步拷贝的时候，如果一次性把哈希表1中的数据全部拷贝到哈希表2中，则会造成线程阻塞。为避免你这个问题，redis采取了渐进式rehash。在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：

Redis底层数据结构

集合类型的底层数据结构主要有 5 种：整数数组、双向链表、哈希表、压缩列表和跳表。

压缩列表

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

如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

跳表

跳表：在链表的基础上，增加多级索引，通过索引位置的几个跳转，实现数组的快速定位

Redis进阶01-Redis底层数据结构