Древовидные структуры в 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»