While I've seen examples for nested sets, no he visto mucho para los intervalos anidados, aunque en teoría no debería ser difícil convertirlo de uno a otro. En lugar de realizar un recorrido de prepedido para etiquetar los nodos, realice una recursión de primer nivel. El truco es encontrar la manera más eficiente de etiquetar n niños de un nodo. Como el nodo entre a/byc/d es (a + c)/(b + d), un inserto mal acondicionado (por ejemplo, insertando a los niños de izquierda a derecha), corre el riesgo de crear el mismo crecimiento exponencial en los valores de índice como, por ejemplo, usando un materialized path completo. No es difícil contrarrestar este efecto: cree los nuevos índices de a uno por vez, insertando cada uno en la ubicación que produzca el denominador resultante más bajo.
En lo que respecta a la degradación del rendimiento, mucho depende de las operaciones que pretenda hacer. Todavía hay algunas operaciones que requerirán un reetiquetado completo de todo el árbol: el conjunto anidado o los métodos de intervalo anidado funcionan mejor para las estructuras que rara vez cambian. Si realiza muchos cambios de estructura en la jerarquía, es más fácil trabajar con la estructura de tabla padre-hijo 'estándar'. recuerde también que algunas operaciones (como el número de descendientes) son mucho más fáciles con el etiquetado entero de conjuntos anidados que con los métodos de intervalo.
Eche un vistazo a mi pregunta: http://stackoverflow.com/questions/1049748/improving-nested-sets-modified-preorder-tree-traversal Comente allí si lo desea. Estoy investigando este espacio también ahora. –
Es una idea increíblemente ingeniosa, lo daré. Pero, ¿es probable que sea más rápido que los punteros de los padres en una base de datos que admite consultas recursivas, como lo hacen las versiones recientes de todas las bases de datos serias (es decir, todo menos MySQL!). –