数据结构

Redis 很快，但“快”并不等于所有命令都是 O(1)。 一次 GET 通常很轻，一次 ZRANGE 可能返回十万个成员，一次 SINTER 可能扫描几个大集合，一次 DEL 也可能为了释放大 key 在主线程上忙很久。它们都只是一条 Redis 命令，对实例造成的压力却完全不同。 这也是线上 Redis 延迟偶尔尖刺时最容易被忽略的地方：QPS 没有明显上涨，CPU 看起来也不算很高，但某个请求做了一次与数据规模相关的 O(N) 操作，后面的请求就一起排队了。 这篇文章按 Redis 的常用数据类型整理时间复杂度。目的不是背完整张命令表，而是学会看到命令时迅速判断两件事：它会扫描多少数据，又会返回多少数据。 如果还不熟悉 Hash、quicklist、intset、listpack 和 skiplist 的关系，可以先看Redis 底层数据结构。底层结构正是这些复杂度的来源。 读复杂度之前，先认识几个变量 后面的表格会反复使用这些字母： 变量 含义 K 一次命令传入的 key 数量 N 当前集合、列表、Hash 或 ZSet 的元素总数 M 本次返回、删除或处理的元素数量 S 为了到达起始位置需要跨过的元素数量 B 需要读取、复制或传输的字节数 比如 ZRANGE rank 0 9 的复杂度是 O(log N + M)：先在有序结构中定位起点，再返回 M 个成员。排行榜里有一百万个人并不可怕，只取前十名依然很轻；真正危险的是 ZRANGE rank 0 -1，因为这时 M 也变成了一百万。 还有三个容易被大 O 记号藏起来的事实。 ...

很多人第一次学 Redis，记住的是五种常用类型：String、List、Hash、Set、ZSet。再往后背面试题，又会遇到 SDS、quicklist、listpack、intset、skiplist、hashtable。 这些名字放在一起很容易让人迷糊：Redis 不是 key-value 数据库吗？为什么一个 Hash 后面还会有 listpack 和 hashtable 两种实现？为什么同样是 Set，有时是 intset，有时又变成哈希表？ 真正要理解的不是“Redis 有哪些数据结构”这张清单，而是一个更具体的问题： Redis 为什么要让同一种对外类型，在不同场景下切换不同的内部编码？ 顺着这个问题往下看，Redis 的底层数据结构会清楚很多。它不是为了把实现弄复杂，而是在内存、CPU、查询速度、扩容成本之间做了一组很工程化的取舍。 写这篇文章时（2026 年 7 月，版本信息核对于 7 月 21 日），Redis Open Source 的最新稳定版是 8.8.0，2026 年 5 月 25 日 GA，预发布阶段亮相的新数据结构 Array 也在这一版正式落地；8.6 线的最新补丁是 8.6.4。 从底层数据结构这条线看，Redis 8.6 以来最值得关注的不是“又多背几个结构名”，而是大 Hash、大 ZSet 的内存继续被优化，以及 Stream 幂等写入、HOTKEYS、key 内存大小直方图、LRM 淘汰策略这些贴近日常排查的新能力。这些在后文对应的小节里都会具体展开。 对外类型和内部编码不是一回事 平时我们写 Redis 命令，面对的是对外类型： SET name bole LPUSH queue a b c HSET user:1 name bole age 18 SADD tags redis cache ZADD rank 100 alice 这些命令分别对应 String、List、Hash、Set、ZSet。但 Redis 在内存里不会只保存“这是一个 Hash”这么简单的信息。 ...

如果一个接口被大量查询不存在的数据，比如用户不断请求不存在的商品 ID、缓存里没有的用户 ID，系统很容易被拖进一个尴尬局面：缓存没命中，请求继续打到数据库；数据库查不到，下一次同样的请求又会重复发生。 这类问题的关键不是“如何更快地查到数据”，而是先回答一个更便宜的问题：这个东西是不是一定不存在？ 布隆过滤器解决的正是这个问题。它不能像哈希集合那样给出完全精确的答案，但它能用很少的内存，很快告诉你： 如果结果是“不存在”，那它一定不存在。 如果结果是“存在”，那它只是可能存在。 这个“可能”就是布隆过滤器最重要的取舍。它用少量误判，换来了很高的空间效率。 先从一个普通集合说起 假设我们要记录 1 亿个已经注册过的用户 ID，最直接的做法是把这些 ID 放进一个集合： registered_users = set() registered_users.add("user:10086") if "user:10086" in registered_users: print("exists") 这个方案很好理解，也很精确。但问题是：集合为了支持快速查询，通常不只存储原始元素，还要维护哈希表、桶、指针、扩容状态等额外结构。数据量一大，内存会明显上去。 如果我们的目标只是提前过滤掉明显不存在的请求，真的需要保存完整的字符串吗？ 布隆过滤器的答案是：不需要。它只保存一些 bit。 布隆过滤器的直觉 可以把布隆过滤器想成一个很大的位图，也就是一串只包含 0 和 1 的数组： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 普通位图通常要求元素能直接映射成整数位置，比如数字 13 就对应第 13 个 bit。但现实里的元素可能是字符串、URL、邮箱、订单号，不一定能直接当数组下标。 布隆过滤器在中间加了一层哈希函数。 对于一个元素，它不用一个位置表示，而是用多个哈希函数算出多个位置： element = "user:10086" hash1(element) -> 3 hash2(element) -> 9 hash3(element) -> 14 插入这个元素时，就把这些位置都置为 1： ...

如果让你记录“今天哪些用户登录过”，最直接的想法可能是放进一个集合： logged_in_users = set() logged_in_users.add(10086) 这样当然能用。但如果用户 ID 范围很大、查询又特别频繁，集合会带来不少额外开销。有没有一种更省空间的办法？ 位图，也就是 Bitmap，解决的就是这类问题：用一个 bit 表示一个状态。这个状态通常只有两种结果：有或没有、是或否、出现过或没出现过。 位图到底是什么 先从一个字节说起。 一个字节有 8 个 bit： 0 0 0 0 0 0 0 0 每个 bit 都可以表示一个编号是否存在。比如我们用 bit 记录数字是否出现过： bit 0 表示数字 0 是否出现 bit 1 表示数字 1 是否出现 bit 2 表示数字 2 是否出现 ... bit 7 表示数字 7 是否出现 如果数字 3 出现过，就把第 3 个 bit 置为 1： 0 0 0 0 1 0 0 0 ↑ 数字 3 这里约定 bit 从右往左数：最右边是 bit 0，往左依次是 bit 1、bit 2……和二进制数的书写习惯一致。 ...