文档章节

Redis数据结构——SDS,链表

nao
 nao
发布于 2016/05/04 20:00
字数 805
阅读 107
收藏 7

简单动态字符串

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

SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度仅为O(1)。

SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性。当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需要的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以

SDS 既不需要手动修改SDS的空间大小,也不会出现缓冲区溢出问题。

SDS通过free 未使用空间解除了字符串长度和底层数组长度之间的关联;在SDS中,buf数组的长度不一定就是字符串数量加1,数组中可包含未使用的字节,而这些字节的数组就有SDS的free属性记录。

使用未使用空间,SDS实现了空间预分配惰性空间释放两种优化策略。

Redis 只会使用C字符串作为字面量,在大多数情况下,Redis 使用SDS(Simple Dynamic String, 简单动态字符串)作为字符串表示。

比起C字符串,SDS具有以下优点:

  1. 常数复杂度获取字符串长度。

  2. 杜绝缓冲区溢出。

  3. 减少修改字符串长度使所需的内存重分配次数。

  4. 二进制安全

  5. 兼容部分C字符串函数


链表

typedef struct listNode {
    struct listNode *prev;  //前置节点
    struct listNode *next;  //后置节点
    void *value;    //节点的值
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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

Redis的链表实现的特性可以总结如下:

双端:链表节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)

无环: 表头节点的prev指针和表尾节点的next指针都指向NULL, 对链表的访问以NULL为终点。

带表头指针和表尾指针:通过list结构的head指针和tail指针,程序获取链表的表头节点和表尾节点的复杂度为O(1).

带链表长度计数器:程序使用list结构的len属性来对list持有的链表节点进行计数,程序获取链表中节点数量的复杂度为O(1)。

多态: 链表节点使用void *指针来保存节点值,并且可以通过list结构的dup,free,match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。


© 著作权归作者所有

nao

nao

粉丝 28
博文 155
码字总数 108154
作品 0
成都
后端工程师
私信 提问
Redis为何这么快——数据存储角度

本文内容思维导图如下: 一、简介和应用 Redis是一个由ANSI C语言编写,性能优秀、支持网络、可持久化的K-K内存数据库,并提供多种语言的API。它常用的类型主要是 String、List、Hash、Set、...

Java干货分享
2018/10/09
0
0
Redis 的基础数据结构(一) 可变字符串、链表、字典

这篇文章关于 Redis 的基础数据。阅读这篇文章你可以了解: 动态字符串(SDS) 链表 字典 三个数据结构 Redis 是怎么实现的。 SDS SDS (Simple Dynamic String) 是 Redis 最基础的数据结构。...

哲别0
2018/05/07
0
0
Redis为何这么快--数据存储角度

本文内容思维导图如下: 一、简介和应用 Redis是一个由ANSI C语言编写,性能优秀、支持网络、可持久化的K-K内存数据库,并提供多种语言的API。它常用的类型主要是 String、List、Hash、Set、...

我叫刘半仙
2018/10/09
0
0
Redis详解(四)------ redis的底层数据结构

  上一篇博客我们介绍了 redis的五大数据类型详细用法,但是在 Redis 中,这几种数据类型底层是由什么数据结构构造的呢?本篇博客我们就来详细介绍Redis中五大数据类型的底层实现。 1、演示...

ysocean
2018/06/01
0
0
可能是目前最详细的Redis内存模型及应用解读

Redis是目前最火爆的内存数据库之一,通过在内存中读写数据,大大提高了读写速度,可以说Redis是实现网站高并发不可或缺的一部分。 我们使用Redis时,会接触Redis的5种对象类型:字符串、哈希...

编程迷思
2018/07/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MySql双主架构原理

在企业中,一般系统架构的瓶颈会出现在数据库这一部分,mysql主从架构在很大程度上解决了这部分瓶颈,但是在mysql主从同步的架构也存在很多问题;比如:1.关于数据写入部分(也就是主库)往往很难做...

xiaomin0322
26分钟前
0
0
分布式系统中一致性哈希

问题场景 近年来B2C、O2O等商业概念的提出和移动端的发展,使得分布式系统流行了起来。分布式系统相对于单系统,解决了流量大、系统高可用和高容错等问题。功能强大也意味着实现起来需要更多...

Java领航员
28分钟前
0
0
接口限流算法:漏桶算法和令牌桶算法

漏桶算法 漏桶可以看作是一个带有常量服务时间的单服务器队列,如果漏桶(包缓存)溢出,那么数据包会被丢弃。这一点和线程池原理是很相似的。 把请求比作是水,水来了都先放进桶里,并以限定...

铁骨铮铮
35分钟前
5
0
Android 生成二维码工具类

/** * 生成条形码和二维码的工具 */public class ZXingUtils { /** * 生成二维码 要转换的地址或字符串,可以是中文 * * @param url * @param width ...

lanyu96
40分钟前
1
0
谈谈lucene的DocValues特性之SortedNumericDocValuesField

前面已经介绍过NumericDocValuesField,这里想强调一下SortedNumericDocValuesField是针对同一篇文档中一键多值的情况进行排序的,换句话说不同文档的同一字段值可以乱序。核心的写入流程与谈...

FAT_mt
48分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部