分类 "读书笔记" 下的文章

个人真的很喜欢这本书, 从对C语言一窍不通, 到发现C语言竟然如此简洁, 以至于我喜欢上了C! 对此前面的底层数据结构也读了几次, 大致整理了书里的内容, 后面的就粗略看了一下, 不再细细整理了.

Redis的设计与实现(1)-SDS简单动态字符串
Redis的设计与实现(2)-链表
Redis的设计与实现(3)-字典
Redis的设计与实现(4)-跳跃表
Redis的设计与实现(5)-整数集合
Redis的设计与实现(6)-压缩列表

整体的感悟吧, 觉得 Redis 的作者, 对每一块内存非常吝啬, 为了节省内存而制造出各种各样的编码和技巧. 阅读源码的过程中, 也学习到了宏的技巧, 比如说:

#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
    (encoding) = (ptr[0]); \
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)





阅读全文

压缩列表 (ziplist) 是列表键和哈希键的底层实现之一.

  1. 当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做列表键的底层实现.
  2. 当一个哈希键只包含少量键值对, 并且每个键值对的键和值要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做哈希键的底层实现.

1. 压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型 (sequential) 数据结构.
一个压缩列表可以包含任意多个节点 (entry) , 每个节点可以保存一个字节数组或者一个整数值.


阅读全文

整数集合(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;

阅读全文

  1. 1
  2. 2
  3. 3