目录
1. Redis数据类型 1.1 基本数据类型 1. string 2. hash 3. list 4. set 5. sortset/Zset 1.2 特殊数据类型 1. bitmap 2. hyperloglog 3. GEO 4. stream 2. Redis底层数据类型 2.1 简介 2.2 动态字符串SDS 2.3 快表QuickList 2.4 字典Dict 2.5 跳跃表ZSipList 2.6 整数集合IntSet 2.7 压缩列表ZipList 面试模拟 参考资料声明：Redis的相关知识是面试的一大热门知识点，同时也是一个庞大的体系，所涉及的知识点非常多，如果用一篇文章罗列，往往会陷入知识海洋中无法感知其全貌，因此，这段时间我会试着拆分Redis的相关章节，辅以思维导图的形式介绍Redis的相关知识点，知识点范围包括如下几部分 Redis基本概念和特点 Redis数据结构和底层数据类型 Redis持久化（AOF和RDB） Redis集群和高可用性 Redis缓存 Redis分布式锁 Redis实现异步队列 Redis运维问题
今天主要介绍的是Redis数据结构和底层数据类型
1. Redis数据类型
在之前的 Redis基本概念 讲解中，我们知道Redis的存储单位是 键值对 。
其中，键 key 只能是字符串类型，而值 value 则支持丰富的数据类型，包括基本数据类型和特殊数据类型。
1.1 基本数据类型
1. string字符串类型，容量大小不超过512MB。主要存储内容为三类：
字符串：普通字符串 or 复杂的字符串（JSON/XML等）； 数字：整数 or 浮点数； 二进制文件：图片、视频、音频等。应用场景：缓存、计数器、session共享等。
相关命令：
set key value：根据key查找指定键，设置值为value get key：根据key查找指定键，获得其存储的value值 del key：根据key查找指定键，删除其存储的value值 incr key：根据key查找指定键，将其存储的value值自增1 decr key：根据key查找指定键，将其存储的value值自减1 incrby key amount：根据key查找指定键，将其存储的value值自增amount decrby key amount: 根据key查找指定键，将其存储的value值自减amount 2. hash之前我们提到过Redis的存储单位是 键值对 ，hash指的是值本身又是一个键值对。
应用场景：缓存、存储对象信息等。
相关命令： - hset key field value：根据key查找指定键，这个键的值是一个哈希表，添加键值对field:value - hget key field：根据key查找指定键，这个键的值是一个哈希表，获取键field对应的值 - hgetall key：根据key查找指定键，这个键的值是一个哈希表，获取哈希表中所有的键值对 - hdel key field：根据key查找指定键，这个键的值是一个哈希表，删除键field对应的键值对3. list
在Redis中使用 双端链表 实现list，列表的插入和删除可以引申出栈、队列等特殊的数据结构。
应用场景：消息队列、时间列表等。
相关命令：
lpush key value：根据key查找指定键，这个键的值是一个列表，把value值插入到列表的左端（左端push） rpush key value：根据key查找指定键，这个键的值是一个列表，把value值插入到列表的右端（右端push） lpop key：根据key查找指定键，获得键的对应值是一个列表，将列表的左侧首元素弹出 rpop key：根据key查找指定键，获得键的对应值是一个列表，将列表的右侧首元素弹出 lrange key start end：根据key查找指定键，获得键的对应值是一个列表，获取列表中指定范围的元素 lindex key index：根据key查找指定键，获得键的对应值是一个列表，获取列表中指定索引的元素，支持负数下标表示倒数第x个元素。 4. set通过哈希表实现set，不允许重复元素。
应用场景：共同好友、共同关注等。
相关命令：
sadd key value：根据key查找指定键，这个键的值是一个集合，把value值插入到集合中 scard key：根据key查找指定键，获得键的对应值是一个集合，获取集合中元素的个数 smembers key：根据key查找指定键，获得键的对应值是一个集合，获取集合中所有元素 sismember key member：根据key查找指定键，获得键的对应值是一个集合，判断member是否在集合中 5. sortset/Zset通过压缩列表或者跳跃表实现Zset，在第二部分会讲到。Zset不允许重复元素，但是每个元素都会关联一个double类型的分数，表示权重。元素本身不能重复，但是double类型的分数可以重复。Zset中的成员，根据分数从小到大排序。
应用场景：排行榜、带权重的消息队列等。
相关命令：
zadd zset-key score member：根据key查找指定键，这个键的值是一个有序集合，把member值插入到集合中，同时关联一个double类型的分数score zrange zset-key start end：根据key查找指定键，获得键的对应值是一个有序集合，获取集合中指定范围的元素 zrem zset-key member：根据key查找指定键，获得键的对应值是一个有序集合，删除集合中指定的元素1.2 特殊数据类型
1. bitmap位图数据结构，操作二进制位进行记录，每一位都只有0·1两种状态，可以节省存储空间。
应用场景：统计用户的签到情况、统计用户的在线情况等。（今日已签/未签、今日在线/不在线）。
相关命令：
setbit key offset value：根据key查找指定键，设置指定偏移量位置的值为value getbit key offset：根据key查找指定键，获得指定偏移量位置存储的value值 bitcount key [start end]：根据key查找指定键，在值所对应的的位图中，统计指定范围内的二进制位中1的个数 2. hyperloglog拥有基数统计的数据结构，基数指的是集合中去掉重复数字之后的元素个数。基数统计指的是在误差允许范围内估算一组数据的基数，而不需要对数据进行全量统计。这样做的好处就是可以节省大量的内存空间。
应用场景：统计网站的UV（独立访客）、注册ip数、在线用户数、共同好友数等等
相关命令：
PFADD key element [element ...]：根据key查找指定键，这个键的值是一个基数统计的数据结构，添加元素到基数统计的数据结构中 PFCOUNT key ：根据key值查找指定键，统计指定键对应的基数统计的数据结构中的基数。 PFCOUNT key [key ...]：根据key值查找指定键，统计多个键对应集合的并集，对这个集合中的元素统计其基数。 PFMERGE destkey sourcekey [sourcekey ...]：根据key值查找指定键，将多个键对应集合的并集，并集存储在destkey对应的值中。 3. GEO本身是使用zset实现的，存储的是经纬度信息，可以用来计算两个地理位置之间的距离。
应用场景：地图检索的相关场景
相关命令：
geoadd key longitude latitude member [longitude latitude member ...]：查找key对应的指定键，这个键的值是一个GEO类型，添加相关地理位置信息（经度longitude 维度latitude 成员名member）到数据结构中。 geopos key member [member ...]：查找key对应的指定键，这个键的值是一个GEO类型，获取指定成员的经纬度信息。 geodist key member1 member2 [unit]：查找key对应的指定键，这个键的值是一个GEO类型，获取两个成员之间的距离。 GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]：查找key对应的指定键，这个键的值是一个GEO类型，以给定的经纬度为圆心，半径为radis，单位为（m米|km千米|ft英尺|mi英里）查找该范围内的位置元素。 WITHCOORD：将位置元素的经纬度也一并返回 WITHDIST：将位置元素与中心之间的距离也一并返回 WITHHASH：将位置元素的geohash值也一并返回 ASC：根据中心的位置，按照从近到远的顺序返回位置元素 DESC：根据中心的位置，按照从远到近的顺序返回位置元素 COUNT：限制返回的位置元素数量，从而减少带宽 4. streamStream这个数据结构，乍一看很像是文件读写时产生的流，但是实际上，这个数据结构和 消息队列 的实现有关。
Redis中消息队列的实现方式为 发布订阅pub/sub ，但是无法记录历史信息，而Stream支持消息持久化和主备到。
Redis中Stream的数据结构如下所示：
其中：
stream的应用场景和 消息队列 的实现是绑定的。
相关命令:
消息队列相关 XADD key ID field value [field value ...]：根据键值key查找相关队列对象，在队尾添加消息。消息id一般使用 * 表示redis自动生成，自定义需要保证递增性， XADD mystream * field1 A field2 B field3 C field4 D :在mystream对应的消息队列中添加多条消息，消息id自动生成，消息内容为field1:A field2:B field3:C field4:D XLEN key：根据键值key查找相关队列对象，获得消息长度 XLEN mystream :获得mystream对应的消息队列的长度 XTRIM key MAXLEN [~] count：根据键值key查找相关队列对象，对队列进行修剪，限制长度为MAXLEN XTRIM mystream MAXLEN 2 ：修剪mystream对应的消息队列，限制长度为2 XDEL key ID [ID ...]：根据键值key查找相关队列对象，删除指定ID的信息 XDEL mystream 1538561700640-0 ：在mystream对应的消息队列中删除id为1538561700640-0的消息 XRANGE key start end [COUNT count]：根据键值key查找相关队列对象，获得[start end]之间的消息列表，id从小到大。count控制返回的消息数量，自动过滤已删除的消息 XRANGE writers - + COUNT 2 ：按照id从小到大的顺序，在writer对应的消息队列中返回2个消息记录 此处的 - 和 + 表示最小值和最大值，只返回2个消息记录； XREVRANGE key end start [COUNT count]：根据键值key查找相关队列对象，反向获取[end start]之间的消息列表，ID从大到小 XREVRANGE writers + - COUNT 1 ：按照id从大到小的顺序，在writer对应的消息队列中返回一个消息记录 XREAD [COUNT count] [BLOCK milliseconds] STREAMS key [key ...] id [id ...]：count表示获取数量，block的毫秒数表示阻塞的毫秒数，没有设置则表示非阻塞，根据key查找相关消息对象，读取对应id的消息 XREAD COUNT 2 STREAMS mystream writers 0-0 0-0 ：从mystream、writers中分别读取id为0-0的消息，返回消息列表 消费组相关 XGROUP CREATE key groupname id-or-$ ：在键值为key的值部分创建消费组，如果不存在key对应的表项则创建，消费组名为groupname， id-or-$ 决定消费方向，如果id为0-0，则表示从头开始读取消息，如果id是 $ ，表示从尾部开始消费 XGROUP CREATE mystream group1 0-0 ：在mystream对应的消息队列中创建消费组group1，从头开始消费 XREADGROUP GROUP group consumer [COUNT count] [BLOCK milliseconds] [NOACK] STREAMS key [key ...] ID [ID ...] ：在key对应的消息队列中，消费组名为group，消费者名为consumer，该消费者读取消息队列中对应id的信息，读取数量为count，milliseconds表示阻塞时间 XREADGROUP GROUP consumer-group-name consumer-name COUNT 1 STREAMS mystream > XACK key group id ：被group对应的消费组处理的指定id的消息标记为"已读" XGROUP SETID key groupname id-or-$ ：在键值为key对应的消息队列，指定名为groupname的消息队列进行游标移动， id-or-$ 决定消费方向，如果id为0-0，则表示从头开始读取消息，如果id是 $ ，表示从尾部开始消费 XGROUP DELCONSUMER key groupname consumername ：删除对应键值的消息队列中名为groupname的消费者组中，名为consumername的消费者 XGROUP DESTROY key groupname ：删除对应键值的消息队列中名为groupname的消费者组 XPENDING key group ：显示对应键值的对应消费组中待处理消息的信息列表，这些信息已经被读取，但是还没有被确认 XCLAIM key group consumername milliseconds ID ：转移消息归属权，类似于传递数据，键值key对应的消息队列，将对应id的信息转移到消费者组group中对应的消费者consumername中，milliseconds表示阻塞时间，超过这个时间才开始转移 XINFO GROUPS groupname ：打印对应消费者组信息 XINFO STREAM key ：打印对应流信息 XINFO CONSUMERS key groupname ：打印对应消费者组中消费者信息2. Redis底层数据类型
2.1 简介
在前文中，我们了解到Redis的基本存储单位是键值对，其中 value 部分支持丰富的数据类型，包括五个基本类型以及Bitmap、hyberloglog、geo、stream等特殊类型，不同的数据类型有不同的使用场景，因此Redis的功能十分强大。而这些丰富的数据类型，每个对象都是有两部分组成的：
对象结构redisObject 对应编码的数据结构Redis 底层数据类型和数据结构的映射关系如下图所示：
而Redis为什么要多此一举，在实现数据类型之后，又要另外构建一套底层数据结构呢？
在之前的介绍中，我们介绍了很多相关的命令，其中很多都是基于键查找值对象，而有的命令是某个值对象特有的，例如 LPUSH 和 LLEN 等只用于列表， SADD 只作用于集合，因此，为了方便这些命令的执行，需要让每个键都带有类型信息，从而让程序选择合适的处理方式。
简单来说，就是 Redis相关操作命令的多态性 决定了Redis需要底层数据结构的支持。
2.2 动态字符串SDS
存储二进制数据的动态扩容字符串，整体由三部分组成：
头部sdshdr: 具体包括四种头部，如下图所示：其中， len 表示字符串的长度， flags 表示头部的类型，使用最后三位， alloc 表示头部和 \0 之外的字节数 数据buf \0
和C语言中的字符串相比，SDS的优势在于：
常数复杂度获取字符串长度：读取 len 参数即可获得字符串长度，时间复杂度为 O(1) 。 动态分配避免缓冲区溢出：SDS在进行字符修改的时候，先根据 len 检查内存空间是否满足，如果不足会进行内存扩展 减少修改字符串时带来的内存重分配次数：SDS在进行字符修改的时候，当字符串长度增加时，会预分配更多的内存空间（分配后长度小于1M，增加所需长度的两倍；分配后长度大于1M，则增加1M空间），减少内存重分配次数；当字符串长度减少的时候，不会立刻进行内存重新分配，二十使用 alloc 记录字节数，供后续使用 二进制安全：SDS可以存储二进制数据，而C语言中的字符串只能存储文本数据，因此SDS是二进制安全的 兼容C语言字符串：SDS以 \0 结尾，因此可以使用C语言字符串的大部分函数，例如 strlen 、 strcat 、 strcpy 等2.3 快表QuickList
是一种双向链表，节点为ziplist(压缩链表)的形式：
这里定义了6个结构体:
2.4 字典Dict
是一种哈希表，使用链地址法解决哈希冲突。
如图展示的是内存的分配情况：
table是一个数组，每个元素都是一个数值存放节点。
每个节点都是一个dictEntry结构体，其中key和value都是一个指针，指向实际存储的数据。
源代码如下所示：
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
//总是等于 size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}dictht
typedef struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一个哈希表节点，形成链表
struct dictEntry *next;
}dictEntry
2.5 跳跃表ZSipList
跳跃表实际应用中主要作为有序列表使用，但是性能比一般的有序列表更优。
源码定义如下所示：
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
设计思路为：
头节点不持有任何数据, 且其level[]的长度为32
每个结点包括如下几个字段：
每个zskiplistLevel中有两个字段 forward字段指向比自己得分高的某个结点(不一定是紧邻的), 并且, 若当前zskiplistLevel实例在level[]中的索引为X, 则其forward字段指向的结点, 其level[]字段的容量至少是X+1. 这也是上图中, 为什么forward指针总是画的水平的原因. span字段代表forward字段指向的结点, 距离当前结点的距离. 紧邻的两个结点之间的距离定义为1.
和平衡树、哈希表等元素相比，跳跃表需要更大的存储空间，打死你性能更优；在范围查找上有相当的优势，且插入和删除更简单，算法实现也更容易。
2.6 整数集合IntSet
encoding 表示编码方式，的取值有三个：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
length 代表其中存储的整数的个数
contents 指向实际存储数值的连续内存区域, 就是一个数组；整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值得大小从小到大有序排序，且数组中不包含任何重复项。（虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值，contents 数组的真正类型取决于 encoding 属性的值）
整数集合的升级
当存储int64的整数集合添加一个int32的元素，会导致集合中所有元素转变为int32类型，按照新元素的类型进行扩容和空间分配，将现有元素转变为新类型，之后改变encoding的值（对应存储元素的类型），并且length+1(表示加入一个新元素)。
2.7 压缩列表ZipList
是一种双向链表，可以存储字符串或整数（二进制形式）。
整体由5部分组成：
和一般的数组相比，ziplist的优势在于：
节省内存：不需要预留空间，而是按照encoding字段的实际需求来确定存储空间大小同样也是因为节省内存，不浪费一点内存的思路，导致ziplist的缺点也很明显：
每次写操作都需要进行内存分配 扩容可能导致链式反应，影响后续节点的存储面试模拟
Q：Redis的数据结构
A：从基本数据类型、特殊数据类型、底层数据结构三个方面回答
Q：为什么Redis使用的是哈希索引
A：内存键值数据库采用哈希表作为索引，很大一部分原因在于，其键值数据基本都是保存在内存中的，而内存的高性能随机访问特性可以很好地与哈希表O（1）的操作复杂度相匹配。
Q：Redis字符串底层和查询过程用的哪些数据结构
A：底层查询的过程中会涉及到跳跃表的使用。
参考资料
Redis教程 - Redis知识体系详解 三万字+八十图，详解Redis五十二问！太全面了! 妈妈再也不担心我面试被Redis问得脸都绿了 Redis Bitmap 学习和使用 Redis源码剖析--基数统计hyperloglog Redis GEO & 实现原理深度分析 基于Redis的Stream类型的完美消息队列解决方案 Redis Stream
查看更多关于【后端面经-数据库】Redis数据结构和底层数据类型的详细内容...