MySQL эффективно хранит неориентированные ребра графа

Question

Я хочу хранить неориентированные ребра графа (например, для друзей). Для хранения и извлечения всех друзей узла a можно использовать:

Создание двух строк на ребро, запрос по одному столбцу на узел:

+--------------------------+
| id | from_node | to_node |
+--------------------------+
| 1  |  a        |  b      |
| 2  |  b        |  a      |
+--------------------------+
SELECT * FROM `x` WHERE from_node = a

Создайте одну строку для каждого края, используйте OR:

+--------------------------+
| id | node_a    | node_b  |
+--------------------------+
| 1  |  a        |  b      |
+--------------------------+
SELECT * FROM `y` WHERE node_a = a OR node_b = a

Что делает поиск более эффективным?

• Таблица x с 2n строками, индексы from_node и to_node, поиск по одному столбцу
• Таблица y с n строками, индексы на node_a и node_b, поиск по обоим столбцам с использованием OR

Answer 1

Это, вероятно, слишком устарело, чтобы быть полезным, но я опубликую его, если это поможет другим людям!

Я храню неориентированные графики, как ваш второй пример, и у меня есть ограничение, которое должен выполнять node_aбыть меньше, чем node_b.Затем вы тривиально накладываете ограничение UNIQUE на пару и знаете, что данные согласованы.Запросы должны немного больше работать, сравнивая node_a с меньшим из {a, b} и node_b другое значение.PostgreSQL (БД, которую я знаю лучше всего) предоставляет функции GREATEST() и LEAST(), которые помогают здесь.

Answer 2

если вы все оптимизируете, X будет быстрее, если вы прочитаете данные с диска и будете запрашивать друзей одного человека. это потому, что вы можете расположить свои данные на диске так, чтобы они упорядочивались по одному индексу, который вы запрашиваете. Таким образом, для одного человека, вам нужно только выполнить один поиск диска. Для Y требуются запросы по двум индексам, поэтому может потребоваться несколько попыток поиска друзей даже для одного человека (а время доступа к диску обычно преобладает в простых запросах).

см. кластеризованные индексы в Википедии (и руководство по mysql )

если вам посчастливится узнать, что данные всегда будут в памяти, то оба они, скорее всего, будут «достаточно быстрыми» (и даже если данные находятся на диске, они могут быть достаточно быстрыми - я не говорю, что X - лучший дизайн, только то, что можно сделать максимально эффективным).