Neo4j является помеченным графом свойств .
Для физической структуры у нас есть хранилища вещей: хранилище узлов, хранилище отношений, хранилище свойств, хранилище меток, строки store, et c.
Это просто файлы нескольких записей в фиксированных форматах, поэтому каждая запись в хранилище графиков имеет одинаковое форматирование, каждая запись в хранилище отношений имеет одинаковое форматирование, et c и между записями есть указатели (идентификаторы графиков). Таким образом, идентификаторы графиков на самом деле являются смещениями, используемыми для переключения указателей между связанными и соответствующими элементами в хранилищах.
Логически, запись узла в хранилище узлов имеет различные указатели на другие записи в других хранилищах, такие как метки, и первые отношения в цепочке отношений. Отношения имеют указатели на начальный и конечный узлы отношения, а также на предыдущее и следующее отношение в цепочке. И узлы, и отношения имеют указатели на первую запись свойства, которые составляют начало их цепочек свойств.
Таким образом, логически мы имеем эквивалент структур связанных списков, соединяющих некоторые из наших элементов (цепочки свойств на узел, отношения цепочки на узел). Но для связи между узлами через отношения то, что вы рисуете на доске при моделировании графа, является довольно хорошим приближением к тому, что происходит в структуре, узлы и отношения связываются непосредственно друг с другом, указывая на запись друг друга в соответствующем хранилище. файлы.
У нас есть небольшая избыточность для ускорения поиска ... узлы содержат некоторое количество меток в самой записи узла, а отношения содержат их тип.
Это также Простейшая абстракция, у нас есть немного другой формат, который мы используем на плотных узлах, так что мы объединяем отношения в узле по их типу и направлению, что позволяет быстро выбирать релевантные отношения по тому, что мы ищем, вместо того, чтобы рассматривать и фильтровать все присутствуют отношения.
Итак, это общий обзор физической структуры. Однако более интересно то, почему была выбрана такая структура, что она позволяет, и как это влияет на то, почему базы данных нативных графов являются конкурентоспособными по сравнению с реляционными базами данных для графических и интенсивных сценариев использования.
Суть всех это то, что обход отношений не использует соединения таблиц или их эквиваленты. Стоимость прохождения отношений / шаблонов не основана на общих отношениях или узлах на графике, а только на фактических отношениях и имеющихся узлах, O (1) указатель переключения между хранилищами, узел -> rel -> узел и т. Д. 1040 *.
Это характеристика c собственных графовых баз данных, известная как безиндексная смежность , и она поддерживается используемыми форматами хранилищ. Это одна из основных причин: в случаях использования графических объектов и связанных данных вы должны рассматривать базу данных собственного графа над реляционной базой данных (или над базой данных за ненативным графом, или с наложением, которое просто располагается поверх реляционной базы данных).
Так, например, если мы находимся в узле 1 с 3 связями с другими узлами, и в графе 10 миллиардов узлов и 50 миллиардов связей, то переход к следующему узлу в шаблоне будет очень быстрым , Неважно, сколько всего связей или узлов общее, важно только то, что на текущем узле присутствуют только 3 связи, поэтому мы делаем три O (1) прыжка с указателем (и любую фильтрацию) и продолжаем обход этих три узла также пытаются найти пути, которые соответствуют шаблону. Стоимость прохождения пропорциональна тем частям графа, к которым вы в итоге прикоснулись / пересекаете, а не к общему размеру графа.
Конечно, чтобы создать отношения, вам часто приходится делать эквивалент объединения таблиц ... сопоставление узлов по определенным свойствам (обычно с использованием структуры индекса, используемой для поиска точек входа в графе), а затем создание взаимосвязи между ними.
Так что да, поиски по индексам вступают в игру, но это происходит при создании отношений. Как только отношения созданы, тогда запросы к ним становятся O (1) за обход, прыжок указателя плюс стоимость любой дополнительной фильтрации, которую вы хотите выполнить. Мы компенсируем стоимость соединения с созданием отношений, чтобы оптимизировать скорость обхода во время выполнения.
Оставшееся использование индекса предназначено для поиска точек входа на графике, и как только мы их получим, прохождение становится центром внимания, и мы снова получаем просто переключение указателя, без присоединения таблицы, зависящей от размера данных.
Старая запись в блоге одного из моих коллег, Макс де Марци, включает описание и визуализацию формата магазина , который может помочь. В некоторых отношениях он немного устарел (и запись в блоге, и ссылка на него с 2012 года), и мы всегда ищем способы оптимизировать и настроить форматирование нашего магазина для повышения производительности, но дух этой записи заключается в том, что имеет значение:
Отношения похожи на объединение таблиц, но мы платим за создание отношений, а не за обход. Для обхода мы просто переключаем указатель, и он не замедляется по мере роста ваших данных, как соединения таблиц в реляционной базе данных.