Как хранить двунаправленные отношения в СУБД, например MySQL?

Предположим, что я хочу хранить отношения между пользователями моего приложения, как и Facebook, как таковой.

Это означает, что если A является другом (или некоторым отношением) B, то B также является другом A. Чтобы сохранить эти отношения, я в настоящее время планирую хранить их в таблице для отношений следующим образом

  UID      FriendID
 ------    --------
 user1      user2
 user1      user3
 user2      user1

Однако я столкнулся с двумя вариантами:

Типичный случай, когда я буду хранить как user1 -> user2, так и user2->user1. Это займет больше места, но (по крайней мере, в моей голове) требуется только один проход по строкам для отображения друзей конкретного пользователя.
Другой вариант - сохранить либо user1->user2 OR user2->user1, и всякий раз, когда я хочу найти всех друзей user1, я буду запрашивать в обоих столбцах таблицы, чтобы найти друзей пользователя. Это займет половину пространства, но (опять же, по крайней мере, в моей голове) в два раза больше времени.

Прежде всего, подходит ли мое рассуждение? Если да, то есть ли какие-то узкие места, которые я забываю (с точки зрения масштабирования/пропускной способности или чего-то еще)?

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

Ответ 1

Вот как эти два подхода будут физически представлены в базе данных:

Проанализируем оба подхода...

Подход 1 (оба направления хранятся в таблице):

PRO: упрощенные запросы.
CON: данные могут быть повреждены вводом/обновлением/удалением только одного направления.
MINOR PRO: не требует дополнительных ограничений для обеспечения дублирования дружбы.
Необходим дальнейший анализ:
- TIE: один индекс охватывает в обоих направлениях, поэтому вам не нужен вторичный индекс.
- TIE: требования к хранению.
- TIE: производительность.

Подход 2 (только одно направление, сохраненное в таблице):

CON: Более сложные запросы.
PRO: Невозможно испортить данные, забыв обращаться с противоположным направлением, поскольку нет противоположного направления.
MINOR CON: Требуется CHECK(UID < FriendID), поэтому одна и та же дружба никогда не может быть представлена двумя разными способами, а ключ на (UID, FriendID) может выполнять свою работу.
Необходим дальнейший анализ:
- TIE: для cover требуются два индекса: оба направления запроса (составной индекс на {UID, FriendID} и составной индекс на {FriendID, UID}).
- TIE: требования к хранению.
- TIE: производительность.

Особый интерес представляет точка 1. MySQL/InnoDB всегда кластеры, а вторичные индексы могут быть дорогими в кластеризованных таблицах (см. "Недостатки кластеризации" в в этой статье), поэтому может показаться, что вторичный индекс в подходе 2 съел все преимущества меньшего количества строк. Однако, вторичный индекс содержит те же самые поля, что и первичный (только в обратном порядке), поэтому в этом конкретном случае нет накладных расходов на хранение. Также нет указателя на кучу таблицы (так как нет кучи таблиц), поэтому, вероятно, даже более дешевое хранилище, чем обычный индекс на основе кучи. И если запрос покрывается индексом, не будет двойного поиска, обычно связанного со вторичным индексом в кластерной таблице. Таким образом, это в основном связь (ни подход 1, ни подход 2 не имеют значительного преимущества).

точка 2 связана с точкой 1: не имеет значения, будет ли у нас B-дерево значений N или двух B-деревьев, каждое из которых имеет N/2 значения. Так что это также связь: оба подхода будут использовать примерно столько же памяти.

То же рассуждение относится к точке 3: мы ищем одно большее B-Tree или два меньших, не имеет большого значения, так что это тоже связь.

Итак, для надежности и, несмотря на несколько более уродливые запросы и необходимость в дополнительном CHECK, я бы пошел с подходом 2.

Ответ 2

Хранение в наши дни относительно дешево, поэтому я не стал бы беспокоиться об этом из-за этого.

Что бы меня беспокоило, так это то, что вы должны очиститься, когда вы дважды храните информацию. Поэтому, если вы кого-то "недружелюбны", вам нужно удалить 2 записи, а не только одну.

Другими соображениями являются поиск и индексация. Могут существовать преимущества хэширования комбинации из 2 идентификаторов пользователей для проверки на существование, если вы следуете соглашению о согласовании (например, всегда добавляйте более высокий идентификатор к нижнему уровню до хэширования).

Итак, теперь у вас есть другие возможности. Вас интересует вопрос о взаимоотношениях между двумя пользователями? Или более важно смотреть на атрибуты одного пользователя?

Это опасения по поводу того, что система будет делать. Взгляните на такие темы, как DDD (Domain Driven Design) и CQRS (Command Query Responsibility Segregation), чтобы увидеть, как разделить ваше приложение, чтобы каждая область была реализована самым простым способом. Это даст вам возможность тонкой настройки и оптимизации позже, не сталкиваясь с проблемами сложности.