Clasificación de árbol con una ruta materializada?

Question

Tengo una estructura de árbol en una tabla y usa rutas materializadas para permitirme encontrar niños rápidamente. Sin embargo, también tengo que ordenar los resultados primero, como se esperaría con las respuestas del foro enhebrado.

id | parent_id | matpath |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 

Así que los resultados finales en realidad debería ser ordenados así:

id | parent_id | matpath |   created 
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 

¿Cómo voy a trabajar en eso? ¿Puedo hacer eso en SQL directo (esto es PostgreSQL 8.4) o debería agregarse información adicional a esta tabla?

Actualización: tratando de explicar mejor los criterios de clasificación.

Imagine que id '1' es la publicación raíz de un foro y todo lo que tiene un 'matpath' que comienza con '1' es hijo de esa publicación. Entonces los ids 2 a 5 son respuestas directas a 1 y obtienen los matpaths de '1'. Sin embargo, id 6 es una respuesta 2, no directamente a 1, por lo que obtiene un matpath de 1.2. Esto significa que para un foro roscado con anidamiento adecuado, con todos los identificadores que se muestran en las tablas, la estructura del foro se vería así, por lo tanto, el requisito de pedido:

* id 1 (root post) 
    * id 2 
     * id 6 
      * id 8 
    * id 3 
    * id 4 
    * id 5 
     * id 9 
    * id 7 

Answer 1

normalmente creo una columnn adicional para esto, llamado algo así como SortPath. Contendría los datos que necesita ordenar, concatenados juntos. Esa columna sería del tipo varchar y se ordenaría como una cadena. Algo como esto:

id | parent_id | matpath |   created   |     sortpath 
---+-----------+---------+-----------------------------+-------------------------------------------------------------------------------------- 
2 |   1 | 1  | 2010-05-08 15:18:37.987544 | 2010-05-08 15:18:37.987544-2 
6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6 
8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8 
3 |   1 | 1  | 2010-05-08 17:38:14.125377 | 2010-05-08 17:38:14.125377-3 
4 |   1 | 1  | 2010-05-08 17:38:57.26743 | 2010-05-08 17:38:57.267430-4 
5 |   1 | 1  | 2010-05-08 17:43:28.211708 | 2010-05-08 17:43:28.211708-5 
9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9 
7 |   1 | 1  | 2010-05-08 18:18:11.849735 | 2010-05-08 18:18:11.849735-7 

Un par de cosas a la nota aquí:

• sortpath se ordenan como una cadena, por lo que es importante todas las fechas tienen la misma longitud para que correctamente especie. Por ejemplo, observe cómo 2010-05-08 17:38:57.26743 tiene un cero adicional agregado en la columna sortpath.
• He agregado el PK de cada nodo al final de su fecha. Esto es para que, si tienes dos filas con la misma fecha, siempre se devuelvan en el mismo orden debido a los datos adicionales que estamos agregando.
• Para mí, los datos se ve asimétrica de la manera que lo he escrito, porque estamos mostrando la fecha del nodo actual en sortpath, pero no lo es en matpath. Preferiría verlo en ambos.
• También le conviene poner la fecha del nodo ID 1 al comienzo de cada sortcolumn. Esto es para que, si alguna vez desea consultar más de un foro a la vez (probablemente no lo hará), aún así se clasifique correctamente.

Answer 2

Creo que su ruta materializada no es correcta.

¿Qué lógica se llega a ordenar las cosas como esta

1 
1.2 
1 
1.5 

¿Por qué es el segundo 1 no junto con la primera?

Si tuviera

1 
1.2 
2 
2.5 

Esto sería trivial.

EDIT: He visto su ejemplo y no está almacenando la ruta materializada de una fila, pero está almacenando una ruta materializada de la fila primaria. Así es como debe verse la ruta materializada de la fila. Clasificar directamente en matpath funcionaría si no tendría más de 9 sucursales si está almacenado como:

id | parent_id | matpath |   created 
----+-----------+-----------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 

lo contrario (> 9) que tendría que girar el matpath en algo así como

001.002.006 
001.002.006.008 

que soportaría hasta 999 sucursales.

Tenga en cuenta

• incluso el enfoque con 4 dígitos fijos, tales como 0001.0002.0006 le daría un campo que es más corto que en la respuesta aceptada
• se ha podido analizar matpath un valor de clasificación de los productos sobre la marcha con una función de usuario
• podría almacenar directamente matpath en este formato (que tiene algunas otras propiedades agradables, también)

Answer 3

no puedo pensar en una manera simple de haz esto en SQL directo. En lugar de matpath, usaré node_path aquí. node_path es matpath || '' || Identificación

id | parent_id | node_path |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 

Ahora usted quiere ordenar el árbol basado en node_path, con el campo de clasificación definido por el número de veces que se ha ejecutado el estilo.

Una función recursiva personalizada en plpgsql ordenando en split_part (node_path, '.', Recursion_depth) funcionará. Deberá verificar los valores NULL de split_part (e ignorarlos).

Answer 4

No estoy seguro de entender por qué la solución aceptada tiene algún sentido. Funciona, pero está aún menos normalizado y es menos eficiente (más espacio en disco, más índices, etc.) que la solución de @ Unreason (para rellenar los ID en la ruta materializada).

Todo el escenario al que se enfrentan OP parece provenir del hecho de que, como @Unreason señala correctamente, la implementación de la ruta materializada (MP) es incorrecta. El OP ha proporcionado el MP al padre, no al nodo actual. En la solución aceptada, la columna SortPath corrige esto proporcionando la ruta materializada al nodo actual (esta vez usando fechas, ¿por qué? - en lugar de la clave principal).

Como referencia considere lo siguiente excerpt:

Ruta

materializa en este enfoque cada registro almacena toda la ruta a la raíz. En nuestro ejemplo anterior , supongamos que KING es un nodo raíz. Luego, el registro con esame = 'SCOTT' se conecta a la raíz a través de la ruta SCOTT-> JONES-> KING. Las bases de datos modernas permiten representar una lista de nodos como un valor único, pero dado que la ruta materializada ha sido inventada mucho antes, la convención se mantuvo en el carácter simple cadena de nodos concatenados con algún separador; más amenudo '.' o '/'.

Answer 5

Mientras @ respuesta de Unreason acerca de las obras de relleno, me gustaría ofrecer otra solución que creo que es mi invención a este problema.

Usted está buscando función de creación de una corriente de bytes, un f(x)=b_1b_2..b_i (lo siento no MatJax el SO), donde b_i es un byte. Sabemos que dos bytestream se comparan de la misma manera que el primer byte diferente. Queremos una función tal que f(x)<f(y) iff x<y.

Relleno a la misma longitud con 0 sin duda obtiene este objetivo, fácilmente. Tomas dos números, miras el primer byte distinto de cero y allí estás.

Steven Wittens (acko.net) introdujo un truco diferente al núcleo de Drupal hace unos ocho años: poner el número de dígitos en la parte delantera de la cadena como otro dígito. Entonces, el número 97685 se convierte en los caracteres 5 9 7 6 8 5. Esto también funciona: primero mira el byte de longitud, si no son lo mismo, el más grande será definitivamente el más grande. Más allá de eso, sabes que los dos números son de igual longitud. También usó los números base 36 con 0-9a-z siendo los dígitos, como el hexágono solo para cada letra. Esta codificación necesita dos bytes para los primeros 36 nodos, tres para el próximo 1260 ...

Tenga en cuenta que ni el relleno ni esta astuta codificación de longitud variable necesitan separadores para la ruta materializada aunque a menudo se incluyen para la legibilidad.

numconv soporta una codificación base85 pero que requiere una intercalación sensible caso. Hay 94 caracteres ASCII si elimina letras minúsculas, usted todavía tiene base68.

Pero si usa un campo 'binario', puede hacer base256: en lugar de una codificación astuta simplemente escriba el número como una serie de bytes y luego prefija todo con la longitud del bytest como un solo byte. Esto le permitirá codificar cualquier árbol de menos de 2^2048 o menos. Para los primeros 256 nodos, está utilizando dos bytes, para el siguiente 65280 está buscando tres bytes. Esto ya es bastante eficiente.

designo a la función utf8encode(x). ¡Considere eso! Necesitas descender a la clasificación de bits en vez de a la ordenación de bytes, pero eso no cambia el resultado: busca el bit cero más a la izquierda. Si la otra cadena tiene un 1 allí, será una codificación UTF-8 más larga, así que definitivamente es más grande. Si tienen el primer cero en el mismo lugar, tenemos cadenas de bits de la misma longitud que nos comparan bien.

Eso es bueno, pero qué pasa con los separadores. El algoritmo UTF-8, al verlo como un algoritmo que crea bitstreams, puede manejar números de 31 bits, por lo que funcionará para árboles que contengan menos de dos mil millones de nodos. Su ruta materializada será un flujo de bits de números codificados en UTF-8 que se comparan bien: descarte los números codificados UTF-8 más a la izquierda y volvemos al párrafo anterior. Q.E.D.

Como no necesitamos separadores ni prefijos de bytes, podemos codificar los primeros 128 nodos en un solo byte, luego el siguiente 1920 en dos bytes y hasta 65535, tres bytes. Para cuatro bytes, base256 ganará. Para árboles muy grandes, puede tratar UTF-8 como un codificador de 0-2147483647 en una secuencia de bytes. Entonces puede usarlo como codificación base2147483647: D

Resumiendo: UTF-8 es mejor para árboles pequeños y no mucho peor que base256 por debajo de dos mil millones de nodos. Más allá de eso hasta 2^2048 o menos prefixed-with-length-base256 gana. Más allá de eso, prefixed-with-length-base2147483647 gana y no hay nada más allá de eso.