Древовидные структуры в базе данных nosql
Я разрабатываю приложение для 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
Как настроить структуру, которая эффективна как для записи, так и для чтения?
2 ответа
Существует ряд хорошо известных способов представления деревьев в базах данных; У каждого из них есть свои плюсы и минусы. Вот наиболее распространенные:
- Список смежности, где каждый узел хранит идентификатор своего родителя.
- Материализованный путь, который описывает стратегия Кейура. Это также подход, используемый группами сущностей (например, родительскими сущностями) в App Engine. Это также более или менее то, что вы описываете в своем обновлении.
- Вложенные множества, где каждый узел имеет "левый" и "правый" идентификаторы, так что все дочерние узлы содержатся в этом диапазоне.
- Списки смежности дополнены корневым идентификатором.
У каждого из них есть свои преимущества и недостатки. Списки смежности просты и дешевы для обновления, но для получения поддерева требуется несколько запросов (по одному на каждый родительский узел). Расширенные списки смежности позволяют получить целое дерево, сохраняя идентификатор корневого узла в каждой записи.
Материализованные пути просты в реализации и дешевы в обновлении и позволяют запрашивать произвольные поддеревья, но увеличивают накладные расходы для глубоких деревьев.
Вложенные наборы сложнее в реализации и требуют обновления, в среднем, половины узлов каждый раз, когда вы делаете вставку. Они позволяют запрашивать произвольные поддеревья без материализации пути увеличения длины ключа.
Тем не менее, в вашем конкретном случае кажется, что на самом деле вам вообще не нужна древовидная структура: каждая история, пусть и разветвленная от оригинала, стоит одна. Я хотел бы предложить модель Story, которая содержит список ключей своих абзацев (например, в Python a db.ListProperty(db.Key)). Чтобы воспроизвести историю, вы выбираете историю, а затем делаете пакетную выборку для всех абзацев. Чтобы ветвить историю, просто продублируйте запись истории, оставив ссылки на абзацы без изменений.
Одно решение, о котором я могу подумать, - путь к узлу также является ключом этого узла. Таким образом, ключ узла 11 - "2/7/6/11". Вы можете пройти путь простым поиском всех ключей в пути - "2/7/6/11", "2/7/6", "2/7", "2"