Redis数据结构简介

​前言

Redis 是一个开源，高级的键值存储和一个适用的解决方案，用于构建高性能，可扩展的 Web 应用程序。在互联网公司中得到了广泛应用，面试也一定会问到，今天我们就来介绍一下redis的相关知识，希望能助各位在面试中脱颖而出

为什么是Redis？

为什么使用Redis而不是Mysql？

1. 快  redis非常快 每秒最多可支持11万次的写操作 ，8万次的读操作 ，这个读写效率是MYSQL拍马莫及的。
2. 支持多种数据类型 Redis 支持多种类型的数据结构 包括 String hash list set 等 这个我们下文会详细介绍
3. 原子性 redis的单次命令都具有原子性 ，避免了可能因并发导致的问题，此外，redis还支持Lua 可以利用Lua一次提交多个命令 使这些命令也具有原子性

基本数据结构

Redis 有五种基本数据结构，它们分别是 String，Hash，Set，ZSet，List，这是Redis中最基础，最重要的知识点。下面我们将重点介绍这五种类型

字符串 String

Redis中的字符串存储的是动态字符串（SDS），这种字符串的长度是可变的

SDS的结构可如上图所示 其中有一个字段记录了字符串长度，这样每次获取长度的复杂度就为O(1)，alloc 记录了分配给这个字段的长度，每次修改字段内容时，以此判断是否需要扩容，flags记录了SDS的类型 ，这里不详细展开，感兴趣的小伙伴可以自行了解一下，buf[] 记录的就是字段实际存储的内容。

使用SDS有以下好处 首先在获取长度时不需要每次计算一遍 这样能提高效率，也不需要手动扩容 ，避免了缓冲区溢出，每次修改时只需要计算alloc-len是否符合长度 如果长度不够则进行扩容，扩容完毕后再执行修改或插入操作

列表 List

除了数组外 大家最熟悉的就是链表了，在redis中list的底层实现就是基于链表，我们可以先简单的把Redis中的list理解为一个双链表 每一个节点都有前后指针。

上图就是Redis中list的大体结构，会有头/尾指针直接执行记录数据的头和尾，记录数据是一个双链表结构，此外列表还记录了链表的长度信息

这种好处不言而喻，在对链表头尾进行操作时十分便捷，还可以直接获取链表的长度信息。

字典 Hash 

Redis中的Hash相当于Java中的HashMap ，实现原理也十分相似，也是通过数组加链表的方式解决hash冲突，下面我们简单看下源码的实现

typedefstruct dictht {    // 哈希表数组    dictEntry **table;    // 哈希表大小    unsignedlong size;    // 哈希表大小掩码，用于计算索引值，总是等于 size - 1    unsignedlong sizemask;    // 该哈希表已有节点的数量    unsignedlong used;} dictht;​typedefstruct dict {    dictType *type;    void *privdata;    // 内部有两个 dictht 结构    dictht ht[2];    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    unsignedlong iterators; /* number of iterators currently running */} dict;

在这里我们可以看到Redis中hash有两个table的属性，这里就要引入一个新的概念“渐进式Hash”

大字典的扩容是一项耗时的操作，因为它涉及到重新申请新的数组并重新挂接旧字典中的所有链表元素到新的数组下面。这个过程的时间复杂度为O(n)，对于单线程的Redis而言，难以承受这样耗时的操作。

为了解决这个问题，Redis采用了渐进式rehash的策略。在渐进式rehash过程中，会同时保留新旧两个哈希结构。在查询时，会同时查询两个哈希结构，以确保数据的一致性。同时，通过定时任务和哈希操作指令，逐步将旧字典的内容迁移到新字典中。当迁移完成后，新的哈希结构会取代旧的哈希结构，并成为主要的数据存储结构。这种渐进式的迁移方式可以有效地减少对单线程Redis的影响。

hash 也有缺点，hash 结构的存储消耗要高于单个字符串，所以到底该使用 hash 还是字符串，需要根据实际情况再三权衡。

集合 Set

Redis 的集合相当于 Java 中的 Set，它内部的键值对是无序且唯一的。它的内部实现相当于一个特殊的Hash，只不过字典对应的值都是NULL。Redis提供了丰富的集合操作，如并集、交集、差集等，可以对多个Set进行操作，方便进行集合运算。

排序集合 ZSet 

ZSet又称SortedSet,可以理解为Set的增强版 。相比于Set，ZSet有一个额外的属性Score，ZSet的排序就依赖于这个Score，ZSet常用于需要按照某种顺序获取元素的场景，比如排行榜、优先级队列等。Redis提供了一系列的ZSet操作，如按分数范围获取元素、按排名获取元素、计算元素的分数等。像我们经常刷的微博热搜，其底层实现一开始就是利用ZSET做的

尾声

这一期我们简单介绍了Redis中的数据结构，下一期我们将更加深入探究Redis的内部