Redis是一个非常高效的键值（key-value）数据库，相对于MySQL这种关系型数据库，它没有那么复杂的查询需求，而仅仅是包含 “键” 和 “值” 两部分。
在Redis中，键的数据类型是字符串，值的数据类型有很多，最常用的数据类型有这样几种：字符串、列表、字典、集合、有序集合。
字符串你已经非常熟悉了，下面我们介绍剩下的集中数据类型，看看他们底层依赖了哪些数据结构。
列表（list）
列表支持存储一组数据，这种数据类型对应两种实现方法：一种是压缩列表（ziplist），另一种是双向循环链表。
压缩列表用于存储数据量较小的情况，要使用压缩列表，需要满足两个条件：
- 列表中的单个数据要小于 64 字节。
- 列表中的数据个数少于 512 个。
压缩列表.jpg
相比于数组，它的特点是节省了内存：
数组.jpg
同时，压缩列表可以支持不同类型数据的存储。而且它使用了连续的存储空间，读取效率非常高。
当然，由于压缩列表不是数组，所以无法实现使用数组下标随机访问的特性。由于 Redis 是 k - v 型数据库，所以这种设定也能够理解。
话说回 Redis 的链表，当数据量较大的时候，列表就要通过双向循环链表实现了。
在 Redis 中，额外定义了一个 list结构体 来组织链表的首、尾指针、长度信息等。这样，使用起来就会非常方便：
// 以下是C语言代码，因为Redis是用C语言实现的。
typedef struct listnode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list {
listNode *head;
listNode *tail;
unsigned long len;
// ....省略其他定义
} list;
个人认为，列表使用双向链表来实现，目的是通过首尾两个指针加速查找。
字典（hash）
字典用于存储一组数据对，每个数据对都包含键和值两个部分。字典类型也有两种实现方式：压缩列表 和 散列表。
同样，数据量较小的情况下，Redis 会使用压缩列表来实现。
当数据较大时，Redis 就使用散列表来实现字典类型。对于 Redis 实现的散列表，有以下特点：
- 使用拉链法处理散列冲突
- 当装载因子大于 1 的时候，进行扩容；小于 0.1 时，进行缩容。变化系数为 2
- 采用渐进式 扩容/缩容 策略
这里我其实不明白为什么要使用压缩列表存储字典。
集合（set）
集合用于存储一组不重复的数据。这种数据类型也有两种实现方法：有序数组 和 基于散列表
当数据较少时，使用有序数组进行存储，使用条件为：
- 存储的数据都是整数
- 存储的数据元素个数不超过 512 个
当不能同时满足这两个条件的时候，Redis 就使用散列表来存储集合中的数据。
我认为用有序数组实现集合是合适的，理由如下：
- 集合要求不重复，所以非常重要的一点就是判重，实现这个功能需要进行额外操作。目前来看，有两种较好的方法：用散列表计算 和 查找集合元素是否存在。
- 对于前者自不必多说，而对于后者，解决思路之一就是维护有序数组，使用二分查找加速查找。这样，在数据较少的时候，时间复杂度为 O(logn)，是非常快速的。
- 数组被诟病的一大原因是增删操作会导致大量数据搬移，所以当数据较多时，Redis 选择使用散列表实现集合。
有序集合（sortedset）
同样，有序集合在数据较少时使用有序列表实现。
数据较多的时候，使用跳表实现。
相比 B+ 树，跳表对查询效率和空间占用可以做到动态更新，可以更方便地配置资源。
数据持久化
Redis 是内存数据库，但是依然可以实现硬盘存储。这可以看作笼统的数据持久化。
数据持久化有两种场景：数据结构的持久化 和 对象的持久化。
Redis是数据库，所以我们要解决的是数据结构的持久化的问题。解决这种问题，有两种思路：
- 清除原有的存储结构，只将数据存储。当要还原数据结构的时候，再讲数据重新组织成原来的数据结构。Redis 采用的就是这种方法
- 第二种思路，保留原有的存储格式，将整个数据结构的组织形式一并保存
总结
你会发现，Redis 就是这些常用数据结构的封装。
当你理解了常用的数据结构和算法，理解这些常用工具的能力也提升了。
这个可能就是打基础的重要性吧。
以上就是本节的所有内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论