Сохранение иерархии каталогов в хранилище данных с ключом

Что такое чистый/эффективный метод для хранения каталога Hierarchy/tree в базе данных Key-Value (в моем случае MongoDB, но любой из них)?

Например, древовидная структура

- Cars 
   + Audi 
   + BMW
      - M5
   + Ford
- Color
   + Red
      - Apple
      - Cherry
   + Purple
- Funny

Метод, который я использую сейчас, каждый объект ссылается на него parent

{ 
  dir: "red"
  parent-dir: "color"
}

Это очень эффективно/быстро вставляет и изменяет порядок любого аспекта дерева (например, если я хочу переместить Red и все его дочерние элементы в каталог Cars).

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

{ 
  dir: "red"
  children: "audi, bmw, ford"
}

{ 
  dir: "bmw"
  children: "m5"
}

Но если я хочу изменить дерево, нужно добавить и изменить целую кучу объектов.

Существуют ли какие-либо другие способы хранения структуры каталогов в хранилище KV?

Ответы

Ответ 1

Используемый вами метод теперь называется модель списка смежности.

Еще одна модель для хранения иерархических данных в (реляционной) базе данных - это вложенная модель набора. Реализация в SQL-базах данных хорошо известна. Также см. эту статью для измененного алгоритма обхода дерева предзаказов.

Очень простой метод: вы можете сохранить путь для каждого объекта - с теми, которые должны быть легко запрошены деревья в базах данных NOSQL:

{ path: "Color", ... }
{ path: "Color.Red", ... }
{ path: "Color.Red.Apple", ... }
{ path: "Color.Red.Cherry", ... }

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

edit: этот метод называется материализованным путем

Наконец, здесь сравнение различных методов для иерархических данных в базах данных NOSQL.

Ответ 2

У меня нет большого количества опыта NOSQL, так что это не окончательный ответ, но вот как я подхожу к нему:

Я бы, скорее всего, использовал ваш первый подход, где у вас есть:

{
  dir: 'dir_name',
  parent_dir: 'parent_dir_name'
}

И затем настройте map-reduce, чтобы быстро запросить дочерние элементы каталога. Функциональность map-reduce MongoDB по-прежнему доступна только в ветке разработки, и я еще не работал с ней, но в CouchDB (и я предполагаю, что с некоторыми изменениями в MongoDB) вы можете сделать что-то вроде:

map:
function(doc) {
  emit( doc.parent_dir, doc.dir );
}

reduce:
function(key, values) {
  return( values );
}

Что даст вам список подкаталогов для каждого родительского каталога.

Ответ 3

Я предлагаю сохранить кучу в идентификаторе элементов данных. Я думаю, что это лучший план. Если вам нужно много и много вещей, любой кучный элемент может быть индексом для другой кучи.

eg

{ "id:xxx", "id:yyy", "sub-heap-id:zzz"....}

Если это неясно, напишите комментарий, и я объясню больше, когда вернусь домой.