Añadir jerarquía a nuestras colecciones de datos en PHP. Creando árboles en PHP

Es una práctica muy común categorizar nuestros. Hacer que existan categorías/sub-categorías/sub-sub-categorías sin límite al igual que directorios o carpetas hay en nuestro ordenador necesitamos tener todo clasificado. Es decir, queremos introducir jerarquía en nuestros datos, hacer que unos campos dependan de otros.
Pero cuando guardamos la información en base de datos, normalmente se guardarán en una tabla con dos dimensiones, por lo que perdemos esa sensación de que hay unos datos dentro de otros. Lo normal en estos casos, es que en cada fila de nuestra tabla haya un campo extra que apunta al identificador de la entrada que establecemos como padre.

Por ejemplo, si intentamos introducir categorías de pintura, tendremos por ejemplo:

La información que tendremos en nuestra tabla de base de datos será:

Añadiendo la entrada padre, esto quedará de la siguiente manera:

Ahora será fácil saber de dónde cuelga cada subcategoría. Podremos traer de base de datos los elementos pertenecientes al género histórico (id=4) buscando todos los elementos cuyo padre sea 4 y veremos 14, 15, 16, 17 y 18. También sabemos que las categorías raíz (las primeras que veremos) serán las que cuelgan de 0.

Lo bueno de esta técnica, es que la tabla puede ir rellenándose en la dirección que sea, es decir, podremos introducir de manera indiferente géneros, técnicas, etc (en el ejemplo están por orden para entendernos mejor, pero en la realidad esto puede llegar a ser un caos (técnicas, épocas, géneros y soportes entremezclados) ya que será la base de datos la que se encargue de traer los datos asociados en cada momento.

Hacer las consultas es fácil, pero ahora queremos tener en PHP un array con esta información de forma que la podamos manejar fácilmente. Una primera aproximación a la solución sería la siguiente:

• Sacamos de la base de datos los elementos que tienen como padre a 0
• Iteramos en ese array y consultamos en base de datos si cada uno de esos IDs tiene elementos (si tiene hijos, o si hay algún elemento cuyo padre sea el ID que estamos mirando en este momento)
  • Si tiene hijos, creamos una clave llamada 'elementos' y metemos ahí el resultado de la consulta.
  • Repetimos la operación con cada uno de los elementos que encontramos en la clave 'elementos'

Lo que nos daría una bonita función recursiva que debe funcionar muy bien (al menos al principio). El problema está en que cuando tengamos muchas categorías y éstas se estén consultando muchas veces, sobrecargaremos la base de datos de consultas y éstas tardarán un tiempo precioso en terminar.

Si ponemos como ejemplo las categorías de pintura, el algoritmo para crear ese array de PHP donde almacenaremos todas las categorías con su jerarquía sería el siguiente (consultas de base de datos en negrita):

• Pedir a base de datos las categorías cuyo padre es 0 (1)
• Recorremos las categorías:
  • Pedir a base de datos las categorías cuyo padre es 1 (Género) (2)
  • Recorremos las subcateogrías de 1, Género:
    • Pedir a base de datos las categorías cuyo padre es 4 (Histórica) (3)
    • Recorremos las subcategorías de 4, Histórica:
      Pedir a base de datos las categorías cuyos padres son: 14, 15, 16, 17, 18(8)
    • Pedir a base de datos las categorías cuyos padres son: 5, 6, 7 (11)
  • Recorremos las subcateogrías de 2, Técnica:
    Pedir a base de datos las categorías cuyos padres son: 8, 9, 10 (14)
  • Recorremos las subcateogrías de 3, Soporte:
    Pedir a base de datos las categorías cuyos padres son: 11, 12, 13 (17)

Lo que hace un total de 17 consultas a base de datos. Lo cual es inviable. Debemos de saber que es mucho más rápido pedir una cantidad de datos grande de una vez que hacer 17 peticiones pequeñas (lo segundo casi casi tarda 17 veces más). No es cuestión de pedir datos que no necesitamos, pero si por ejemplo queremos dibujar un árbol con las categorías sí que necesitamos tenerlas todas en memoria por lo que es mucho más rápido pedir una sola vez la tabla completa de subcategorías y trabajarla para obtener nuestro array final.

Para ello, podemos utilizar múltiples algoritmos, aunque uno muy rápido es el siguiente:

Esto nos creará una estructura con dos índices:

En el primero de ellos se irán almacenando cada uno de los elementos en bruto y en el segundo nuestra tan ansiada estructura en forma de árbol. La esencia de este algoritmo radica en su complejidad O(n) o lo que es lo mismo, realizaremos tantas operaciones como elementos totales haya en nuestra tabla de categorías. Con esto, nos quitamos un algoritmo recursivo (y la sobrecarga que produce) y lo hacemos tan sencillo como pasar datos de un lado a otro.
Lo que estamos haciendo aquí es copiar las referencias de cada uno de los elementos de la lista y no los elementos en sí. De esta forma, si la referencia de un elemento del índice 'children' tiene dos elementos hijos dentro de él la copiamos al índice 'root', cuando consultemos dentro de root, estaremos viendo los dos hijos; pero si ahora, le añadimos al mismo elemento dentro de children otro hijo, al consultarlo desde 'root' veremos este nuevo hijo. Lo mejor es que no se están realizando copias de datos completos, sino de referencias, por lo que, aunque veamos los mismos elementos en 'root' y en 'children' no están ocupando el doble.

Por lo general, esta función buildTree() admitirá un array de elementos, cada uno de esos elementos deberá ser un array y obligatoriamente, debemos tener una clave id y otra clave parentId (luego podremos hacerlo configurable si queremos). Por defecto al ID de la categoría o elemento raíz será 0.

He de decir también, que en este ejemplo, he revuelto el orden de los elementos, para que veamos que no importa en qué posición estén, es más, podemos incluso especificar los elementos hijos antes que los elementos padre (muy útil cuando queremos que vengan en un orden determinado en base de datos).
Foto: Robert Couse-Baker (Flickr CC-by)