Подтвердить что ты не робот

Структуры дерева в базе данных nosql

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

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

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

Представьте себе следующую структуру дерева:

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

  • Список аджакции, где каждый node хранит идентификатор своего родителя.
  • Материализованный путь, который описывает стратегию Keyur. Это также подход, используемый группами объектов (например, родительскими объектами) в App Engine. Это также более или менее то, что вы описываете в своем обновлении.
  • Вложенные наборы, где каждый node имеет идентификаторы "left" и "right", так что все дочерние узлы содержатся в этом диапазоне.
  • Списки аджакции, связанные с идентификатором корня.

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

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

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

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

Ответ 2

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