Redis常用数据类型对应的数据结构

redis常用的数据类型共有五种：

此文章为极客时间《数据结构与算法之美》的笔记，图片来自本课程。

字符串：

底层就是字符串

列表（list）：

这种数据类型对应两种实现方法，一种是压缩列表（ziplist），另一种是双向循环链表。

压缩列表（ziplist）：

体需要同时满足下面两个条件：

1. 列表中保存的单个数据（有可能是字符串类型的）小于 64 字节；
2. 列表中数据个数少于 512 个。

我们需要用最大长度的字符串大小作为元素的大小（假设是 20 个字节）。那当我们存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。

压缩列表这种存储结构，一方面比较节省内存，另一方面可以支持不同类型数据的存储。而且，因为数据存储在一片连续的内存空间（相当于数组），通过键来获取值为列表类型的数据，读取的效率也非常高。

当列表中存储的数据量比较大的时候就用双向链表实现List

字典（hash）：

字典类型用来存储一组数据对。每个数据对又包含键值两部分。字典类型也有两种实现方式。一种是我们刚刚讲到的压缩列表，另一种是散列表。

当存储的数据量比较小的情况下，Redis 才使用压缩列表来实现字典类型。需要满足两个条件(同List)。

Redis 还支持散列表的动态扩容、缩容。

当装载因子大于 1 的时候，Redis 会触发扩容，将散列表扩大为原来大小的 2 倍左右。

当装载因子小于 0.1 的时候，Redis 就会触发缩容，缩小为字典中数据个数的大约 2 倍大小。

字典（hash）：

集合这种数据类型用来存储一组不重复的数据。这种数据类型也有两种实现方法，一种是基于有序数组，另一种是基于散列表。

当要存储的数据，同时满足下面这样两个条件的时候，Redis 就采用有序数组，来实现集合这种数据类型。

1. 存储的数据都是整数；
2. 存储的数据元素个数不超过 512 个。
   其余为散列表。

有序集合（sortedset）：

一般来说是跳表+散列表：
这样可以做到O（1）通过ID找到对象。
添加、修改对象复杂度为O(logn)。

有序集合也并不仅仅只有跳表这一种实现方式。当数据量比较小的时候，Redis 会用压缩列表来实现有序集合。条件是：
1. 所有数据的大小都要小于 64 字节；
2. 元素个数要小于 128 个。