Estructuras de árbol en una base de datos nosql

Question

Estoy desarrollando una aplicación para Google App Engine que usa BigTable para su almacén de datos.

Es una aplicación sobre cómo escribir una historia en colaboración. Es un proyecto de hobby muy simple en el que estoy trabajando solo por diversión. Es de código abierto y lo puedes ver aquí: http://story.multifarce.com/

La idea es que cualquier persona puede escribir un párrafo, que luego debe ser validado por otras dos personas. Una historia también se puede ramificar en cualquier párrafo, de modo que otra versión de la historia pueda continuar en otra dirección.

imaginar la siguiente estructura:

Cada número sería un párrafo. Quiero poder seleccionar todos los párrafos en cada línea de historia única. Básicamente, esas historias únicas son (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) y (2, 5, 9, 4). Ignore que el nodo "2" aparece dos veces, solo tomé un diagrama de estructura de árbol de Wikipedia.

También hice un diagrama de una solución propuesta: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

¿Cómo puedo configurar una estructura es un rendimiento eficiente tanto para la escritura, pero lo más importante para la lectura?

Answer 1

una serie de formas bien conocidas de representar árboles en bases de datos; cada uno de ellos tiene sus pros y sus contras. Estos son los más comunes:

• Adjacency list, donde cada nodo almacena el ID de su elemento primario.
• Materialized path, que es la estrategia que describe Keyur. Este es también el enfoque utilizado por los grupos de entidades (por ejemplo, entidades padre) en App Engine. También es más o menos lo que describes en tu actualización.
• Nested sets, donde cada nodo tiene identificaciones 'izquierda' y 'derecha', de modo que todos los nodos secundarios están contenidos en ese rango.
• Listas de adyacencia con una ID de raíz.

Cada uno de estos tiene sus propias ventajas y desventajas. Las listas de adyacencia son simples y económicas de actualizar, pero requieren múltiples consultas para recuperar un subárbol (uno para cada nodo padre). Las listas de adyacencia aumentadas permiten recuperar un árbol completo almacenando la ID del nodo raíz en cada registro.

Las rutas materializadas son fáciles de implementar y económicas de actualizar, y permiten consultar subárboles arbitrarios, pero imponen una sobrecarga creciente para árboles profundos.

Los conjuntos anidados son más difíciles de implementar y requieren actualizar, en promedio, la mitad de los nodos cada vez que realiza una inserción. Le permiten consultar subárboles arbitrarios, sin el aumento de longitud de clave que tiene la ruta materializada.

En su caso específico, sin embargo, parece que en realidad no necesita una estructura de árbol en absoluto: cada historia, si bien puede ser bifurcada, es independiente.Lo que sugeriría es tener un modelo de "Historia", que contiene una lista de las claves de sus párrafos (por ejemplo, en Python a db.ListProperty (db.Key)). Para representar una historia, busca la historia y luego realiza una búsqueda por lotes para todos los párrafos. Para ramificar una historia, simplemente duplique la entrada de la historia, dejando sin cambios las referencias a Párrafos.

Answer 2

Una solución en la que puedo pensar es: la ruta al nodo también es la clave de ese nodo. Entonces, la clave del nodo 11 es "2/7/6/11". Puede recorrer la ruta mediante una simple búsqueda de teclas en todas las teclas de la ruta - "2/7/6/11", "2/7/6", "2/7", "2"