如何在Redis中高效地合并非重叠集合？

Question

我有一个使用场景，我确信我的Redis存储中的一些集合是不相交的。由于我的一些集合非常大，因此它们的sunion或sunionstore需要很长时间。Redis是否提供处理这种联合的功能？

或者，如果有一种方法可以在Redis中添加元素到集合中而无需在每次插入之前检查唯一性，那么它可以解决我的问题。

- Pirooz

Answer 1

实际上，没有必要使用这样的功能，因为操作的相对成本较高。当您构建Redis对象（例如集合或列表）时，成本不是由数据结构管理（哈希表或链表）主导的，因为单个插入操作的摊销复杂度为O（1）。成本由所有项目的分配和初始化（即集合对象或列表对象）主导。当您检索这些对象时，成本由输出缓冲区的分配和格式化主导，而不是数据结构中的访问路径。因此，绕过集合的唯一性属性不会带来显着的优化。如果集合是不相交的，则通过替换成多个SMEMBERS命令的管道来检索各个集合（并在客户端端构建联合）可以优化SUNION命令。优化SUNIONSTORE实际上并不可行，因为不相交的集合是性能最差的情况。性能受结果项数的支配，因此共同项越少，响应时间就越长。

- Didier Spezia

---

SUNIONSTORE的时间复杂度是O(N)，其中N是元素总数，无论有多少个共同项（若要知道其是否为共同项，则必须读取它）。您可能会将其与SINTERSTORE混淆，后者的时间复杂度为O(N*M)，其中N是最小集合的基数，M是集合数量。 - Ofir Luzon

我在谈论“单个”操作的成本。SUNIONSTORE之所以是O(n)，是因为单个插入的成本是O(1)。我的回答实际上与并集有关，而不是交集。 - Didier Spezia

请查看此处：https://github.com/antirez/redis/blob/73a809b1591378e1042a1028d0b8e10217e6e7c7/src/t_set.c#L797 - Ofir Luzon