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

整数集合 (intset) 是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_t , int32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素.

1. 整数集合的定义

每个 intset.h/intset 结构表示一个整数集合:

typedef struct intset {
  // 编码方式
  uint32_t encoding;
  // 集合包含的元素数量
  uint32_t length;
  // 保存元素的数组
  int8_t contents[];
} intset;

阅读全文

跳跃表 (skiplist) 是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的.

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

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

Redis 使用跳跃表作为有序集合键的底层实现之一: 如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员 (member) 是比较长的字符串时, Redis 就会使用跳跃表来作为有序集合键的底层实现.

和链表, 字典等数据结构被广泛地应用在 Redis 内部不同, Redis 只在两个地方用到了跳跃表, 一个是实现有序集合键, 另一个是在集群节点中用作内部数据结构, 除此之外, 跳跃表在 Redis 里面没有其他用途.

阅读全文

Redis 的数据库使用字典实现, 对数据库的增, 删, 查, 改也是构建在对字典的操作之上的.

字典是哈希键的底层实现之一: 当一个哈希键包含的键值对比较多, 又或者键值对中的元素都是比较长的字符串时, Redis 将会使用字典作为哈希键的底层实现.

1. 哈希表

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

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

阅读全文

链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现.

除了链表键之外, 发布与订阅, 慢查询, 监视器等功能也用到了链表, Redis 服务器还使用链表保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer).

1. 链表的定义

每个链表节点使用一个 adlist.h/listNode 结构来表示:

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

使用 adlist.h/list 来操作链表会更方便

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

可见, 它是一个双向链表.

阅读全文

一开始以为 webpack-bundle-analyzer 是什么插件...后来才发现, 原来我用vue-cli安装的包, 在构建的时候, 多加个参数就可以了, 它还自动把浏览器打开了...

# build for production and view the bundle analyzer report
npm run build --report

无需配置, 只需一个参数, over...