Redis-数据结构-SDS、链表

一、简单动态字符串 SDS（simple dynamic string）

1、redis中使用SDS作为默认字符串表示，C字符串只会作为字符串字面量使用（无须对字符串值进行修改，如打印日志）

2、定义

3、SDS与C字符串的区别

    3.1、常数复杂度获取字符串长度

            SDS在len属性中记录了字符串的长度，获取SDS长度的算法复杂度为O(1)

    3.2、杜绝缓冲区溢出

            SDS的API会自动检查空间，不需要手动分配内存，杜绝了缓冲区溢出的可能

    3.3、减少修改字符串时带来的内存重分配次数

            SDS 通过未使用空间（free属性）解除了字符串长度和底层数组长度之间的关联：buf数组的长度不一定是字符串长度+1，buf数组可以包含未使用的字节，这些字节数量由free属性记录

            SDS通过未使用空间，实现了空间预分配和惰性空间释放两种优化策略

                    3.3.1 空间预分配

            通过预分配策略，SDS将连续增长N次字符串所需内存重分配次数从必定N次降低为最多N次

                    3.3.2、惰性空间释放

                用于优化SDS字符串缩短操作，使用free属性记录释放的空间，在需要真正释放空间的使用再对buf数组进行操作

     3.4、二进制安全（支持二进制数据）

    3.5、兼容部分C字符串函数

4、

        4.1、与Java StringBuilder类对比，StringBuilder 继承抽象类 AbstractStringBuilder

二、链表

1、实现结构

        1.1、链表节点

        1.2、链表

2、特性

                2.1、双端：带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)

                2.2、无环：表头节点的prev和表尾结点的next指针都指向NULL,对链表的方位以NULL为终点

                2.3、带有表头指针和表尾指针

                2.4、带有链表长度计数器

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

3、链表主要用于实现链表键、发布订阅、慢查询（？）、监视器（？）