Redis数据库口试——数据结构范例知识
各人好，这里是Good Note，关注 公主号：Goodnote，专栏文章私信限时Free。本文详细先容Redis 提供的5种根本数据结构范例和4种特殊范例，除此之外，还有8种底层数据结构，每种结构范例有其特点和适用场景。https://i-blog.csdnimg.cn/direct/02e173146ca547f383d17a5860aaae34.png#pic_center
根本数据范例
1. String（字符串）
[*]简介：Redis 最根本的数据范例，一个 key 对应一个 value，支持二进制安全，可存储任意数据（如图片、序列化对象）。
[*]特点：
[*]最大可存储 512MB 数据。
[*]用于缓存、计数器、分布式 ID 生成等场景。
[*]常用下令：
[*]存储：SET key value、MSET key value
[*]获取：GET key、MGET key
[*]计数器使用：INCR key、DECR key、INCRBY key increment
[*]底层实现：
[*]使用 SDS（Simple Dynamic String） 存储，支持动态扩容，避免频繁内存分配，镌汰内存碎片。
二进制安全的核心是：将数据视为纯字节流，不做额外解释或处置处罚。在 Redis 和其他支持二进制安全的工具中，这种特性使得它们可以或许高效存储和处置处罚多样化的数据范例，确保数据的完备性和兼容性。
使用场景
缓存
可以缓存各种信息（字符串、图片、视频等），存储在 Redis 中作为缓存，减轻持久层的读写压力；或者将 session 存储在 Redis 中用于共享。
[*] 存储键值对：
[*]SET key value：存入键值对，覆盖旧值，无视范例。
[*]MSET key value ：批量存储字符串键值对。
[*] 获取键值对：
[*]GET key：根据键获取对应的值。
[*]MGET key ：批量获取字符串键值对。
[*] 删除与设置过期时间：
[*]DEL key：删除对应键的键值对。
[*]EXPIRE key seconds：设置指定键的有效时间。
计数器
Redis 是单线程模子，下令只能逐个实行，不会出现并发问题导致计数错误。例如，可用于统计文章阅读量。
[*]INCR key：使键对应的数字加 1。
[*]DECR key：使键对应的数字减 1。
[*]INCRBY key increment：使键的值加上指定增量。
[*]DECRBY key decrement：使键的值减去指定增量。
ID 生成器
在分布式系统中可以保证生成的序列号唯一。
[*]INCRBY orderId increment：将键对应的数字加上指定的增量值。
分布式锁
方法是否保举问题分析SETNX + EXPIRE不保举非原子使用，大概导致死锁。SET NX EX保举原子使用，避免死锁，更安全可靠。 SET NX EX 是现代 Redis 分布式锁的保举实现方式。
1. 使用 SETNX 下令 + EXPIRE 下令
[*] 过程：
[*]使用 SETNX 下令实验设置锁：SETNX lock:resource "unique_value"
[*]如果 SETNX 乐成，则设置锁的过期时间：EXPIRE lock:resource 10
[*] 问题：
[*]非原子使用：
[*]SETNX 和 EXPIRE 是两个独立的下令，实行时无法保证原子性。
[*]如果 SETNX 乐成后，客户端崩溃或网络异常，未能实行 EXPIRE，大概导致锁永久存在（死锁）。
[*] 状态：
[*]由于上述缺陷，这种方式 不保举使用。
[*]已被原子性更强的 SET NX EX 下令 取代。
2. 使用 SET NX EX 下令
[*] 过程：
[*]使用 SET 下令，同时指定：
[*]NX：仅当键不存在时设置。
[*]EX：设置键的过期时间（秒）。
SET lock:resource "unique_value" NX EX 10
[*] 长处：
[*]原子使用：
[*]SET NX EX 是单个下令，保证了加锁和设置过期时间的原子性。
[*]避免了非原子使用导致的死锁问题。
[*] 状态：
[*]保举使用，已成为 Redis 实现分布式锁的标准方式。
2. Hash（哈希）
[*]简介：键值对集合，类似于 HashMap，每个 key 是 field，value 是对应的值。
[*]特点：
[*]适合存储对象，如用户信息、购物车等。
[*]支持单个字段更新，节流空间。
[*]常用下令：
[*]存储：HSET key field value、HMSET key field value
[*]获取：HGET key field、HGETALL key
[*]增量使用：HINCRBY key field increment
[*]底层实现：
[*]小数据量时使用 ziplist（压缩列表），节流内存。
[*]大数据量时使用 hashtable（哈希表），支持快速的插入和查询使用。
[*] ziplist（压缩列表）：
[*]为了节流内存开销，小规模的 Hash 数据使用紧凑的压缩列表存储。
[*]长处：内存使用少少，适合字段数目少、数据简单的场景。
[*]缺点：随着字段数目或数据大小增长，查找效率降低。
[*] hashtable（哈希表）：
[*]当数据量增大或字段较多时，自动切换为哈希表实现。
[*]长处：查找效率高，时间复杂度为 O(1)。
[*]缺点：内存开销相对较大。
通过这两种实现方式，Redis 平衡了内存使用和性能，适应不同数据规模的需求。
切换条件 Redis 在以下情况下，自动将 Hash 的底层存储从 ziplist 切换为 hashtable：
[*]字段数目超出阈值：
[*]默认 hash-max-ziplist-entries=512，即当字段数目超过 512 时，切换为哈希表。
[*]单个字段或值的大小超出阈值：
[*]默认 hash-max-ziplist-value=64，即当字段或值的大小超过 64 字节时，切换为哈希表。
以上两个参数可以通过 Redis 设置文件进行调解，以适应具体业务场景。
3. List（链表/列表）
[*]简介：双向链表实现的列表，支持插入、删除使用，有序，可通过下标访问。
[*]特点：
[*]支持先进先出（FIFO）队列、消息队列等场景。时间轴（timeline）或者消息流：例如微博的时间轴，有人发布微博，用lpush加入时间轴，展示新的列表信息。
[*]插入和删除性能优异，API 丰富。
[*]常用下令：
[*]插入：LPUSH key value、RPUSH key value
[*]获取：LRANGE key start stop
[*]壅闭使用：BLPOP key timeout、BRPOP key timeout
[*]
[*]底层实现：
[*]使用 quicklist（以 ziplist 为节点的双链表），联合链表的灵活性和 ziplist 的内存高效。
总结
模式使用下令描述Stack (栈)LPUSH + LPOP后进先出（LIFO）。Queue (队列)LPUSH + RPOP先进先出（FIFO）。Capped CollectionLPUSH + LTRIM保持固定长度的列表。Message QueueLPUSH + BRPOP生产者-斲丧者消息队列。1. LPUSH + LPOP = Stack (栈)
[*]栈模子：后进先出（LIFO）。
[*]下令解释：
[*]LPUSH key value：将值插入到列表的左侧（头部）。
[*]LPOP key：从列表的左侧（头部）弹出并返回值。
[*]使用场景：实现撤销功能、递归算法中的辅助栈。
2. LPUSH + RPOP = Queue（队列）
[*]队列模子：先进先出（FIFO）。
[*]下令解释：
[*]LPUSH key value：将值插入到列表的左侧（头部）。
[*]RPOP key：从列表的右侧（尾部）弹出并返回值。
[*]使用场景：实现任务队列或哀求排队。
3. LPUSH + LTRIM = Capped Collection（有限集合）
[*]有限集合：限制列表的长度，仅保留最近的 N 个元素。
[*]下令解释：
[*]LPUSH key value：将值插入到列表的左侧（头部）。
[*]LTRIM key start stop：裁剪列表，仅保留索引范围内的元素（从 start 到 stop）。
[*]使用场景：实现固定长度的访问纪录、日记系统等。
4. LPUSH + BRPOP = Message Queue（消息队列）
[*]消息队列模子：支持壅闭等待，适合生产者-斲丧者模式。
[*]下令解释：
[*]LPUSH key value：将消息插入到队列的左侧（头部）。
[*]BRPOP key timeout：从队列的右侧（尾部）弹出消息，若队列为空则壅闭直到超时。
[*]如果 timeout=0，则表现永不超时，一直壅闭直到有新消息。
[*]使用场景：任务调度系统，斲丧者从队列中获取任务。
4. Set（集合）
[*]简介：保存多个字符串的集合，元素唯一且无序。
[*]特点：
[*]支持集合运算（交集、并集、差集）。
[*]常用于标签系统、点赞、挚友保举等。
[*]常用下令：
[*]添加：SADD key member、SUNION key
[*]查询：SMEMBERS key、SISMEMBER key member
[*]集合运算：SINTER key （交集）、SUNION key （并集）
[*]底层实现：
[*]使用 hashtable 存储，大数据量时支持高效的查找、插入和删除。
[*]小规模集合使用 intset 存储（仅包罗整数）。
Redis 根据集合中元素的数目和范例，自动在 intset 和 hashtable 之间切换：
[*]如果集合中的所有元素都是整数，且数目较少，则使用 intset。
[*]如果集合中的元素范例不为整数，或数目超过设置的阈值（默认 512 个），则切换为 hashtable。
5. Sorted Set（有序集合）
[*]简介：与 Set 类似，但每个元素有一个关联的分数（score），按分数排序。
[*]特点：
[*]适用于排行榜、耽误队列等场景。
[*]分数可以重复，但元素值必须唯一。
[*]常用下令：
[*]添加：ZADD key score member
[*]获取：ZRANGE key start stop （正序）、ZREVRANGE key start stop （倒序）
[*]增量使用：ZINCRBY key increment member
[*]底层实现：
[*]当 ZSet 较小时，Redis 使用 Ziplist 实现，节流内存。
[*]当 ZSet 较大时，Redis 切换到使用 跳跃链表（Skiplist） 和 哈希表（Hash Table） 组合实现：
[*]zskiplist 提供高效的范围查找和排序。
[*]hashtable 用于快速查找元素。
底层实现：
当满足以下两个条件时，Redis 会使用 ziplist来实现 ZSET：
[*] 元素数目小于 128：如果集合中存储的元素较少，使用 ziplist 更加高效。它通过压缩数据来节流内存。
[*] 每个元素的长度小于 64 字节：如果每个元素的长度较短（例如，成员字符串很短），那么 ziplist 的压缩效率就很高。
[*] ziplist 的结构：在 ziplist 中，ZSET 的成员和分数（score）是交替存储的，数据压缩非常紧凑。
当 ZSET 的元素数目超过肯定的阈值（例如超过 128 个元素），或者单个元素的长度较长时，Redis 会自动使用 skiplist（跳跃链表）和哈希表（Hash Table）的组合 来实现 ZSET。这是 Redis ZSET 中的默认数据结构。
[*] zskiplist（跳跃表）：
[*]作用：实现有序集合中的元素排序和范围查找。
[*]特点：
[*]跳跃表是一种随机化的数据结构，类似于平衡树，但实现更简单。
[*]支持按照分数（score）排序的高效使用，如范围查询、按分数排序等。
[*]跳跃表中每个节点包罗：
[*]成员元素（member）。
[*]分数值（score）。
[*]前后指针（用于维护链表关系）。
[*]时间复杂度：
[*]插入、删除、范围查找：O(log N)。
[*] hashtable（哈希表）：
[*]作用：提供成员元素到分数值的快速映射。
[*]特点：
[*]哈希表存储了每个成员元素和对应的分数（member -> score）。
[*]用于快速查找某个成员是否存在，以及其分数值。
[*]时间复杂度：
[*]查找、插入、删除：O(1)。
zskiplist 和 hashtable 的组合
[*] 为什么需要组合两种结构：
[*]跳跃表（zskiplist）：
[*]支持按分数排序的快速使用。
[*]能高效实现范围查询和按分数排序的功能。
[*]哈希表（hashtable）：
[*]提供快速的元素查找和分数更新。
[*]弥补跳跃表在精确查找上的性能不敷。
[*] 两者协同工作：
[*]插入或删除一个元素时：
[*]在 hashtable 中存储或删除成员和分数的映射。
[*]同时在 zskiplist 中插入或删除节点，保持排序。
[*]查询元素是否存在时：
[*]使用 hashtable 进行快速查找。
[*]进行范围查询或排序时：
[*]使用 zskiplist 高效实现按分数排序或范围扫描。
优势分析
[*]跳跃表的排序和范围使用：
[*]允许快速实现按分数排序和范围查找。
[*]时间复杂度为 O(log N)。
[*]哈希表的快速查找：
[*]提供成员到分数的直接映射，查找效率为 O(1)。
[*]内存效率：
[*]跳跃表的结构简单，节点的动态分配优化了内存使用。
[*]哈希表避免了重复排序，进步了效率。
特殊数据范例
6. Bitmaps（位图）
[*]概述：以位的形式存储数据，每个键对应一个字符串，可以使用字符串的二进制位。
[*]特点：
[*]位使用效率高，适合存储二进制状态。
[*]最大大小同字符串（512 MB）。
[*]常见用途：
[*]用户签到（按日期设置某天状态）。
[*]在线状态纪录。
[*]常用下令：
[*]SETBIT key offset value：设置指定偏移位的值。
[*]GETBIT key offset：获取指定偏移位的值。
[*]BITCOUNT key：统计所有位为 1 的数目。
7. HyperLogLog
[*]概述：一种基于概率的数据结构，用于估算集合的基数（去重后的元素数目）。
[*]特点：
[*]适合存储大规模数据，内存占用固定为 12 KB。
[*]结果是近似值，但偏差在 0.81% 以内。
[*]常见用途：
[*]网站 UV 统计（独立访客）。
[*]近似计数。
[*]常用下令：
[*]PFADD key element：添加元素。
[*]PFCOUNT key：返回估算的基数值。
8. Geo（地理位置）
[*]概述：用于存储地理位置信息（经纬度），并支持基于地理位置的使用。
[*]特点：
[*]可以计算两点之间的距离。
[*]支持范围查询（如附近的人）。
[*]常见用途：
[*]附近位置查询。
[*]地理信息存储。
[*]常用下令：
[*]GEOADD key longitude latitude member：添加地理位置。
[*]GEODIST key member1 member2：计算两点间距离。
[*]GEORADIUS key longitude latitude radius：按范围查询地理位置。
9. Streams（流）
[*]概述：Redis 的消息队列实现，用于生产者-斲丧者模子。
[*]特点：
[*]支持斲丧者组、消息确认。
[*]可以持久化消息。
[*]常见用途：
[*]及时日记。
[*]消息分发。
[*]常用下令：
[*]XADD key * field value：添加消息。
[*]XRANGE key start end：按范围读取消息。
[*]XREADGROUP：斲丧者组读取消息。
底层数据范例
Redis 对用户暴露的根本范例 Value Type（如字符串、哈希、列表等）实际是通过底层多种高效数据结构实现的。这些数据结构在性能、内存占用、以及适用场景上各有特点，以下为详细先容：
Redis 的 Value Type 基于以下底层数据结构实现：
[*]SDS（Simple Dynamic String）：简单动态字符串，支持高效扩容。
[*]LinkedList：双向链表。
[*]HashTable：哈希表，支持平滑扩容。
[*]zskiplist：跳跃表，支持排序和范围查询。
[*]IntSet：整数集合，存储小规模整数。
[*]ZipList：压缩列表，节流内存。
[*]QuickList：联合链表和压缩列表，兼顾内存和效率。
[*]ZipMap：轻量级字典，适合小规模场景。
以下是 Redis 的 8 种底层数据结构及其用途汇总：
底层数据结构数据范例使用场景特点/用途SDSString存储字符串，支持动态扩容，二进制安全。intsetSet存储小规模整数集合，内存节流。ziplistHash、List、Sorted Set小数据量场景，一连内存存储，节流内存。linkedlistList（早期实现）双向链表，已被 quicklist 替换。quicklistList链表+ziplist 的联合，内存高效、使用灵活。hashtableHash、Set大数据量场景，提供 O(1) 的查找性能。zskiplistSorted Set跳跃表，支持范围查询和排序。dictHash、Set、Sorted Set通用哈希表，动态扩容，支持快速查找。 Redis 的灵活实现联合了不同数据结构的长处，针对不同场景优化性能与内存占用。
SDS（Simple Dynamic String）
[*]简介：
SDS 是 Redis 用于存储字符串的动态字符串结构，可以或许支持二进制数据和动态扩容。
[*]特点：
[*]二进制安全：可以存储任意二进制数据（如图片、序列化对象）。
[*]动态扩容：自动扩展和缩小，避免频繁的内存分配。
[*]高效使用：纪录已用长度和未用空间，镌汰字符串拼接时的性能斲丧。
[*]结构：struct sdshdr {
int len; // 已使用长度
int free; // 未使用长度
char buf[]; // 字符数组
};
[*]应用场景：
[*]用于实现 Redis 的字符串范例。
[*]实现键值对中的键和某些简单值。
LinkedList（链表）
[*]简介：
Redis 的链表是一个通用的双向链表，节点通过指针毗连。
[*]特点：
[*]双向链表：每个节点包罗前驱和后继指针。
[*]通用性强：节点的数据由 void* 指针指向，可以存储任意范例数据。
[*]灵活性高：适合频繁插入和删除使用的场景。
[*]结构：typedef struct listNode {
struct listNode *prev;// 前向指针
struct listNode *next;// 后向指针
void *value; // 节点值
} listNode;
[*]应用场景：
[*]实现早期 Redis 的列表范例（已被 quicklist 替换）。
[*]用于其他需要链表结构的功能。
HashTable
[*]简介：
Redis 的字典使用双哈希表实现，支持高效的查找、插入和删除使用。
[*]特点：
[*]双哈希表：一个用于存储数据，另一个在扩容时用于渐进式数据迁移。
[*]平滑扩容：通过渐进式扩展镌汰扩容对性能的影响。
[*]结构：typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 掩码，用于计算索引
unsigned long used; // 已用节点数量
} dictht;
[*]应用场景：
[*]实现 Redis 的哈希范例。
[*]用于内部数据存储，如保存键空间。
zskiplist（跳跃表）
[*]简介：
跳跃表是一种基于链表的有序数据结构，支持高效的范围查询和排序。
[*]特点：
[*]多层索引：通过额外的索引层进步查找效率。
[*]简单高效：实现简单，性能靠近平衡树。
[*]结构：typedef struct zskiplistNode {
double score; // 分数
robj *obj; // 成员对象
struct zskiplistNode *backward; // 后向指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 前向指针
unsigned int span; // 层跨度
} level[];
} zskiplistNode;
[*]应用场景：
[*]实现 Redis 的有序集合（Sorted Set）范例。
intset（整数集合）
[*]简介：
Redis 的整数集合是一个有序的整数数组，用于存储小规模整数集合。
[*]特点：
[*]有序存储：通过二分查找快速定位元素。
[*]节流内存：自动根据数据范例调解存储大小（如 int16、int32、int64）。
[*]结构：typedef struct intset {
uint32_t encoding; // 当前编码方式
uint32_t length; // 元素数量
int8_t contents[]; // 数据内容
} intset;
[*]应用场景：
[*]用于实现 Redis 的 Set 范例（当集合较小时）。
ziplist（压缩列表）
[*]简介：
压缩列表是一种内存紧凑型的双向链表，用于存储小规模数据。
[*]特点：
[*]节流内存：数据紧凑存储，适合存储少量元素。
[*]使用简单：支持顺序遍历、插入和删除使用。
[*]结构：struct ziplist {
uint32_t zlbytes; // 列表总字节数
uint32_t zltail; // 表尾偏移量
uint16_t zllen; // 列表元素数量
unsigned char entries[]; // 数据条目
};
[*]应用场景：
[*]实现 Redis 的列表和哈希范例（当数据量较小时）。
quicklist（快速列表）
[*]简介：
quicklist 是 ziplist 和链表的联合体，兼顾内存使用率和使用效率。
[*]特点：
[*]高效存储：链表中的每个节点存储一个 ziplist。
[*]灵活性强：既支持高效的插入删除，又节流内存。
[*]结构：typedef struct quicklistNode {
unsigned char *zl; // ziplist 数据
struct quicklistNode *prev; // 前驱节点
struct quicklistNode *next; // 后继节点
} quicklistNode;
[*]应用场景：
[*]实现 Redis 的列表范例（List）。
zipmap（压缩字典）
[*]简介：
zipmap 是一种轻量级的哈希表结构，用于小规模场景。
[*]特点：
[*]内存占用小：适合存储少量键值对。
[*]直接持有数据：不支持嵌套结构。
[*]结构：
[*]由紧凑的键值对序列构成，节流内存。
[*]应用场景：
[*]实现 Redis 的哈希范例（当数据量较小时）。
redisObject：衔接底层数据结构与 Value Type 的桥梁
在 Redis 中，redisObject 是一个核心的数据结构，主要用于衔接 Redis 的 Value Type（数据范例） 和 底层存储实现。每个 Redis 中的 Key 和 Value 实际上都是一个 redisObject 实例。
redisObject 的结构
redisObject 的主要结构如下：
typedef struct redisObject {
unsigned type:4; // 数据类型（Value Type），如 String、Hash、List、Set、ZSet。
unsigned encoding:4; // 数据的底层编码类型，如 raw、int、ziplist、hashtable。
unsigned lru:24; // 最近一次访问时间（LRU，用于内存管理）。
int refcount; // 引用计数，用于内存回收。
void *ptr; // 指向具体数据的指针。
} robj;
redisObject 的关键字段
[*] type（数据范例）：
[*]表现 Value 的逻辑范例。
[*]包罗：String、Hash、List、Set、ZSet 等。
[*]决定了 Redis 对外暴露的使用接口。
[*] encoding（底层实现编码）：
[*]指定该数据范例使用的底层存储结构。
[*]不同的数据范例大概有多种底层实现，例如：
[*]String 范例：raw（平凡字符串）或 int（整型优化）。
[*]Hash 范例：ziplist（压缩列表）或 hashtable（哈希表）。
[*]List 范例：quicklist。
[*]Redis 会根据数据规模自动选择最符合的底层结构。
[*] lru（最近访问时间）：
[*]用于纪录该对象的最近访问时间（以秒为单位）。
[*]配合 Redis 的 LRU 内存镌汰计谋，决定是否需要将对象从内存中删除。
[*] refcount（引用计数）：
[*]用于引用管理，避免重复内存分配。
[*]当引用计数为 0 时，Redis 会回收该对象的内存。
[*] ptr（指针）：
[*]指向实际存储数据的地址。
[*]数据存储的具体形式由 encoding 决定。
redisObject 的作用
[*] 毗连 Value Type 和底层实现：
[*]RedisObject 的 type 表现数据的逻辑范例。
[*]RedisObject 的 encoding 表现底层实现，负责优化内存和性能。
[*]通过 redisObject，Redis 能在不改变逻辑接口的前提下，动态切换底层实现。
[*] 内存管理：
[*]使用 refcount 和 lru 实现高效的内存管理。
[*]支持对象的生命周期管理和 LRU 镌汰机制。
[*] 进步灵活性：
[*]RedisObject 的多层抽象允许 Redis 在各种场景中灵活优化性能，例如：
[*]小数据用压缩结构（如 ziplist）节流内存。
[*]大数据用高效结构（如 hashtable）进步使用速率。
历史文章
MySQL数据库
[*]MySQL数据库笔记——数据库三范式
[*]MySQL数据库笔记——存储引擎（InnoDB、MyISAM、MEMORY、ARCHIVE）
[*]MySQL数据库笔记——常见的几种锁分类
[*]MySQL数据库笔记——索引先容
[*]MySQL数据库笔记——事务先容
[*]MySQL数据库笔记——索引结构之B+树
[*]MySQL数据库笔记——索引潜规则（回表查询、索引覆盖、索引下推）
[*]MySQL数据库笔记——索引潜规则（最左前缀原则）
[*]MySQL数据库笔记——常见慢查询优化方式
[*]MySQL数据库笔记——日记先容
[*]MySQL数据库笔记——多版本并发控制MVCC
[*]MySQL数据库笔记——主从复制
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]