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

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

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

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

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

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

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

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

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

Я не уверен в структуре таблицы или сложности системы, но вот простой пример 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 PersonID=@TargetPersonID
    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)

Реализовать

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

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

Хранить соединения 1-го уровня в виде отсортированного списка в некотором KV sore:

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-номер соединения обоих пользователей.

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

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