Сложность времени / анализ производительности MySQL - PullRequest
Новая
       36

Сложность времени / анализ производительности MySQL

0 голосов
/ 20 января 2010

Настройка (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 для моего предыдущего поста:

Задача, как реализовать алгоритм для шести степеней разделения?

Но в чем его сложность? Предположим, что существует всего n записей.

1 Ответ

1 голос
/ 20 января 2010

Предполагая, что есть N вершин и E ребер. Для каждой таблицы может быть соединение между каждой парой вершин, и необходимо проверить все вершины на равенство. Таким образом, производительность в худшем случае будет O (| V | + | E |)

Обновлено: Если вы рассматриваете Mysql, есть много вещей, которые влияют на сложность, если у вас есть индекс первичного ключа в поле, будет использоваться индекс b-дерева. Если это обычный некластеризованный индекс, будет использован хеш-индекс. Для каждой из этих структур данных существуют разные затраты.

Из вашего другого вопроса, я вижу, это ваши требования 1. Рассчитайте путь от UserX до UserY 2. Для UserX рассчитайте всех пользователей, которые находятся на расстоянии не более 3 шагов.

Во-первых, лучше всего применить алгоритм djikstra и создать таблицу в Java, а затем обновить ее в таблице. Обратите внимание, что для добавления каждого нового узла требуется полная обработка.

Другим решением этой проблемы будет использование рекурсивного SQL, введенного в стандарте SQL 1999, для создания представления, содержащего путь от UserX до UserY. Дайте мне знать, если вам нужны ссылки для рекурсивных запросов.

Для второго написанный вами запрос отлично работает.

...