1. 先把问题说清楚

半年前我接了个风控需求。线上有2亿条用户关联关系，比如转账、同设备登录、同IP。这堆关系里，判断任意两个账号是否在同一个团伙里。

第一版用了MySQL 8.0.35的递归CTE。上线两周，某天凌晨2点被DBA叫醒：递归查询把连接池打满，支付接口超时告警。单次查询平均1.2秒，深度超过50直接超时，线上根本没法用。

后来换成并查集，同一个需求变成了：合并100万条边耗时124ms，后续单次查询均摊0.1微秒。这篇是完整记录，代码直接用。

2. 方案选型：别上来就写SQL

连通性问题一共对比了3个方案。

2.1 BFS/DFS连通分量标记

思路是先把全图遍历一遍，给每个节点染色，相同颜色的就是一个团伙。查询时比对颜色即可，时间复杂度O(1)。

代价是预处理O(V+E)。在有2亿条边的图上，遍历一遍要跑8秒以上，内存碎片直接干到2GB。而且只要新增一条边，就可能需要重新染色。这个方案在静态小图里不错，在风控这种动态图上不现实。

2.2 MySQL递归CTE

不需要预处理，查询时沿着边往下递归找。

CREATE TABLE `user_relation` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `user_id` bigint NOT NULL,
  `related_id` bigint NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_user` (`user_id`),
  KEY `idx_related` (`related_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

-- 查询 user_id=1 和 user_id=2 是否连通
WITH RECURSIVE relate_path AS (
  SELECT related_id, 1 AS depth FROM user_relation WHERE user_id = 1
  UNION ALL
  SELECT r.related_id, relate_path.depth + 1
  FROM relate_path
  JOIN user_relation r ON r.user_id = relate_path.related_id
  WHERE relate_path.depth < 50
)
SELECT EXISTS(SELECT 1 FROM relate_path WHERE related_id = 2) AS connected;

问题是：MySQL的递归CTE每次查询都要从起点重新扩一圈。深度30的时候平均耗时1200ms，深度50就直接把连接池拖垮。它只能解决“单次查询”，解决不了“批量判断”。

2.3 并查集

并查集专门处理动态连通性。每次合并一条边，均摊O(α(n))，α(n)是反阿克曼函数，可以理解为常数小于5。查询也是同样的复杂度。

直接说结论：动态连通性，选并查集。不是因为它新，而是因为它就是为这个问题设计的。

3. 并查集原理：树和路径压缩

并查集维护一个森林。每个节点存一个parent指针。parent指向自己的节点，就是这棵树的根。两个节点在同一个集合，当且仅当它们的根相同。

合并时，把一棵树的根挂到另一棵树的根上。如果不做任何优化，树会退化成链表，find操作变成O(n)。

第一个优化是路径压缩：find的时候把路径上所有节点直接挂到根下面。这样下次find就快了。第二个优化是按秩合并：永远把矮树挂到高树上，控制树高。两个优化一起用，摊还复杂度是O(α(n))，数学上可以认为是在正常数据范围内接近O(1)。

为什么必须两个都用？只用路径压缩，每次union可能把两个深度差不多的树合并，树高依然可能增长。只用按秩合并，树高被控制在O(log n)，但查询要log n次跳转。两个都用，树高被压到极小，几乎查一次就能把路径拉平。

4. PHP 8.3完整实现

生产环境是PHP 8.3.2，CLI模式，Linux 5.10，Intel Xeon E5-2680，32GB内存。

节点ID是自增整数，直接映射数组下标。用SplFixedArray而不是普通PHP数组——普通数组在100万整数key时内存轻松超200MB，SplFixedArray每个元素固定8字节，两个数组100万节点才16MB。

<?php
declare(strict_types=1);

class UnionFind {
    private SplFixedArray $parent;
    private SplFixedArray $rank;
    private int $count;
    private int $n;

    public function __construct(int $n) {
        $this->n = $n;
        $this->parent = new SplFixedArray($n);
        $this->rank = new SplFixedArray($n);
        $this->count = $n;

        for ($i = 0; $i < $n; $i++) {
            $this->parent[$i] = $i;
            $this->rank[$i] = 0;
        }
    }

    public function find(int $x): int {
        $root = $x;
        // 循环找根，不递归。PHP递归深了直接Segmentation fault
        while ($this->parent[$root] !== $root) {
            $root = $this->parent[$root];
        }
        // 第二次循环做路径压缩，把路径上所有节点挂到根上
        while ($x !== $root) {
            $next = $this->parent[$x];
            $this->parent[$x] = $root;
            $x = $next;
        }
        return $root;
    }

    public function union(int $x, int $y): void {
        $rx = $this->find($x);
        $ry = $this->find($y);
        if ($rx === $ry) {
            return;
        }
        // 按秩合并：矮树挂高树
        if ($this->rank[$rx] < $this->rank[$ry]) {
            $this->parent[$rx] = $ry;
        } elseif ($this->rank[$rx] > $this->rank[$ry]) {
            $this->parent[$ry] = $rx;
        } else {
            $this->parent[$ry] = $rx;
            $this->rank[$rx]++;
        }
        $this->count--;
    }

    public function isConnected(int $x, int $y): bool {
        return $this->find($x) === $this->find($y);
    }

    public function getCount(): int {
        return $this->count;
    }
}

注意find是两段循环，不是递归。PHP没有尾递归优化，100万节点递归一次就崩。

5. 压测数据：124ms合并100万条边

压测脚本直接生成100万条随机边，先合并，再跑100万次随机查询，记录每次的耗时和内存峰值。

<?php
require 'UnionFind.php';

$n = 1000000;
$uf = new UnionFind($n);

srand(42);
$mergeStart = hrtime(true);
for ($i = 0; $i < 1000000; $i++) {
    $a = rand(0, $n - 1);
    $b = rand(0, $n - 1);
    $uf->union($a, $b);
}
$mergeTime = hrtime(true) - $mergeStart;

$queryStart = hrtime(true);
$connected = 0;
for ($i = 0; $i < 1000000; $i++) {
    $a = rand(0, $n - 1);
    $b = rand(0, $n - 1);
    if ($uf->isConnected($a, $b)) {
        $connected++;
    }
}
$queryTime = hrtime(true) - $queryStart;

printf("合并100万条边: %.3f ms\n", $mergeTime / 1e6);
printf("查询100万次:   %.3f ms\n", $queryTime / 1e6);
printf("单次查询均摊:  %.6f ms\n", $queryTime / 1e6 / 1000000);
printf("剩余连通分量:  %d\n", $uf->getCount());
printf("内存峰值:      %.2f MB\n", memory_get_peak_usage(true) / 1048576);

运行结果（PHP 8.3.2，opcache开启，JIT关闭）：

$ php union_find_test.php
合并100万条边: 124.508 ms
查询100万次:   91.321 ms
单次查询均摊:  0.000091 ms
剩余连通分量:  632723
内存峰值:      16.25 MB

注意“池化”效应：随着合并次数增加，树高被路径压缩不断拉平，后续find更快。前10万条合并是最慢的，越往后越快。

6. 内存再砍一半：秩存进低2位

如果你连16MB都嫌多，可以把rank压缩进parent数组的低2位。因为树高最大不会超过n，而n=100万时，高30位足够存父节点编号，低2位存秩。

<?php
class CompactUnionFind {
    private SplFixedArray $data;

    public function __construct(int $n) {
        $this->data = new SplFixedArray($n);
        for ($i = 0; $i < $n; $i++) {
            // 父节点编号左移2位，低2位为0（秩=0）
            $this->data[$i] = $i << 2;
        }
    }

    private function parent(int $x): int {
        return $this->data[$x] >> 2;
    }

    private function rank(int $x): int {
        return $this->data[$x] & 3;
    }

    private function setParent(int $x, int $parent): void {
        $this->data[$x] = ($parent << 2) | $this->rank($x);
    }

    private function setRank(int $x, int $rank): void {
        $this->data[$x] = ($this->parent($x) << 2) | $rank;
    }

    public function find(int $x): int {
        $root = $x;
        while ($this->parent($root) !== $root) {
            $root = $this->parent($root);
        }
        while ($x !== $root) {
            $next = $this->parent($x);
            $this->setParent($x, $root);
            $x = $next;
        }
        return $root;
    }

    public function union(int $x, int $y): void {
        $rx = $this->find($x);
        $ry = $this->find($y);
        if ($rx === $ry) {
            return;
        }
        $hx = $this->rank($rx);
        $hy = $this->rank($ry);
        if ($hx < $hy) {
            $this->setParent($rx, $ry);
        } elseif ($hx > $hy) {
            $this->setParent($ry, $rx);
        } else {
            $this->setParent($ry, $rx);
            $this->setRank($rx, $hx + 1);
        }
    }

    public function isConnected(int $x, int $y): bool {
        return $this->find($x) === $this->find($y);
    }
}

这个版本100万节点内存8.25MB，合并耗时132ms，查询耗时95ms。性能略低一点点，但内存减半。如果你要处理1亿节点，普通数组直接Out of Memory，这个版本还能扛住。

7. 实际应用不只是风控

7.1 无向图判环

并查集在Kruskal算法里用于判断一条边的两个端点是否已经连通。如果已经连通，加上这条边就是环。直接复用上面的union方法，如果union返回false就是形成了环。只需要改一点：

public function unionWithCycleDetection(int $x, int $y): bool {
    $rx = $this->find($x);
    $ry = $this->find($y);
    if ($rx === $ry) {
        return false;
    }
    $this->union($x, $y);
    return true;
}

7.2 批量等价关系合并

我们线上还有一个场景：用户多个账号（手机号、设备ID、支付宝号）要做归一化。每组等价关系进来，直接union。最终每个连通分量就是一个统一身份ID。原来用嵌套循环去匹配，100万组跑4小时；换并查集后8分钟。

8. 避坑指南：我踩过的5个坑

坑1：PHP普通数组真不是给你存100万int的。

我第一版用$parent = []，100万节点跑完memory_get_peak_usage显示218MB。因为PHP数组是哈希表，每个整数key/value都要一个zval和bucket。改成SplFixedArray后直接降到16MB。你要是看到内存报警，先查这边。

坑2：递归find在PHP里会Segmentation fault。

别问我怎么知道的。find递归10000层，PHP直接segmentfault，连错误日志都不打。用循环写，成本低一半，还安全。

坑3：union方向写反，树退化成链表。

按秩合并时，永远是rank小的挂到rank大的下面。写反一次，100万次查询从91ms变成2.3秒，而且路径压缩也救不回来。因为每次find都被拉成长链的find拖慢。写完之后一定要自测 union(1,2), union(1,3) 这类场景，确认树的形态。

坑4：MySQL递归CTE有深度限制。

MySQL 8.0.35的cte_max_recursion_depth默认1000。看起来够用，但深链路递归时，每层还要做连接查询，实际深度超过100就基本卡死。别拿它做连通性判断，在线业务会死给你看。

坑5：路径压缩和按秩合并缺一个都慢。

我做过对照组：只用路径压缩，100万次查询耗时180ms；只用按秩合并，耗时210ms；两个都用，91ms。少了任何一个，都是线性到树高的log差距。不能只写find循环不写rank，也不能写了rank不压缩。

9. 结论

并查集不是新东西，但解决动态连通性仍然是最好的选择。如果你也遇到“给一堆关系，判断任意两点是否连通”的问题，别再写递归SQL了。上面的代码直接拿去用，压测数据就是经验值。注意SplFixedArray、循环find、按秩合并这三个点，你已经避开80%的坑。