Эффективная структура базы данных для данных глубокого дерева

Question

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

Существует несколько стандартных алгоритмов для представления дерева данных. Я нашел эту ссылку в качестве части руководства Mongodb отличным сводкой: http://docs.mongodb.org/manual/tutorial/model-tree-structures/

Моя система имеет свойства, которые плохо сопоставляются ни с одним из этих случаев. Проблема в том, что глубина дерева настолько велика, что держать «предков» или «путь» очень велико. Дерево также часто изменяется настолько, что подход «Вложенные наборы» неэффективен. Я рассматриваю гибрид подхода «Материализованные пути» и «Родительские ссылки», где вместо пути я храню хэш, который не гарантированно является уникальным, но в 90% случаев он является. Затем в 10% случаев происходит столкновение, исходная ссылка разрешает его. Идея состоит в том, что в 90% случаев существует быстрый запрос для хэша пути. Эта идея похожа на технологию фильтра цветения. Но это все для фона: вопрос находится в первой строке этого сообщения.

Answer 1

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

Это довольно наивный подход, в котором нет ничего умного, но он работает для меня.

У дерева было около 300 или 400 членов, и, я думаю, 7 или 8 уровней в глубину. У этой части системы вообще не было проблем с производительностью: это было очень быстро. Пользовательский интерфейс был другим делом, но это уже другая история.