Создание эффективного списка друзей с использованием PHP

Question

Я хотел бы создать веб-сайт, содержащий некоторые элементы социальной сети.

Поэтому я пытался придумать эффективный способ хранения списка друзей (что-то вроде Facebook).

И после небольшого поиска единственное предложение, с которым я столкнулся, - это создание "таблицы" с двумя "идентификаторами", указывающими на дружбу.

Это может работать на небольших сайтах, но не кажется эффективнымнемного.

У меня есть опыт работы с Java, но я недостаточно хорошо разбираюсь в PHP.

Идея пришла мне в голову, и я думаю, что она могла бы работать довольно хорошо, проблема в том, что я не уверен, какреализовать это.

идея состоит в том, чтобы все идентификаторы ваших друзей сохранялись в древовидной структуре данных, каждый узел в этом дереве напоминает одну цифру из идентификатора друга.

сначала начинается с 1узел, а затем добавляя больше узлов, как пользователь добавляет друзей.(Немного похоже на Лемпеля-Зива).

каждый узел сможет указывать на 11 других узлов, от 0 до 9 и X.

"X" обозначает конец Id.

например, посмотрите это дерево:

Пример

В этом дереве у пользователя 4 друзей со следующими "id":

• 0
• 143
• 1436
• 15

Обновление: , как могло бы бытьДо сих пор неясно, идея состоит в том, что у каждого пользователя будет дерево в виде многомерного массива, в котором наличие самих указателей указывает на «идентификатор» друга.

Если у каждого пользователя был такой многомерный массив, поискесли идентификатор "y" является моим другом, удаление идентификатора "y" из моего списка друзей или добавление идентификатора "y" в мой список друзей потребует постоянного времени O (1) без зависимости от количества пользователей, которые могут быть на сайте.есть, только отступать, взять такой огромный массив, сериализовать его и помещать его в каждый ряд таблицы просто не кажетсяверно.

-Это вообще возможно реализовать?

-Практично ли использовать сериализацию для вставки этого дерева в таблицу?

-Есть ли лучший способ сделать это?this?

Преимущества, которые я выбрал, заключаются в том, что даже при очень большом количестве идентификаторов (миллионы или миллиарды) время поиска, добавления, удаления является линейным (зависит от количества цифр).

Я был бы очень признателен за любую помощь в реализации этого или любые предложения по альтернативным способам улучшения или изменения этого метода.

Answer 1

Я бы настоятельно рекомендовал против этого.

• Экономия хранения незначительна и может (вероятно?) Быть хуже . В реальном наборе данных фактическая экономия пространства, предоставляемая вам при таком подходе, минимальна. Вычисление средней экономии является очень сложной проблемой, но используйте некоторые действительные числа и попробуйте несколько образцов со случайными идентификаторами. Если у вас миллион пользователей, рассмотрите пользователя с 15 друзьями. Сколько данных вы сохраняете с этим подходом? На самом деле вы можете использовать больше места, поскольку модели смежности деревьев могут требовать значительных данных.

• «Рендеринг» списка пользователей требует затрат ресурсов процессора.

• Вставки являются недетерминированными и нетривиальными. Когда вы добавляете нового пользователя в существующее дерево, у вас будет множество способов его вставки. Предполагая, что вы не выбираете произвольно, трудно вычислить, какой подход является лучшим (и будет основан только на эвристике).

Это большие, которые пришли мне в голову. Но в целом, я думаю, вы слишком обдумываете это.

Answer 2

Вы говорите «используя PHP» в заголовке, но это, кажется, просто вопрос базы данных в его основе. И верьте, хотите нет, но таблица ссылок - безусловно лучший путь. Особенно, если у вас есть миллионы или миллиарды пользователей. Это будет быстрее обрабатывать, легче обрабатывать в коде PHP и меньше для хранения.

Обновление

Таблица пользователей:

  id    |   name   |   moreInfo
   1    |    Joe   |     stuff
   2    |    Bob   |     stuff
   3    |   Katie  |     stuff
   4    |   Harold |     stuff

Таблица дружбы:

   left   |   right
    1     |     4
    1     |     2
    3     |     1
    3     |     4

В этом примере Джо знает всех, а Кэти знает Гарольда.

Это, конечно, упрощенный пример.

Я бы хотел услышать, если у кого-то есть лучшая логика слева и справа и объяснение, почему.

Обновление

Я дал несколько php-код в комментарии ниже, но он был размечен неправильно, поэтому здесь это снова.

$sqlcmd = sprintf( 'SELECT IF( `left` = %1$d, `right`, `left`) AS "friend" FROM `friendship` WHERE `left` = %1$d OR `right` = %1$d', $userid);

Answer 3

Вы должны проверить OQGRAPH , механизм хранения графов Open Query. Он предназначен для эффективного хранения деревьев и графиков для MySQL.

Вы также можете проверить мою презентацию Модели для иерархических данных с SQL и PHP или мой ответ на Какой самый эффективный / элегантный способ разбить плоскую таблицу на дерево? 1008 * здесь, на переполнении стека.

Я описываю схему, которую я называю Таблица закрытия , в которой записываются все пути между предками и потомками в иерархии.

Answer 4

Мало идей:

• упорядоченные списки - поиск по упорядоченному списку выполняется быстро, хотя сам порядок упорядочения может быть более тяжелым;
• данные горизонтального разделения;
• избавление от преждевременных оптимизаций.