mysql - 时间复杂度/MySQL性能分析

Question

设置(MySQL):

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

这是我上一篇文章的 BFS 解决方案:

Challenge,how to implement an algorithm for six degree of separation?

但这有什么复杂性呢？假设总共有n条记录。

Answer 1

假设有N个顶点和E条边。对于每个表，每对顶点之间都可以有一个连接，并且需要检查所有顶点是否相等。所以最坏情况下的性能将是 O(|V| + |E|)

更新:如果你正在考虑 Mysql，有很多东西会影响复杂性，如果你在字段上有主键索引，将使用 b-tree 索引。如果它是一个普通的非聚集索引，将使用散列索引。这些数据结构中的每一个都有不同的成本。

从你的另一个问题来看，这是你的要求1.计算UserX到UserY的路径2.对于UserX，计算距离不超过3步的所有用户。

对于第一个，最好的办法是应用djikstra算法并在java中构建一个表，然后在表中更新它。请注意，添加每个新节点都需要完整的处理。

对此的其他解决方案是使用 SQL 1999 标准中引入的递归 SQL 来创建包含从 UserX 到 UserY 的路径的 View 。如果您需要递归查询的一些引用，请告诉我。

对于第二个，您编写的查询非常有效。