\"Redis的设计与实现（第一版）\

第一部分：内部数据结构 3 1.1 简单动态字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 sds 的用途 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Redis 中的字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 优化追加操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.4 sds 模块的 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 双端链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 双端链表的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 双端链表的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 迭代器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 字典的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 字典的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.3 创建新字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.4 添加键值对到字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.5 添加新元素到空白字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.6 添加新键值对时发生碰撞处理 . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.7 添加新键值对时触发了 rehash 操作 . . . . . . . . . . . . . . . . . . . . . 22 1.3.8 Rehash 执行过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.9 渐进式 rehash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.3.10 字典的收缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.3.11 字典其他操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.3.12 字典的迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.3.13 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.4 跳跃表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.4.1 跳跃表的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4.2 跳跃表的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.4.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2 第二部分：内存映射数据结构 37 2.1 整数集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.1 整数集合的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.2 数据结构和主要操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.1.3 intset 运行实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.1.4 升级 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.5 关于升级 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 i 迅捷PDF编辑器2.1.6 关于元素移动 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.7 其他操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.8 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2 压缩列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.1 ziplist 的构成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2.2 节点的构成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.2.3 创建新 ziplist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.4 将节点添加到末端 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.5 将节点添加到某个/某些节点的前面 . . . . . . . . . . . . . . . . . . . . . 52 2.2.6 删除节点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.7 遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.8 查找元素、根据值定位节点 . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.9 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54