1.1架构师图谱

Read More

前面的章节，介绍了Redis泳道的主要数据结构，比如简单动态字符串，双端列表，字典，压缩列表，整数集合等等。Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于数据结构创建了一个对象系统，这个系统包含字符串对象，列表对象，哈希对象，集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种前面说的数据结构。

对象的类型和编码

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键，另一个对象用作键值对的值。

1
2
3
4
5
6
7
8

type struct redisObject {
    // 类型
  	unsigned type:4;
  	// 编码
  	unsigned encoding:4;
  	// 指向底层实现数据结构的指针
  	void *ptr;
} robj;

类型

编码和底层实现

对象的prt指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定。encoding属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现。

每种类型的对象都至少使用了两种不同的编码。

压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键值包含少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，那么Redis就会使用压缩列表做列表键的底层实现。

另外，当一个哈希键值包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做哈希键的底层实现。

Read More

整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

Read More

跳跃表(skiplist)是一种有序数据结构，他通过在每个节点维持多个指向其他节点的指针，从来打到快速访问节点的目的。

跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树媲美，并且因为跳跃表的实现比平衡树更为简单，所以有不少程序都使用跳跃表来代替平衡树。

Redis使用跳跃表作为有序结合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中的成员(member)是比较长的字符串，Redis机会使用跳跃表来作为有序集合键的底层实现。和链表、字典等数据结构被广泛应用在Redis内部不同，Redis只在两个地方泳道了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

Read More

字典，又称符号表(symbol table)、关联数组(associative array)或映射(map)，是一种保存键值对的抽象数据结构

在字典中，一个键(key)可以和一个值(value)进行关联，这些关联的键和值就称为键值对。

字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对。

字典的实现

Redis字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

Read More

引言

在看redis原理的时候，看到链表结构中，用到了函数指针，想起了之前容易弄混的指针函数和函数指针，所以记录一下

函数指针和指针函数的区别

定义

• 函数指针是指向函数地址的指针，本质是一个指针
• 指针函数是返回类型是指针的函数，本质上是函数

如何区分

看星号是否被括号包含：被括号包含是函数指针，反之是指针函数。

Read More

每个链表和链表节点的实现

链表节点结构

1
2
3
4
5
6
7
8

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

链表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

dup、free、match成员用于实现多态链表所需的类型特定函数：

• dup函数用于复制链表节点所保存的值。
• free函数用于释放节点所保存的值。
• match函数用户对比链表节点所保存的值和另一个输入值是否相等。

Read More

Redis没有直接使用C语言传统的字符串表示（以空字符串结尾的字符数组），而是自己构建了一种名为动态字符串（simple dynamic string，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。Redis的数据库里面，包含字符串值的键值对在底层都是用SDS实现的；除此之外，SDS还被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是有SDS实现的。

Read More

通配符（glob）是 shell 中的一个比较重要的概念，可以认为是正则表达式的简化版本。通配符在字符串匹配和文件名搜索等方面非常有用。本篇只讲它在字符串匹配上的用法

通配符的基本用法

之前在讲字符串匹配判断时，通配符出现过，就是 *"$str"* 两边的星号。

1
2
3
4
5
6
7
8
9

% str1=abcd
% str2=bc
# 星号要在引号外边
% [[ $str1 == *"$str2"* ]] && echo good
good
# 注意带通配符的字符串必须放在右边
% [[ *"$str2"* == $str1 ]] && echo good

Read More