redis面试系列：数据结构

本文参考了《redis设计与实现》第二版

1. 数据类型

  • 常见数据类型
    • string 字符串(简单动态字符串[sds],int整数)
    • list 列表(链表[linkedlist]，压缩表[ziplist])
    • hash 哈希（字典[hashtable]，压缩表[ziplist]）
    • set 集合（字典[hashtable], 整数集合[intset]）
    • zset 有序集合（跳跃表[skiplist], 压缩表[ziplist]）
  • 其他高级类型
    • bitmap
    • HyperLogLog
    • Pub/Sub
    • Geo
    • BloomFilter

此文主要分析常见数据结构的应用场景、实现原理。

2. 简单动态字符串（SDS）

  redis是基于c语言实现的，但是redis的字符串却没有直接使用c语言的string类型，而是基于自己实现的简单字符串（simple dynamic string，简称sds）。sds的数据结构如下所示：

1
2
3
4
5
struct sdshdr {
    int free;
    int len;
    char buf[];
}
  • 每一个字符串对应底层的sds是由三部分组成，分别是空闲空间长度，字符串长度，保存字符串的字节数组
  • free表示当前空闲的字节数，即空闲空间长度
  • len是用来保存当前字符串使用的字节长度，通常用来表示字符串的长度
  • redis的字符串在sds底层是通过字节数组的方式保存在buf当中

为什么redis放着c语言现成的字符串类型不用，却自己去实现一套sds呢？从sds的数据结构可以看出它具备以下几个特点：
redis基本数据结构

（1）有效防止缓存区溢出

  • SDS在执行修改之前会检查空间是否足够，如果不够用会自动将空间扩展

（2）获取字符串长度的复杂度为O(1)

  • SDS本身保存了自身的长度，所以直接获取就行

（3）减少内存分配次数

  • 在C语言中，每次对字符的修改涉及到长度的变动时，都会发生系统对内存的操作（申请或释放）。SDS通过空间预分配和惰性释放极大减少了对内存的操作次数。
  • 空间预分配：每次涉及到对字符串的操作时候，SDS不仅会为其分配修改所需要的空间，还会为SDS分配额外未使用的空间。
  • 惰性释放：字符串长度缩短之后，不需要的空间不会立刻释放，而是分配到free空间里面，下次需要的时候直接获取，不需要重新分配内存。

（4）二进制安全

  • 不同于C语言特殊的字符保存格式（字符串加末尾空字符），redis的SDS不会受限于任何格式，保存时候不会发生修改，所以它可以用来保存图片，视频等二进制数据。

3. 链表

  C语言本身是没有链表这一数据结构，redis是自己实现的。链表提供了搞笑的节点重排，节点访问，节点增删能力。redis的列表底层实现之一就是链表，而且redis的发布与订阅，慢查询，监视器等功能也用到了链表，redis本身使用链表来保存多个客户端的状态。
redis基本数据结构

4. 字典（map）

  字典数据结构广泛应用于redis的各种功能当中，包括数据库和哈希键。redis中的字典使用哈希表作为底层实现，每个字典包含了两个哈希表，一个平时使用，一个是在rehash(扩展或收缩hash表)时用到。

5. 跳跃表（skiplist）

  跳跃表是一种有序的数据结构，它通过在每个节点中维持指向其他节点的指针，从而拥有快速访问其他节点的能力。redis选择跳跃表作为有序集合的底层实现之一。

6. 整数集合（intset）

  整数集合是集合键的底层实现之一。当一个集合只用来保存整数，并且数量不是很多的时候，redis就会选择使用整数集合来实现。

7. 压缩表（ziplist）

 &emsp压缩表是列表和哈希两种数据类型的底层实现之一，压缩表是redis为了节约内存而开发的，它是由特殊编码的连续内存块组成的顺序数据结构。当一个列表只包含少量的键，并且每个键对应的值比较小的时候，redis就会使用压缩表来实现该列表。同样如果一个hash键只包含少量的值，则也会选择压缩表作为其底层实现。