Древовидные структуры в базе данных nosql

Question

Я разрабатываю приложение для Google App Engine, которое использует BigTable для своего хранилища данных.

Это приложение для совместного написания истории.Это очень простой хобби-проект, над которым я работаю просто для удовольствия.Это открытый исходный код, и вы можете увидеть его здесь: http://story.multifarce.com/

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

Представьте следующую древовидную структуру:

Каждый номер будет абзацем.Я хочу иметь возможность выбрать все параграфы в каждой уникальной сюжетной линии.В основном, эти уникальные сюжетные линии (2, 7, 2);(2, 7, 6, 5);(2, 7, 6, 11) и (2, 5, 9, 4).Не обращая внимания на то, что узел «2» появляется дважды, я просто взял диаграмму древовидной структуры из Википедии.

Я также сделал диаграмму предложенного решения: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

Как настроитьструктура эффективна как для записи, так и для чтения?

Answer 1

Существует ряд хорошо известных способов представления деревьев в базах данных; У каждого из них есть свои плюсы и минусы. Вот наиболее распространенные:

• Список смежностей , где каждый узел хранит идентификатор своего родителя.
• Материализованный путь , который описывает стратегия Кейура. Это также подход, используемый группами сущностей (например, родительскими сущностями) в App Engine. Это также более или менее то, что вы описываете в своем обновлении.
• Вложенные множества , где каждый узел имеет «левый» и «правый» идентификаторы, так что все дочерние узлы содержатся в этом диапазоне.
• Списки смежности, дополненные корневым идентификатором.

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

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

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

Однако в вашем конкретном случае кажется, что вам на самом деле вообще не нужна древовидная структура: каждая история, пусть и разветвленная от оригинала, стоит одна. Я хотел бы предложить модель Story, которая содержит список ключей своих абзацев (например, в Python a db.ListProperty (db.Key)). Чтобы воспроизвести историю, вы выбираете историю, а затем делаете пакетную выборку для всех абзацев. Чтобы создать ветку, просто продублируйте статью, оставив ссылки на «Параграфы» без изменений.

Answer 2

Одно решение, о котором я могу подумать, - путь к узлу также является ключом этого узла.Таким образом, ключ узла 11 - «2/7/6/11».Вы можете пройти путь простым поиском всех ключей в пути - «2/7/6/11», «2/7/6», «2/7», «2»