说在前面

感谢牛客举办这样一个有意思的活动，也督促我有更多看书的动力哈哈哈。
也要感谢一下那位给我点赞的同学，让我以总计两票的微弱优势获得了这次的读书活动~

关于这本书

《redis的设计与实现》的作者在前言当中说，这本书可以帮助我们更好的了解redis，避开那些可能引起性能问题的陷阱。

引言给我们提示

1.如果只是对redis原理感兴趣但并不想研究源码，本书够用了
2.本书分为数据结构、单机实现、多机实现和独立功能实现
3.自底向上的章节流程

数据结构

字符串

没有使用C语言自带的字符串表示，而是重新构建了简单动态字符串（simple dynamic string, SDS）的类型。

struct sdshdr{
    int len;//已使用字节数量
    int free;//未使用字节数量
    char buf[];//字节数组，保存字符串
}

sds相比于c语言的字符串，更加安全且效率更高，具体体现在以下几点

获取字符串长度

因为有len属性，所以获取的时间复杂度从O(N)降到O(1)

杜绝缓冲溢出

c语言字符串长度固定，如果字符串拼接前忘记分配空间会造成溢出，sds在拼接前会检测。

内存重分配次数

空间预分配：free和len共同构建buf[]的长度，同时扩张时free的长度也会更新。

惰性空间释放：使用trim方法删除某些字符时，空间并不会真正回收。

链表

和数据结构课程中所学的链表一样，在发布与订阅、慢查询、监视器等功能中都会用到链表。

typedef struct listNode{
    //前节点
    struct listNode *prev;

    //后节点
    struct listNode *next;

    //节点值
    void *value;
}listNode;

typedef struct list{
    listNode *head;

    listNode *tail;

    unsigned long len;

    void *(*dup)(void *ptr);//节点复制函数

    void *(*free)(void *ptr);//节点值释放函数

    void (*match)(void *ptr, void *key);//节点值比较函数
}

字典

字典是一种键值对的数据结构。redis的数据库底层就是字典。

struct dictht{
    //哈希表
}

struct dictEntry{
    //用于保存多个键值对
}

struct dict{
    //dict头
} 

struct dictType{
    //特定类型操作
}

哈希算法

插入数据时，根据哈希函数插入指定索引位置。当存在hash冲突时，使用链地址法，也就是在桶位置构建一个链表。rehash的保证负载因子维持在合理范围，使用dt[0]和dt[1]进行相互拷贝实现。

跳跃表

跳表是一种特殊的链表，对于每个Node可以指向下一个或其他多个节点。支持平均O(logN)的查找复杂度。跳跃表是有序集合的底层实现之一。

//跳表节点
typedef struct zskiplistNode{
    struct zskiplistNode *backward;

    double score;

    robj *obj;//成员对象

    struct zskiplistLevel{//层
        struct zskiplistNode *forward;

        unsigned int span;//跨度
    }level[];

}

//跳表信息
typedef struct zskiplist{
    struct sikplistNode *header, *tail;//头尾

    unsigned long length;//节点数

    int level;//层数
}

《Redis设计与实现》读书笔记 基础数据结构（一）