【面试题】redis的底层数据结构

admin管理员组

文章数量:1794759

【面试题】redis的底层数据结构

redis的底层数据结构

• 1. redis底层用了什么数据结构
• • 1.1 示例一：String类型
  • 1.2 示例二： List类型
• 2. 五种数据类型底层用了什么数据结构
• • 2.1 String(SDS)
  • 2.2 List（linkedlist、ziplist）
  • 2.3 hash（hashtable、ziplist ）
  • 2.4 Set（intset、hashtable）
  • 2.5 Zset（ziplist 、skiplist）
• 3. 底层结构详解
• • 3.1 SDS( 简单动态字符串 )
  • • 3.1.1 SDS结构
    • 3.2.2 为什么不使用C语言字符串实现，而是使用 SDS呢？这样实现有什么好处？
  • 3.2 链表（双向链表）
  • • 3.2.1 链表定义
    • 3.2.2 Redis链表特性
  • 3.3 跳跃表
  • • 3.3.1 结构
    • 3.3.2 查询
  • 4.4. 字典
  • • 4.4.1 哈希表结构定义
    • 4.4.2 哈希表最大的问题是存在哈希冲突，如何解决哈希冲
  • 4.5 压缩列表
  • 4.6 intset

1. redis底层用了什么数据结构

该命令是用来显示那五大数据类型的底层数据结构。

OBJECT ENCODING key 1.1 示例一：String类型

1.2 示例二： List类型

这里我们就不做过多的演示了，那么上次出现的 embstr 以及 int 还有 quicklist 是什么数据结构呢？下面我们就来介绍Redis中几种主要的数据结构。

2. 五种数据类型底层用了什么数据结构 2.1 String(SDS)

字符串的长度不能超过512M。 字符串对象的编码可以是int，raw或者embstr。 int 编码：保存的是可以用 long 类型表示的整数值。 embstr 编码：保存长度小于44字节的字符串。 raw 编码：保存长度大于44字节的字符串。

int 编码是用来保存整数值，raw编码是用来保存长字符串，而embstr是用来保存短字符串。其实 embstr 编码是专门用来保存短字符串的一种优化编码，raw 和 embstr 的区别： embstr与raw都使用redisObject和sds保存数据，区别在于，embstr的使用只分配一次内存空间（因此redisObject和sds是连续的），而raw需要分配两次内存空间（分别为redisObject和sds分配空间）。

ps：Redis中对于浮点数类型也是作为字符串保存的，在需要的时候再将其转换成浮点数类型。

2.2 List（linkedlist、ziplist）

列表对象的编码可以是 ziplist(压缩列表) 和 linkedlist(双端链表)。

比如我们执行以下命令，创建一个 key = ‘numbers’，value = ‘1 three 5’ 的三个值的列表。

rpush numbers 1 "three" 5

ziplist 编码表示如下： 　linkedlist表示如下： 　 编码转换 当同时满足下面两个条件时，使用ziplist（压缩列表）编码：

列表保存元素个数小于512个

每个元素长度小于64字节 不能满足这两个条件的时候使用 linkedlist 编码。 上面两个条件可以在redis.conf 配置文件中的 list-max-ziplist-value选项和 list-max-ziplist-entries 选项进行配置。

2.3 hash（hashtable、ziplist ）

哈希对象的编码可以是 ziplist 或者 hashtable。

比如执行以下命令：

hset profile name "Tom" hset profile age 25 hset profile career "Programmer"

如果使用ziplist，profile 存储如下： 当使用 hashtable 编码时，上面命令存储如下：

编码转换 使用ziplist（压缩列表）编码必须满足下面两个条件，不能满足这两个条件的时候使用 hashtable 编码。

列表保存元素个数小于512个

每个元素长度小于64字节

2.4 Set（intset、hashtable）

set的底层存储intset和hashtable是存在编码转换的，使用intset存储必须满足下面两个条件，否则使用hashtable，条件如下： 结合对象保存的所有元素都是整数值，且个数不超512个。

intset我们可以理解为数组，hashtable就是普通的哈希表（key为set的值，value为null）

2.5 Zset（ziplist 、skiplist）

有序集合的编码可以是 ziplist 或者 skiplist。

ZADD price 8.5 apple 5.0 banana 6.0 cherry

每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个节点保存元素的分值。并且压缩列表内的集合元素按分值从小到大的顺序进行排列，小的放置在靠近表头的位置，大的放置在靠近表尾的位置。 编码转换 当有序集合对象同时满足以下两个条件时，对象使用 ziplist 编码：

保存的元素数量小于128；

保存的所有元素长度都小于64字节。 不能满足上面两个条件的使用 skiplist 编码。

总结 对于string 数据类型，因为string 类型是二进制安全的，可以用来存放图片，视频等内容，另外由于Redis的高性能读写功能，而string类型的value也可以是数字，可以用作计数器（INCR,DECR），比如分布式环境中统计系统的在线人数，秒杀等。 对于 hash 数据类型，value 存放的是键值对，比如可以做单点登录存放用户信。 对于 list 数据类型，可以实现简单的消队列，另外可以利用lrange命令，做基于redis的分页功能 对于 set 数据类型，由于底层是字典实现的，查找元素特别快，另外set 数据类型不允许重复，利用这两个特性我们可以进行全局去重，比如在用户注册模块，判断用户名是否注册；另外就是利用交集、并集、差集等操作，可以计算共同喜好，全部的喜好，自己独有的喜好等功能。 对于 zset 数据类型，有序的集合，可以做范围查找，排行榜应用，取 TOP N 操作等。

3. 底层结构详解 3.1 SDS( 简单动态字符串 )

Redis 是用 C 语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串，它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

3.1.1 SDS结构 struct sdshdr{ //记录buf数组中已使用字节的数量 //等于 SDS 保存字符串的长度 int len; //记录 buf 数组中未使用字节的数量 int free; //字节数组，用于保存字符串 char buf[]; }

3.2.2 为什么不使用C语言字符串实现，而是使用 SDS呢？这样实现有什么好处？

上面的定义相对于 C 语言对于字符串的定义，多出了 len 属性以及 free 属性。 常数复杂度获取字符串长度 由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。 3.2.2.2 减少修改字符串的内存重新分配次数 　C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。 　而对于SDS，由于len属性和free属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略： 　　1. 空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。 　　2. 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 free 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）

3.2 链表（双向链表）

链表是一种常用的数据结构，C 语言内部是没有内置这种数据结构的实现，所以Redis自己构建了链表的实现。

3.2.1 链表定义 typedef struct listNode{ //前置节点 struct listNode *prev; //后置节点 struct listNode *next; //节点的值 void *value; }listNode

通过多个 listNode 结构就可以组成链表，这是一个双向链表，Redis还提供了操作链表的数据结构：

typedef struct list{ //表头节点 listNode *head; //表尾节点 listNode *tail; //链表所包含的节点数量 unsigned long len; //节点值复制函数 void (*free) (void *ptr); //节点值释放函数 void (*free) (void *ptr); //节点值对比函数 int (*match) (void *ptr,void *key); }list;

3.2.2 Redis链表特性

双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。

无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。

带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。

多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

3.3 跳跃表 3.3.1 结构

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。具有如下性质：

由很多层结构组成；

每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点；

最底层的链表包含了所有的元素；

如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；

链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；

3.3.2 查询

搜索 从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。 插入 首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层到k层。 删除 在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

4.4. 字典

用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。 使用哈希表作为底层实现。

4.4.1 哈希表结构定义 typedef struct dictht{ //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码，用于计算索引值 //总是等于 size-1 unsigned long sizemask; //该哈希表已有节点的数量 unsigned long used; }dictht

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

typedef struct dictEntry{ //键 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; }v; //指向下一个哈希表节点，形成链表 struct dictEntry *next; }dictEntry 4.4.2 哈希表最大的问题是存在哈希冲突，如何解决哈希冲

有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。

4.5 压缩列表

压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

previous_entry_ength：记录压缩列表前一个字节的长度。当前节点位置减去上一个节点的长度即得到上一个节点的起始位置，压缩列表可以从尾部向头部遍历。这么做很有效地减少了内存的浪费。

encoding：节点的encoding保存的是节点的content的内容类型以及长度，encoding类型一共有两种，一种字节数组一种是整数，encoding区域长度为1字节、2字节或者5字节长。

content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定。

4.6 intset

intset的结构

typedf struct inset{ uint32_t encoding;//编码方式 有三种 默认 INSET_ENC_INT16 uint32_t length;//集合元素个数 int8_t contents[];//实际存储元素的数组 //元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小，并且数组中的元 //素从小到大排列 }inset;

编码格式encoding：共有三种，INTSET_ENC_INT16、INSET_ENC_INT32和INSET_ENC_INT64三种，分别对应不同的范围。Redis为了尽可能地节省内存，会根据插入数据的大小选择不一样的类型来进行存储。 元素数量length：记录了保存数据的数组contents中共有多少个元素，这样获取个数的时间复杂度就是O(1)。 数组contents：真正存储数据的地方，数组是按照从小到大有序排列的，并且不包含任何重复项。 优点：根据存入的数据大小选择合适的编码方式，且只在必要的时候进行升级操作，节省内存 缺点：升级过程耗费系统资源，还有就是不支持降级，一旦升级就不可以降级

来源：wwwblogs/ysocean/p/9080942.html intset结构：blog.csdn/ymb615ymb/article/details/123371540

本文标签： 数据结构底层面试题Redis