Almacenamiento de la jerarquía de directorios en un almacén de datos clave-valor

Question

¿Qué es un método limpio / eficiente para almacenar el directorio Jerarquía / árbol en una base de datos de Key-Value (en mi caso MongoDB, pero cualquiera de ellos)?

Por ejemplo, una estructura de árbol

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

El método que estoy usando ahora, cada objeto se enlaza con su padre

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

Esto hace que sea muy eficiente / rápido para insertar y reordenar cualquier aspecto del árbol (por ejemplo, si quiero mover Rojo y todos sus hijos al directorio de Coches).

Pero este método apesta cuando quiero todos los subdirectorios y sus hijos para un directorio dado recursivamente. Para que sea eficiente analizar, puedo tener una estructura, por ejemplo,

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

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

Pero si quiero modificar el árbol, es necesario tocar y modificar una gran cantidad de objetos.

¿Existen otros métodos para almacenar una estructura de directorios en un almacén KV?

Answer 1

El método que utiliza actualmente se llama modelo de lista de adyacencia .

Otro modelo para almacenar datos jerárquicos en una base de datos (relacional) es el modelo de conjunto anidado . Su en las bases de datos SQL es bien conocida . También vea este artículo para el algoritmo transversal del árbol de preorden modificado .

Un método muy simple: podría almacenar una ruta por objeto, con los que debería ser fácil consultar árboles en bases de datos NOSQL:

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

Cuando se eliminarán o cambiarán de nombre los nodos, se deben actualizar algunas rutas. Pero en general, este método parece prometedor. Solo tienes que reservar un carácter especial como separador. La sobrecarga de espacio de almacenamiento debe ser despreciable.

editar: este método se llama ruta materializada

Finalmente, aquí está una comparación de diferentes métodos para datos jerárquicos en bases de datos NOSQL .

Answer 2

No tengo una gran cantidad de experiencia con NOSQL, por lo que esta no es una respuesta definitiva, pero así es como lo abordaría:

Probablemente usaría tu primer enfoque, donde tienes:

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

Y luego configure una reducción de mapa para consultar rápidamente los hijos de un directorio. La funcionalidad de reducción de mapas de MongoDB todavía está disponible solo en la rama de desarrollo y todavía no he trabajado con ella, pero en CouchDB (y supongo que, con algunas modificaciones, en MongoDB), podría hacer algo como:

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

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

Lo que le daría la lista de subdirectorios para cada directorio padre.

Answer 3

Sugiero almacenar un montón para el ID de los elementos de datos. Creo que este es el mejor plan. Si necesita muchas cosas, cualquier elemento del montón podría ser un índice para otro montón.

por ejemplo

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

Si esto no está claro, publique un comentario y le explicaré más cuando llegue a casa.

Answer 4

Haz un índice!

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