Как сайты, подобные LinkedIn, эффективно отображают отношения 1-го/2-го/3-го уровня рядом с именем каждого человека?

Ответ 1

Вы можете использовать аксиомы о сетях малого мира, чтобы оптимизировать этот тип обхода.

Малые сети мира характеризуются "хабами", представляющими очень плотные взаимосвязи других узлов. Большинство узлов в сети, как правило, либо соединяются в пределах нескольких перелетов с топологически расположенным рядом с node (1-4 ударами), либо проедут через один или несколько таких концентраторов. Это одна из основных причин того, что сети малого мира ведут себя так, как они себя делают.

Ответ 2

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

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

Ответ 3

Если вы думаете об этом, то в SQL это может быть очень интенсивным.

Учитывая это и тот факт, что он в конечном итоге будет использоваться повсеместно, и это пространство относительно дешево... Я бы предложил создать индекс с использованием Lucene (или Lucene.NET) в зависимости от вашего языкового предпочтения. Вы могли бы сделать пару вещей таким образом.

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

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

С идентификаторами в руке (из которых вы всегда выполняете поиск) вы можете перейти в БД, чтобы получить необходимую информацию. Затем кешируйте свой вывод, чтобы еще больше свести к минимуму то, что было бы очень быстрым поиском, db-запросом, построением данных... но быстрее, если он просто исходит из кеша.

Используйте что-то вроде Velocity, MemCached или MemCached Win32 для централизованного кэширования в веб-ферме.

Ответ 4

Я не уверен в структуре таблицы или сложности системы, но вот простой пример SQL Server с использованием рекурсивного CTE:

DECLARE @People table (PersonID int, Name varchar(10))
DECLARE @Network table (PersonID int, NetworkedPersonID int)
INSERT INTO @People VALUES (1,'AAA')
INSERT INTO @People VALUES (2,'BBB')
INSERT INTO @People VALUES (3,'CCC')
INSERT INTO @People VALUES (4,'DDD')
INSERT INTO @People VALUES (5,'EEE')
INSERT INTO @People VALUES (6,'FFF')
INSERT INTO @People VALUES (7,'GGG')
INSERT INTO @People VALUES (8,'HHH')
INSERT INTO @Network VALUES (1,2)
INSERT INTO @Network VALUES (1,3)
INSERT INTO @Network VALUES (2,5)
INSERT INTO @Network VALUES (2,7)
INSERT INTO @Network VALUES (4,8)
INSERT INTO @Network VALUES (7,8)
INSERT INTO @Network VALUES (7,3)
INSERT INTO @Network VALUES (8,9)
DECLARE @TargetPersonID  int
SET @TargetPersonID=1

;WITH NetworkLevels AS
(   SELECT
        NetworkedPersonID,1 AS NetworkLevel
        FROM @Network
        WHERE [email protected]
    UNION ALL
    SELECT
        n.NetworkedPersonID, l.NetworkLevel+1
        FROM @Network                n
            INNER JOIN NetworkLevels l ON n.PersonID=l.NetworkedPersonID
    WHERE l.NetworkLevel<=2
)
SELECT * FROM NetworkLevels

ВЫВОД:

NetworkedPersonID NetworkLevel
----------------- ------------
2                 1
3                 1
5                 2
7                 2
8                 3
3                 3

(6 row(s) affected)

Ответ 5

Чтобы реализовать

DistanceCategory(A,B): { 1, 2, 3+}

Используйте то, что соединения двунаправлены.

Храните соединения 1-го уровня как отсортированный список в некоторых случаях, связанных с KV:

Key: [UserFromId,UserToId].
Value: UserToId

псевдокод:

DistanceCategory(A,B)
{
    if ( exists([A,B]) )
        return 1;
    if ( firstCommonElement(getAll([A,B]), getAll([A,B])) != null )
        return 2;
    return 3;
}

Сложность: O (C1 + C2). C1, C2 - номер подключения обоих пользователей.

Ответ 6

Не связаны ли данные в виде большого гигантского графика? и когда пользователь войдет в систему, система будет обращаться к своему node, а затем, выполнив ширину первого обхода для 3 уровней, система сохранит эти узлы в виде набора (вместе с информацией уровня) и когда появится человек на веб-странице система выполняет поиск этого набора node и выдает соотношение расстояний..

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