Redis入门到通关之数据结构解析-动态字符串SDS

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis入门到通关之数据结构解析-动态字符串SDS

Redis数据结构-动态字符串


我们都知道 Redis 中保存的Key是字符串,value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构。

不过 Redis 没有直接使用C语言中的字符串,因为C语言字符串存在很多问题:

  • 获取字符串长度的需要通过运算
  • 非二进制安全
  • 不可修改

Redis 构建了一种新的字符串结构,称为简单动态字符串(Simple Dynamic String),简称 SDS

例如,我们执行命令:

set name 技术

那么 Redis 将在底层创建两个 SDS,其中一个是包含“name”的 SDS,另一个是包含“技术”的 SDS。

Redis 是 C 语言实现的,其中 SDS 是一个结构体,源码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct sds {
    int len;         // 记录字符串的长度
    int free;        // 记录未使用的字节数
    char buf[];      // 字符串的实际存储空间
} sds;
// 创建一个新的 sds
sds *sds_new(int init_len) {
    sds *s = malloc(sizeof(sds) + init_len + 1);
    if (!s) return NULL;
    s->len = 0;
    s->free = init_len;
    s->buf[0] = '\0';
    return s;
}
// 释放 sds
void sds_free(sds *s) {
    if (s) free(s);
}
// 追加字符串到 sds
sds *sds_append(sds *s, const char *append) {
    int append_len = strlen(append);
    if (s->free < append_len) {
        s = realloc(s, sizeof(sds) + s->len + append_len + 1);
        if (!s) return NULL;
        s->free = append_len;
    }
    memcpy(s->buf + s->len, append, append_len);
    s->len += append_len;
    s->free -= append_len;
    s->buf[s->len] = '\0';
    return s;
}
// 打印 sds
void sds_print(const sds *s) {
    printf("Length: %d\n", s->len);
    printf("Free: %d\n", s->free);
    printf("String: %s\n", s->buf);
}
int main() {
    sds *str = sds_new(10);
    if (!str) {
        printf("Error: Unable to create SDS.\n");
        return 1;
    }
    str = sds_append(str, "Hello, ");
    if (!str) {
        printf("Error: Unable to append to SDS.\n");
        return 1;
    }
    str = sds_append(str, "world!");
    if (!str) {
        printf("Error: Unable to append to SDS.\n");
        return 1;
    }
    sds_print(str);
    sds_free(str);
    return 0;
}

例如,一个包含字符串“name”的sds结构如下:


动态扩容举例


SDS 之所以叫做动态字符串,是因为它具备动态扩容的能力,例如一个内容为“hi”的SDS:

假如我们要给SDS追加一段字符串“,Amy”,这里首先会申请新内存空间:

  • 如果新字符串小于1M,则新空间为扩展后字符串长度的两倍+1;
  • 如果新字符串大于1M,则新空间为扩展后字符串长度+1M+1。称为内存预分配


二进制安全


  • Redis 可以存储各种数据类型,那么二进制数据肯定也不例外。但二进制数据并不是规则的字符串格式,可能会包含一些特殊的字符,比如 ‘\0’ 等。
  • 前面我们提到过,C 中字符串遇到 ‘\0’ 会结束,那 ‘\0’ 之后的数据就读取不上了。但在 SDS 中,是根据 len 长度来判断字符串结束的。
  • 如此, 二进制安全的问题就解决了。


SDS优点


SDS 优点:

  1. 获取字符串长度的时间复杂度为O(1)
  2. 支持动态扩容, 减少内存分配次数
  3. 二进制安全

与C语言中的字符串的区别


SDS(Simple Dynamic String)是Redis使用的一种字符串表示方式,与C语言中的字符串有一些显著的区别:

  • 动态调整大小:SDS是动态分配内存的,可以根据需要动态增加或减少其大小,而C语言中的字符串通常是静态分配的,大小在创建时就确定了,后续无法直接调整大小。
  • 二进制安全:SDS允许存储任意二进制数据,而C语言中的字符串通常以NULL结尾,因此不适合存储包含NULL字符的二进制数据。
  • 惰性空间释放:SDS采用惰性空间释放策略,即当SDS的内容被截断或缩短时,并不立即释放多余的内存,而是等待下一次需要扩展空间时才释放。这种策略可以减少频繁的内存分配和释放操作,提高性能。而C语言中的字符串在缩短时无法自动释放多余的内存,需要手动管理内存。
  • 长度存储:SDS在内部存储了字符串的长度信息,这样可以在O(1)时间内获取字符串的长度,而C语言中的字符串需要遍历整个字符串才能确定长度。

SDS是一种更加灵活和高效的字符串表示方式,特别适合需要频繁修改和操作字符串的场景,而C语言中的字符串更适合于静态不变的情况。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
23小时前
|
NoSQL Java Redis
如何在 Java 中操作这些 Redis 数据结构的基本方法
如何在 Java 中操作这些 Redis 数据结构的基本方法
8 2
|
10天前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
1天前
|
存储 NoSQL 算法
redis数据结构—哈希表
redis数据结构—哈希表
11 0
|
13天前
|
XML 数据采集 自然语言处理
掌握Python字符串:全面解析与实战指南
掌握Python字符串:全面解析与实战指南
|
15天前
|
缓存 NoSQL 关系型数据库
Redis第二课,1.set key value(设置对应的key和value)2.get key(得到value值)Redis全局命令(支持很多的数据结构)3.keys(用来查询当前
Redis第二课,1.set key value(设置对应的key和value)2.get key(得到value值)Redis全局命令(支持很多的数据结构)3.keys(用来查询当前
|
NoSQL 安全 Shell
Redis源码学习——基础数据结构之SDS
###Redis数据结构-SDS Redis是一个开源(BSD许可),内存存储的数据结构服务器,可用作数据库,高速缓存和消息队列代理。 首先介绍下Redis的基础数据结构 —— SDS Redis没有使用传统C语言的字符串(字符数组)表示。而是自己构建了一种名为sds(Simple Dymamic String)的抽象类型,作为redis的默认字符类型。 SDS用于保存数据库中的
3907 0
|
1月前
|
NoSQL Linux 网络安全
Linux安装Redis(详细教程)
Linux安装Redis(详细教程)
97 2
|
28天前
|
NoSQL Linux Redis
Redis -- 安装客户端redis-plus-plus
Redis -- 安装客户端redis-plus-plus
50 0
|
2天前
|
NoSQL Redis Windows
win10下Redis安装、启动教程
win10下Redis安装、启动教程
11 2
|
4天前
|
消息中间件 缓存 NoSQL
Redis单实例安装
Redis单实例安装
14 1

推荐镜像

更多