Posts

String 介绍 最基本的数据类型，一个 key 对应一个 value 底层结构 SDS 应用场景 缓存 计数器 常用命令 命令 描述 SET key value 设置 key 对应的值为 value GET key 获取 key 对应的值 DEL key 删除 key 对应的值 INCR key key 对应的值加 1 DECR key key 对应的值减 1 INCRBY key increment key 对应的值加 increment DECRBY key decrement key 对应的值减 decrement List 介绍 双端链表，支持从两端插入和删除 底层结构 QuickList 应用场景 消息队列 常用命令 命令 描述 LPUSH key value1 [value2 … valueN] 从左边插入一个或多个值 RPUSH key value1 [value2 … valueN] 从右边插入一个或多个值 LPOP key 从左边删除一个值 RPOP key 从右边删除一个值 LINDEX key index 获取指定索引的值 LRANGE key start stop 获取指定范围的值 Hash 介绍 哈希表，类似于 Java 中的 HashMap...

结构 /* ZSETs use a specialized version of Skiplists */ typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; ele: 持有数据，是一个 sds 结构 score: 分值 backward: 指向前一个节点 level: 层级，包含 forward 和 span 两个字段 forward: 指向下一个节点 span: 记录跨度，即当前节点到下一个节点的距离 优势 插入、删除、查找的时间复杂度都是 O(logN) 有序，可以使用跳表进行范围查询

结构 typedef struct dict { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dict; typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; } v; struct dictEntry *next; } dictEntry; key: 键 val: 值，值可以是一个指针，也可以是 uint64_t 或 int64_t 类型的整数 next: 指向下一个节点，形成链表 哈希算法 // 使用字典设置的哈希函数，计算键 key 的哈希值 hash = dict->type->hashFunction(key); // 使用哈希表的 sizemask 属性和第一步得到的哈希值，计算索引值 index = hash & dict->ht[x].sizemask; 关注点 解决哈希冲突：拉链表，使用 *next 指向下一个具有相同索引值的哈希表节点 扩容和缩容：根据原哈希表已使用的空间扩大一倍或缩小一半 扩容条件： 没有执行 BGSAVE 或 BGREWRITEAOF 命令，且负载因子大于 1 在执行 BGSAVE 或 BGREWRITEAOF 命令，负载因子大于 5 渐进式 rehash：在 rehash 的过程中，新哈希表和旧哈希表同时存在，查询时先查询新哈希表，再查询旧哈希表，写入时只写入新哈希表

结构 双向链表，每一个节点都是一个 ziplist /* Node, quicklist, and Iterator are the only data structures used currently. */ /* quicklistNode is a 32 byte struct describing a ziplist for a quicklist. * We use bit fields keep the quicklistNode at 32 bytes. * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k). * encoding: 2 bits, RAW=1, LZF=2. * container: 2 bits, NONE=1, ZIPLIST=2. * recompress: 1 bit, bool, true if node is temporarry decompressed for usage....

结构 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> zlbytes: uint32_t，记录整个 ziplist 的字节数 zltail: uint32_t，记录 ziplist 中最后一个节点的偏移量 zllen: uint16_t，记录 ziplist 中节点的数量 entry: ziplist 中的节点，包含 prevlen、encoding、entry-data（可能没有） zlend: uint8_t，标识 ziplist 的结束 Entry 结构 <prevlen> <encoding> <entry-data>（可能没有） prevlen: 表示前一个 entry 的长度 如果前一个 entry 的长度小于 254 字节，prevlen 占用 1 字节，记录前一个 entry 的长度 如果前一个 entry 的长度大于等于 254 字节，prevlen 占用 5 字节，第一个字节为 0xFE，后面 4 字节记录前一个 entry 的长度 encoding: 表示当前 entry 的类型和长度 前两位表示类型，当前两位为 11 时，表示 entry 为 int 类型，否则为 string 类型 entry-data: 实际存储的数据，如果是 int 类型，entry-data 会合并到 encoding 中，否则会单独存储在 entry-data 中 优势 利用 encoding 字段来细化存储空间长度，压缩存储空间 元素长度不相同，所以用 prevlen 字段满足从后向前遍历的需求 缺点 不预留空间，每次写操作都会进行内存分配 如果节点扩容，会导致它后面的节点的 prevlen 需要重新计算