Publi

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:

  • Género pictórico
    • Histórica
      • Prehistoria
      • Edad antigua
      • Edad media
      • Edad moderna
      • Edad contemporánea
    • Retrato
    • Paisaje
    • Bodegón
  • Técnica
    • Óleo
    • Cera
    • Acuarela
  • Soporte
    • Lienzo
    • Papel
    • Vidrio

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

ID Nombre
1 Género
2 Técnica
3 Soporte
4 Histórica
5 Retrato
6 Paisaje
7 Bodegón
8 Óleo
9 Cera
10 Acuarela
11 Lienzo
12 Papel
13 Vidrio
14 Prehistoria
15 Edad antigua
16 Edad media
17 Edad moderna
18 Edad contemporánea

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

ID Nombre Padre
1 Género  0
2 Técnica  0
3 Soporte  0
4 Histórica  1
5 Retrato  1
6 Paisaje  1
7 Bodegón  1
8 Óleo  2
9 Cera  2
10 Acuarela  2
11 Lienzo  3
12 Papel  3
13 Vidrio  3
14 Prehistoria  4
15 Edad antigua  4
16 Edad media  4
17 Edad moderna  4
18 Edad contemporánea  4

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
<?php
$ex = array(
array('id' => 1,
'nombre' => 'Género',
'parentId' => 0),
array('id' => 2,
'nombre' => 'Técnica',
'parentId' => 0),
array('id' => 3,
'nombre' => 'Prehistoria',
'parentId' => 7),
array('id' => 4,
'nombre' => 'Edad antigua',
'parentId' => 7),
array('id' => 7,
'nombre' => 'Histórica',
'parentId' => 1),
array('id' => 5,
'nombre' => 'Óleo',
'parentId' => 2),
array('id' => 6,
'nombre' => 'Retrato',
'parentId' => 1),
array('id' => 8,
'nombre' => 'Soporte',
'parentId' => 0),
array('id' => 9,
'nombre' => 'Lienzo',
'parentId' => 8),
array('id' => 10,
'nombre' => 'Edad media',
'parentId' => 7),
array('id' => 11,
'nombre' => 'Paisaje',
'parentId' => 1),
array('id' => 12,
'nombre' => 'Bodegón',
'parentId' => 1),
array('id' => 13,
'nombre' => 'Cera',
'parentId' => 2),
array('id' => 14,
'nombre' => 'Acuarela',
'parentId' => 2),
array('id' => 15,
'nombre' => 'Papel',
'parentId' => 8),
array('id' => 16,
'nombre' => 'Vidrio',
'parentId' => 8),
array('id' => 17,
'nombre' => 'Edad moderna',
'parentId' => 7),
array('id' => 18,
'nombre' => 'Edad contemporánea',
'parentId' => 7),
);

function buildTree($data, $rootId=0)
{
$tree = array('children' => array(),
'root' => array()
);
foreach ($data as $ndx=>$node)
{
$id = $node['id'];
/* Puede que exista el children creado si los hijos entran antes que el padre */
$node['children'] = (isset($tree['children'][$id]))?$tree['children'][$id]['children']:array();
$tree['children'][$id] = $node;

if ($node['parentId'] == $rootId)
$tree['root'][$id] = &amp;$tree['children'][$id];
else
{
$tree['children'][$node['parentId']]['children'][$id] = &amp;$tree['children'][$id];
}

}
return $tree;
}

print_r(buildTree($ex));

Esto nos creará una estructura con dos índices:

  • children
  • root

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)

También podría interesarte...

There are 6 comments left Ir a comentario

  1. Pingback: Cómo encontrar la ruta de un elemento dentro de una jerarquía en PHP | Poesía Binaria /

  2. CLaudio /
    Usando Mozilla Firefox Mozilla Firefox 38.0 en Linux Linux

    hola amigo buen escript, esto creo que seria util poner:
    <?php
    $tree=buildTree($ex);
    imprimir($tree['root']);

    function imprimir($tree) {
    echo '’;
    foreach ($tree as $row) {
    echo ”;
    echo $row[‘nombre’];
    if ( count( $row[‘children’] ) > 0 ) {
    imprimir( $row[‘children’] );
    }
    echo ”;
    }
    echo ”;
    }

    1. Gaspar Fernández / Post Author
      Usando Mozilla Firefox Mozilla Firefox 38.0 en Ubuntu Linux Ubuntu Linux

      Gran idea. Así podemos hacer la visualización más amena que con un simple print_r() o var_dump()
      Gracias!

  3. Romulo /
    Usando Google Chrome Google Chrome 45.0.2454.101 en Windows Windows XP

    Hola Grupo! observo que una cosa es que estén agrupados y otra es la estructura
    para el nivel 0 to dos cuelgan , pero para los demás no dice la estructura mas si se sabe que están agrupados
    En resumen Agrupación 1 ,2,3 están al mismo nivel
    Agrupación 4 esta al tercer nivel

    1. Gaspar Fernández / Post Author
      Usando Mozilla Firefox Mozilla Firefox 41.0 en Ubuntu Linux Ubuntu Linux

      Hola Romulo,

      No sé exactamente a lo que te refieres, pero en el array, como primer nivel tenemos ‘root’ y ‘children’, en ‘root’ están todos, lo tomamos como referencia para crear ‘children’, bajo ‘children’ sí que encontramos la estructura bien definida.

      De todas formas, el espacio en memoria no es doble, ya que lo que estamos almacenando en root son las referencias a los nodos.

  4. Carlos /
    Usando Mozilla Firefox Mozilla Firefox 53.0 en Ubuntu Linux Ubuntu Linux

    Saludos amigos; tengo un problema. El iDe netbeans me detecta como error &amp
    alguien sabe como solucionarlo 🙁

Leave a Reply