程序员数学03：集合论 - Redis与SQL

本文是《程序员数学扫盲课》系列文章

← 上一篇：程序员数学02：对数Log – 数据库索引 | → 下一篇：程序员数学04：图论 – 微服务依赖管理

TL;DR

为什么Redis的SINTER能瞬间找出共同好友？为什么SQL的JOIN有时候会把数据库搞崩？答案都藏在集合论里。这篇文章用Go代码带你搞懂交集、并集、差集，看完你会发现：集合操作就是数组的高级玩法。

系列导航

《程序员数学扫盲课》系列：
1. 破冰篇：数学符号就是代码
2. 对数Log：数据库索引的魔法
3. 集合论：玩转Redis与SQL（本篇）
4. 图论基础：微服务依赖管理
5. 概率论：系统可用性计算
6. 统计学：P99延迟与监控报警
7. 线性代数入门：推荐系统的数学基础
8. 哈希与模运算：负载均衡算法
9. 信息论：数据压缩与编码
10. 组合数学：容量规划与性能预估

一、集合论到底是什么？

先说重点：集合就是”不重复的一堆东西”。

1.1 从生活场景说起

假设你有两个微信群：

群A（技术群）：

{张三, 李四, 王五, 赵六}

群B（同学群）：

{李四, 王五, 孙七, 周八}

现在你想知道：
– 谁既在技术群又在同学群？ → 交集（∩）
– 两个群的所有人？ → 并集（∪）
– 只在技术群不在同学群的人？ → 差集（-）

这就是集合论的核心操作。

1.2 集合的数学符号

看到这些符号别慌：

1.3 为什么后端程序员必须懂集合论？

因为所有的数据操作都是集合操作：

你看，集合论无处不在。不懂集合论，就看不懂Redis和SQL的底层逻辑。

二、基础集合操作：用Go实现

2.1 交集（Intersection）：找共同元素

数学符号：

A ∩ B = {x | x ∈ A 且 x ∈ B}

翻译成人话：既在A又在B的元素。

Go代码实现：

package main

import "fmt"

// 交集：找出两个切片的共同元素
func Intersection(a, b []int) []int {
    // 用map记录a中的元素
    set := make(map[int]bool)
    for _, v := range a {
        set[v] = true
    }

    // 找出b中也在a中的元素
    result := []int{}
    seen := make(map[int]bool) // 防止重复
    for _, v := range b {
        if set[v] && !seen[v] {
            result = append(result, v)
            seen[v] = true
        }
    }

    return result
}

func main() {
    techGroup := []int{1001, 1002, 1003, 1004} // 张三、李四、王五、赵六
    classGroup := []int{1002, 1003, 1005, 1006} // 李四、王五、孙七、周八

    common := Intersection(techGroup, classGroup)
    fmt.Printf("共同好友: %v\n", common) // [1002 1003] (李四、王五)
}

时间复杂度：O(n + m)，其中n和m是两个数组的长度。

2.2 并集（Union）：合并去重

数学符号：

A ∪ B = {x | x ∈ A 或 x ∈ B}

翻译成人话：A和B的所有元素，重复的只保留一个。

Go代码实现：

// 并集：合并两个切片并去重
func Union(a, b []int) []int {
    set := make(map[int]bool)

    // 添加a的所有元素
    for _, v := range a {
        set[v] = true
    }

    // 添加b的所有元素
    for _, v := range b {
        set[v] = true
    }

    // 转换为切片
    result := []int{}
    for k := range set {
        result = append(result, k)
    }

    return result
}

func main() {
    techGroup := []int{1001, 1002, 1003, 1004}
    classGroup := []int{1002, 1003, 1005, 1006}

    all := Union(techGroup, classGroup)
    fmt.Printf("所有人: %v\n", all) // [1001 1002 1003 1004 1005 1006]
}

时间复杂度：O(n + m)

2.3 差集（Difference）：A有但B没有

数学符号：

A - B = {x | x ∈ A 且 x ∉ B}

翻译成人话：只在A不在B的元素。

Go代码实现：

// 差集：A中有但B中没有的元素
func Difference(a, b []int) []int {
    // 用map记录b中的元素
    setB := make(map[int]bool)
    for _, v := range b {
        setB[v] = true
    }

    // 找出a中不在b中的元素
    result := []int{}
    for _, v := range a {
        if !setB[v] {
            result = append(result, v)
        }
    }

    return result
}

func main() {
    techGroup := []int{1001, 1002, 1003, 1004}
    classGroup := []int{1002, 1003, 1005, 1006}

    onlyTech := Difference(techGroup, classGroup)
    fmt.Printf("只在技术群: %v\n", onlyTech) // [1001 1004] (张三、赵六)
}

时间复杂度：O(n + m)

2.4 完整示例：社交网络场景

package main

import (
    "fmt"
    "sort"
)

type User struct {
    ID   int
    Name string
}

type SocialNetwork struct {
    users map[int]*User
}

func NewSocialNetwork() *SocialNetwork {
    return &SocialNetwork{
        users: make(map[int]*User),
    }
}

func (sn *SocialNetwork) AddUser(id int, name string) {
    sn.users[id] = &User{ID: id, Name: name}
}

// 找共同好友
func (sn *SocialNetwork) CommonFriends(friendsA, friendsB []int) []*User {
    common := Intersection(friendsA, friendsB)
    result := []*User{}
    for _, id := range common {
        if user, ok := sn.users[id]; ok {
            result = append(result, user)
        }
    }
    return result
}

// 找所有相关用户
func (sn *SocialNetwork) AllRelated(friendsA, friendsB []int) []*User {
    all := Union(friendsA, friendsB)
    result := []*User{}
    for _, id := range all {
        if user, ok := sn.users[id]; ok {
            result = append(result, user)
        }
    }
    return result
}

func main() {
    sn := NewSocialNetwork()
    sn.AddUser(1001, "张三")
    sn.AddUser(1002, "李四")
    sn.AddUser(1003, "王五")
    sn.AddUser(1004, "赵六")
    sn.AddUser(1005, "孙七")
    sn.AddUser(1006, "周八")

    // 用户A的好友
    friendsA := []int{1001, 1002, 1003, 1004}
    // 用户B的好友
    friendsB := []int{1002, 1003, 1005, 1006}

    // 共同好友
    common := sn.CommonFriends(friendsA, friendsB)
    fmt.Println("共同好友:")
    for _, u := range common {
        fmt.Printf("  %s (ID: %d)\n", u.Name, u.ID)
    }

    // 所有相关用户
    all := sn.AllRelated(friendsA, friendsB)
    fmt.Printf("\n所有相关用户: %d 人\n", len(all))
}

输出：

共同好友:
  李四 (ID: 1002)
  王五 (ID: 1003)

所有相关用户: 6 人

三、Redis集合操作：生产环境实战

3.1 Redis集合命令对照表

3.2 场景1：共同好友功能

需求： 用户A和用户B的共同好友列表。

Go + Redis实现：

package main

import (
    "context"
    "fmt"
    "github.com/redis/go-redis/v9"
)

var ctx = context.Background()

func main() {
    // 连接Redis
    rdb := redis.NewClient(&redis.Options{
        Addr: "localhost:6379",
    })

    // 用户A的好友集合
    userA := "user:1001:friends"
    rdb.SAdd(ctx, userA, 2001, 2002, 2003, 2004)

    // 用户B的好友集合
    userB := "user:1002:friends"
    rdb.SAdd(ctx, userB, 2002, 2003, 2005, 2006)

    // 找共同好友：SINTER
    common, err := rdb.SInter(ctx, userA, userB).Result()
    if err != nil {
        panic(err)
    }

    fmt.Printf("共同好友: %v\n", common) // [2002 2003]

    // 统计共同好友数量
    count := len(common)
    fmt.Printf("共同好友数: %d\n", count)
}

性能分析：
– 如果用MySQL：需要JOIN两张表，O(NM)
– 用Redis集合：直接SINTER，O(NM)但全内存操作，快100倍

3.3 场景2：推荐系统（找可能认识的人）

需求： 推荐”你可能认识的人” = 好友的好友 – 已有好友 – 自己

算法：

推荐列表 = (好友A的好友 ∪ 好友B的好友 ∪ ...) - 我的好友 - {我}

Go + Redis实现：

func RecommendFriends(rdb *redis.Client, userID string) []string {
    myFriendsKey := fmt.Sprintf("user:%s:friends", userID)

    // 1. 获取我的所有好友
    myFriends, _ := rdb.SMembers(ctx, myFriendsKey).Result()

    // 2. 获取好友的好友（并集）
    friendsOfFriendsKeys := []string{}
    for _, friendID := range myFriends {
        key := fmt.Sprintf("user:%s:friends", friendID)
        friendsOfFriendsKeys = append(friendsOfFriendsKeys, key)
    }

    // 3. 合并所有好友的好友（并集）
    if len(friendsOfFriendsKeys) == 0 {
        return []string{}
    }
    allFriendsOfFriends, _ := rdb.SUnion(ctx, friendsOfFriendsKeys...).Result()

    // 4. 排除我的好友和我自己（差集）
    recommendations := []string{}
    myFriendsSet := make(map[string]bool)
    for _, f := range myFriends {
        myFriendsSet[f] = true
    }
    myFriendsSet[userID] = true

    for _, candidate := range allFriendsOfFriends {
        if !myFriendsSet[candidate] {
            recommendations = append(recommendations, candidate)
        }
    }

    return recommendations
}

func main() {
    rdb := redis.NewClient(&redis.Options{
        Addr: "localhost:6379",
    })

    // 构造测试数据
    rdb.SAdd(ctx, "user:1001:friends", "1002", "1003")
    rdb.SAdd(ctx, "user:1002:friends", "1001", "1004", "1005")
    rdb.SAdd(ctx, "user:1003:friends", "1001", "1006")

    // 推荐好友
    recommendations := RecommendFriends(rdb, "1001")
    fmt.Printf("推荐好友: %v\n", recommendations) // [1004 1005 1006]
}

3.4 场景3：标签系统（内容推荐）

需求： 找出同时具有多个标签的文章。

Go + Redis实现：

func FindArticlesByTags(rdb *redis.Client, tags []string) []string {
    if len(tags) == 0 {
        return []string{}
    }

    // 构造Redis key
    keys := make([]string, len(tags))
    for i, tag := range tags {
        keys[i] = fmt.Sprintf("tag:%s:articles", tag)
    }

    // 交集：同时具有所有标签的文章
    articles, _ := rdb.SInter(ctx, keys...).Result()
    return articles
}

func main() {
    rdb := redis.NewClient(&redis.Options{
        Addr: "localhost:6379",
    })

    // 文章1：Go + 后端
    rdb.SAdd(ctx, "tag:Go:articles", "article:1001")
    rdb.SAdd(ctx, "tag:后端:articles", "article:1001")

    // 文章2：Go + 微服务
    rdb.SAdd(ctx, "tag:Go:articles", "article:1002")
    rdb.SAdd(ctx, "tag:微服务:articles", "article:1002")

    // 文章3：Go + 后端 + 微服务
    rdb.SAdd(ctx, "tag:Go:articles", "article:1003")
    rdb.SAdd(ctx, "tag:后端:articles", "article:1003")
    rdb.SAdd(ctx, "tag:微服务:articles", "article:1003")

    // 查找：同时具有"Go"和"后端"标签的文章
    result := FindArticlesByTags(rdb, []string{"Go", "后端"})
    fmt.Printf("结果: %v\n", result) // [article:1001 article:1003]
}

四、SQL JOIN：集合论的数据库实现

4.1 JOIN的本质是笛卡尔积 + 过滤

笛卡尔积（Cartesian Product）：

A × B = {(a, b) | a ∈ A, b ∈ B}

翻译成人话：A和B的所有可能组合。

示例：

A = {1, 2}
B = {x, y}

A × B = {(1,x), (1,y), (2,x), (2,y)}

Go代码实现：

func CartesianProduct(a, b []int) [][2]int {
    result := [][2]int{}
    for _, va := range a {
        for _, vb := range b {
            result = append(result, [2]int{va, vb})
        }
    }
    return result
}

func main() {
    a := []int{1, 2}
    b := []int{10, 20}

    product := CartesianProduct(a, b)
    fmt.Println("笛卡尔积:")
    for _, pair := range product {
        fmt.Printf("  (%d, %d)\n", pair[0], pair[1])
    }
}

输出：

笛卡尔积:
  (1, 10)
  (1, 20)
  (2, 10)
  (2, 20)

4.2 JOIN类型对照表

4.3 INNER JOIN = 交集

场景： 找出有订单的用户。

SQL：

SELECT u.name, o.order_id
FROM users u
INNER JOIN orders o ON u.id = o.user_id;

Go模拟实现：

type User struct {
    ID   int
    Name string
}

type Order struct {
    OrderID int
    UserID  int
}

func InnerJoin(users []User, orders []Order) [][2]interface{} {
    result := [][2]interface{}{}

    // 笛卡尔积 + 过滤
    for _, u := range users {
        for _, o := range orders {
            if u.ID == o.UserID { // JOIN条件
                result = append(result, [2]interface{}{u.Name, o.OrderID})
            }
        }
    }

    return result
}

func main() {
    users := []User{
        {1, "张三"},
        {2, "李四"},
        {3, "王五"},
    }

    orders := []Order{
        {1001, 1}, // 张三的订单
        {1002, 1}, // 张三的订单
        {1003, 2}, // 李四的订单
    }

    result := InnerJoin(users, orders)
    fmt.Println("INNER JOIN结果:")
    for _, row := range result {
        fmt.Printf("  %s - 订单%d\n", row[0], row[1])
    }
}

输出：

INNER JOIN结果:
  张三 - 订单1001
  张三 - 订单1002
  李四 - 订单1003

注意： 王五没有订单，所以不在结果中。

4.4 LEFT JOIN = A + (A ∩ B)

场景： 找出所有用户及其订单（没订单的也要显示）。

SQL：

SELECT u.name, o.order_id
FROM users u
LEFT JOIN orders o ON u.id = o.user_id;

Go模拟实现：

func LeftJoin(users []User, orders []Order) [][2]interface{} {
    result := [][2]interface{}

    for _, u := range users {
        hasOrder := false

        // 找匹配的订单
        for _, o := range orders {
            if u.ID == o.UserID {
                result = append(result, [2]interface{}{u.Name, o.OrderID})
                hasOrder = true
            }
        }

        // 如果没有订单，也要保留用户记录
        if !hasOrder {
            result = append(result, [2]interface{}{u.Name, nil})
        }
    }

    return result
}

func main() {
    users := []User{
        {1, "张三"},
        {2, "李四"},
        {3, "王五"},
    }

    orders := []Order{
        {1001, 1},
        {1002, 1},
        {1003, 2},
    }

    result := LeftJoin(users, orders)
    fmt.Println("LEFT JOIN结果:")
    for _, row := range result {
        if row[1] == nil {
            fmt.Printf("  %s - 无订单\n", row[0])
        } else {
            fmt.Printf("  %s - 订单%d\n", row[0], row[1])
        }
    }
}

输出：

LEFT JOIN结果:
  张三 - 订单1001
  张三 - 订单1002
  李四 - 订单1003
  王五 - 无订单

五、笛卡尔积的陷阱：为什么JOIN会炸数据库

5.1 CROSS JOIN的恐怖

场景： 不小心写了个没有WHERE条件的JOIN。

SQL：

SELECT * FROM users, orders;  -- 危险！
-- 等价于 CROSS JOIN

结果：

users表：3条记录
orders表：1000条记录
结果集：3 × 1000 = 3000条记录

如果两个表都很大：

users表：10万条
orders表：100万条
结果集：10万 × 100万 = 1000亿条记录 → 数据库直接崩溃

5.2 Go模拟：笛卡尔积爆炸

func DangerousCrossJoin(users []User, orders []Order) int {
    count := 0
    for range users {
        for range orders {
            count++
            // 每个组合都要处理，内存爆炸
        }
    }
    return count
}

func main() {
    // 模拟大表
    users := make([]User, 100000)    // 10万用户
    orders := make([]Order, 1000000) // 100万订单

    fmt.Println("开始笛卡尔积计算...")
    // 警告：这会生成1000亿条记录，别真跑！
    // count := DangerousCrossJoin(users, orders)

    // 直接计算结果
    count := len(users) * len(orders)
    fmt.Printf("结果集大小: %d 条记录\n", count)
    fmt.Printf("如果每条记录1KB，总大小: %.2f TB\n",
        float64(count)/1024/1024/1024)
}

输出：

开始笛卡尔积计算...
结果集大小: 100000000000 条记录
如果每条记录1KB，总大小: 93.13 TB

5.3 如何避免笛卡尔积陷阱

规则1：JOIN必须有ON条件

-- ❌ 错误：没有ON条件
SELECT * FROM users, orders;

-- ✅ 正确：有ON条件
SELECT * FROM users u
INNER JOIN orders o ON u.id = o.user_id;

规则2：检查JOIN条件的选择性

// 计算JOIN后的预估行数
func EstimateJoinSize(leftRows, rightRows int, selectivity float64) int {
    // selectivity: JOIN条件的选择性（0-1之间）
    // 0.01 表示只有1%的记录匹配
    return int(float64(leftRows * rightRows) * selectivity)
}

func main() {
    users := 100000
    orders := 1000000

    // 场景1：没有JOIN条件（selectivity = 1.0）
    crossJoin := EstimateJoinSize(users, orders, 1.0)
    fmt.Printf("CROSS JOIN: %d 条\n", crossJoin)

    // 场景2：有JOIN条件（平均每个用户10个订单）
    innerJoin := EstimateJoinSize(users, orders, 0.00001)
    fmt.Printf("INNER JOIN: %d 条\n", innerJoin)
}

输出：

CROSS JOIN: 100000000000 条
INNER JOIN: 1000000 条

六、小结

这篇文章的核心观点：

1. 集合就是”不重复的一堆东西”，交集、并集、差集是最基础的操作
2. Redis集合操作直接对应数学概念：SINTER=交集，SUNION=并集，SDIFF=差集
3. SQL JOIN的本质是笛卡尔积+过滤，理解这个才能写出高效的SQL
4. 笛卡尔积是性能杀手：10万×100万=1000亿条记录，能把数据库搞崩
5. 集合论无处不在：共同好友、推荐系统、标签搜索、权限校验都是集合操作

记住这个对照表：

实战建议：
– 用Redis做集合操作，比MySQL快100倍（全内存）
– 写JOIN前先估算结果集大小，避免笛卡尔积
– 共同好友、推荐系统优先用Redis集合，不要用SQL JOIN

下次面试官问”如何实现共同好友功能”，你就可以回答：用Redis的SINTER做交集，O(N*M)时间复杂度，全内存操作。

参考资料
– Redis官方文档：Set命令
– MySQL官方文档：JOIN语法
– 《数据库系统概念》第6章：关系代数

返回系列总览

👉 程序员数学扫盲课：完整课程大纲