Хранение иерархии каталогов в хранилище данных ключ-значение

Question

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

например

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

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

Answer 4

Сделайте индекс!

http://www.mongodb.org/display/DOCS/Indexes