Este artículo de hoy es para ingenieros y científicos en computación, y es uno que prometí desde que implementé el nuevo motor de blog de eliax 2.0 (actualmente en versión beta) en Febrero de este año, y lo que les mostraré es una técnica que les ayudará a acelerar enormemente estructuras de datos jerárquicas, con un truco lineal de mi autoría.

Pero primero, un poco de datos históricos de trasfondo para poner todo esto en contexto: Eliax anteriormente estaba alojado en un servidor dedicado (es decir, una sola máquina para el blog) y funcionaba bastante bien, pero habían muchas cosas que el motor de blog que utilizada en ese entonces (Serendipity) no hacía que no me gustaba, por lo que decidí tomarme un fin de semana y dedicárselo a escribir mi propio motor de blog, que es el que utilizan todos actualmente en eliax.

Obviamente pude haber utilizado otro motor como Wordpress, pero ¿en dónde está la diversión en eso? Sí, soy un geek, lo admito... :)

Sin embargo, quizás la razón principal de yo querer escribir mi propio motor de blog era ver qué tan rápido podía yo acelerar la parte de los comentarios (ya para inicios de este año algunos artículos de eliax contenían cientos de comentarios), y para eso decidí utilizar un truco que me inventé hace más de una década atrás, y que hoy comparto con ustedes.

Para que tengan una idea de lo que hablamos, me refiero a una simple técnica de código que les acelerará este tipo de operaciones entre varias veces y miles de veces más rapido (dependiendo de la profundidad del árbol jerárquico y los números de nodos de este).

Esta optimización, más otras tantas más, hicieron el nuevo motor de blog tan más rápido que el viejo, que pude dejar atrás el servidor dedicado y poner eliax en un simple servidor compartido (como con otras 50 páginas más).

Eso por un lado me ofreció un par de ventajas:

1. Un costo muchísimo menor (bajé de US$220 dólares mensuales a apenas unos US$15 dólares mensuales).

2. Muchísima más fácil administración (la empresa que aloja a eliax se encarga de todos los temas de actualizaciones, seguridad, gestión de servicios web, bases de datos, etc).

Sin embargo, obtuve una gran desventaja: Ahora cada vez que uno de esos otros 50 websites hace alguna operación extrema que hace que se caiga el servidor, eliax se cae también con esas páginas, razón por la cual a veces ven a eliax caído por unos segundos o incluso un par de minutos al día.

Debido a eso estoy contemplando regresar a un entorno de servidor dedicado, pero antes de hacer eso quería sacar este artículo para que prueben lo rápido del código aun en un ambiente de servidores compartidos.

Habiendo dicho todo eso, aquí vamos...

¿Cuál es el problema?
El problema a resolver es el siguiente: En foros (y lo mismo aplica a un sinnúmero de otros ambientes), se necesita almacenar datos de forma jerárquica, lo que hace el modelo de datos super-sencillo, pues para un blog el modelo puede ser tan simple como el siguiente esquema SQL (noten que he simplificado la sintaxis por motivos didácticos, y obviando por ejemplo temas de índexes, autoinc, llaves primarias, etc):

COMENTARIO_ID INT
PADRE_ID INT
FECHA_DE_ENTRADA TIMESTAMP
AUTOR CHAR
COMENTARIO TEXT

Con tan solo esa simple estructura es posible modelar una tabla para almacenar comentarios de forma jerárquica en algo como este mismo blog de eliax.

Noten que he obviado de este esquema un campo que se llame ENTRADA_DE_BLOG_ID que tendría el ID del artículo bajo el cual se está comentando. Lo he dejado fuera para simplificar el ejemplo, pero recuerden que obviamente se necesita un ID por artículo.

Veamos ahora como se almacenarían estos 3 comentarios (Ejemplo 1):

- Primer comentario por Jose Elias a las 10:00
   - Tercer comentario por Lector 2 a las 10:30
- Segundo comentario por Lector 1 a las 10:15

Estos los almacenaríamos de la siguiente manera (tomando en cuenta nuestro diseño de tablas de hace 3 párrafos atrás):

1, 0, 10:00, Jose Elias, Primer comentario
2, 0, 10:15, Lector 1, Segundo comentario
3, 1, 10:30, Lector 2, Tercer comentario

Noten ahora un par de cosas:

1. Cuando seteamos el valor de PADRE_ID a 0 queremos indicar que este comentario está en la raíz de los comentarios.

2. Cuando seteamos PADRE_ID a un valor igual o mayor a 1, queremos decir que este comentario es en respuesta al ID de ese otro comentario.

Esto es bastante eficiente para almacenar, pero tiene un grave problema a la hora de uno leer esos datos de la base de datos y desplegarlos: No podemos obtener la estructura completa en un formato listo para desplegar con una sola operación.

Es decir, tenemos que hacer una de estas dos operaciones:

1. Leer solo los nodos de la raiz (es decir, aquellos en donde PADRE_ID = 0), y después hacer más queries de SQL para saber cuáles son los comentarios hijos de esos, y repetir el proceso recursivamente hasta llegar a los últimos comentarios de cada rama del árbol.

2. Leerlo todo en memoria en una sola operación SQL, pero de todas maneras recorrer los datos de manera recursiva para "desenvolver" el árbol y poder desplegarlo.

En ambos casos, mientras más comentarios y más profundo sea el árbol de comentarios, más lento es este proceso.

Para que tengan una idea, leer tan solo 10 comentarios, en donde cada uno de ellos tenga 8 subcomentarios, y en donde cada uno de esos 8 subcomentarios tenga 5 sub-subcomentarios, requeriría de aproximadamente unas 400 operaciones distintas.

Hoy les voy a enseñar como hacerlo con una sola operación, acelerando (en este ejemplo) el tiempo de respuesta a 400 veces más rápidamente...

¿Cuál es la solución?
Primeramente, noten que deben existir varias soluciones a este problema, en particular dependiendo de ciertas variables del ambiente en donde se necesite la optimización. En mi caso, asumo las siguientes variables:

1. Esto es óptimo en ambientes en donde la proporción de lectura es mucho más alta que la de escritura. Es decir, en blogs como este de eliax, por cada persona que escribe un comentario quizás hay 1,000 más que simplemente leen. Por tanto, la optimización está pensada para lecturas y no para escrituras.

2. Asumiremos que tendremos un máximo de 1000 comentarios a nivel de raiz, y cada uno de ellos podrá tener 1000 subcomentarios, y esos subcomentarios tendrán cada uno un máximo de 1000, y así sucesivamente. Esta no es una limitación de mi técnica, sino que un límite de optimización. Como explicaré en unos momentos, pueden extender esos límites a prácticamente cualquier límite que deseen, pero a un precio a pagar en almacenamiento.

Habiendo dicho eso, primero estudiemos por qué con las técnicas tradicionales este tipo de esquemas de SQL distan mucho de ser óptimos...

A simple vista uno diría, ¿pero no es esto tan sencillo con simplemente hacer un query en orden cronológico por ID por fecha de creación del comentario? Es decir, algo como esto:

SELECT *
FROM COMENTARIOS
ORDER BY FECHA_DE_ENTRADA

Y la respuesta es que eso no funciona, ya que es posible poner comentarios en cualquier orden. Solo miren el ejemplo que dí, en donde el tercer comentario en realidad aparece primero que el segundo comentario, ya que este es un sub-comentario del comentario original.

Similarmente hay muchas posibles maneras de tratar de resolver el tema a nivel de SQL, pero en casi todos los casos, llegarán a un callejón sin salida en donde eventualmente tendrán que hacer más queries (y eso aplica, aunque no lo noten, a soluciones dedicadas para árboles en algunas bases de datos).

Entonces, el truco que ideé es el siguiente, y es bastante sencillo después que lo entiendan: ¿Qué tal, si de alguna manera podemos codificar informarción lineal, sobre la jerarquía? Y la respuesta es que se puede, y de la siguiente manera...

Volvamos a ver el ejemplo anterior, y de cómo almacenamos esos datos en la forma tradicional:

1, -1, 10:00, Jose Elias, Primer comentario
2, 0, 10:15, Lector 1, Segundo comentario
3, 1, 10:30, Lector 2, Tercer comentario

Como pueden ver, el reto es poder almacenar los datos de manera tal, que sin importar en qué orden insertamos los datos (y cuándo en el tiempo esos comentarios ocurrieron) que podamos representarlos todos de forma lineal, y por tanto poder hacer un solo query de SQL para obtenerlos todos.

El truco está en pensar en ordenarlos de manera lexicográfica, con un campo adicional que se decodifica automáticamente en el orden en que estos deben ser representados visualmente.

No se asusten, esto es muchísimo más sencillo de lo que suena, y la mejor manera de explicarlo es con un ejemplo. Tomemos el ejemplo anterior, y ahora agreguemos un nuevo campo que llamaremos ORDEN_DE_DESPLIEGUE que será nuestro último campo (de tipo texto y con un índice aplicado) para obtener esto:

1, -1, 10:00, Jose Elias, Primer comentario,001
2, 0, 10:15, Lector 1, Segundo comentario,002
3, 1, 10:30, Lector 2, Tercer comentario,001-001

Con esta información adicional, si ahora hacemos este query:

SELECT *
FROM COMENTARIOS
ORDER BY ORDEN_DE_DESPLIEGUE

Obtendremos los resultados de esta manera:

1, -1, 10:00, Jose Elias, Primer comentario,001
3, 1, 10:30, Lector 2, Tercer comentario,001-001
2, 0, 10:15, Lector 1, Segundo comentario,002

Como pueden apreciar, ahora los datos son devueltos a nosotros en el mismo orden que vimos con el ejemplo 1, en donde la idea es desplegarlos de esta manera en pantalla:

- Primer comentario por Jose Elias a las 10:00
   - Tercer comentario por Lector 2 a las 10:30
- Segundo comentario por Lector 1 a las 10:15

Pero, ¿y qué fue lo que hicimos? Pues analicemos cómo almacenamos los datos en el campo ORDEN_DE_DESPLIEGUE...

El truco está en almacenar los datos de forma lexicográfica (es decir, en orden alfabético) pero con numerales que se incrementan, y en grupos, en donde cada grupo representa un nodo del árbol.

Así que el primer nodo A se llamaría "001"
Un nodo B1 pegado como hijo a ese sería "001-001"
Así mismo un segundo nodo B2 pegado al nodo A sería "001-002"
Y un nodo C1 pegado a al subnodo B1 sería "001-001-001"
Mientras que un nodo C2 pegado al subnodo B2 sería "001-002-001"

Note que los nodos los estoy representando con un número de 3 dígitos que inicia en 001 (o 000 si lo prefieren) para un total de 999 (o 1000) nodos.

Noten además que cada hijo adicional de un nodo simplemente incrementa por 1 el valor del hijo anterior de ese nodo.

Así que una estructura compleja como esta:

A1
    B1
        C1
    B2
        C2
            D1
            D2
        C3
        C4
    B3
A2
    B4
        C5
            D3
        C6
        C7

Se almacenaría así (si eres Contable/Contador, reconocerás esta estructura):

A1 = 001
B1 = 001-001
C1 = 001-001-001
B2 = 001-002
C2 = 001-002-001
D1 = 001-002-001-001
D2 = 001-002-001-002
C3 = 001-002-002
C4 = 001-002-003
B3 = 001-003
A2 = 002
B4 = 002-001
C5 = 002-001-001
D3 = 002-001-001-001
C6 = 002-001-002
C7 = 002-001-003

Noten un par de cosas mas:

1. No es necesario poner el guión ("-") entre los números. Los puse simplemente para que sea más fácil visualizar el código, pero yo no los utilizo en la práctica.

2. Aunque con grupos de 3 dígitos dije que es posible almacenar hasta 1000 nodos por nodo, lo cierto es que nada les impide utilizar todo el abecedario ASCII (es decir, números del 0 al 1, y letras de la A a la Z) para lograr un rango mucho mayor, pero recuerden que al hacer eso insertan complejidad en el sistema. Esta debe ser una decisión a tomarse dependiendo del proyecto. Noten que otra forma de almacenar más nodos por nodo es simplemente agregando más dígitos. Por ejemplo, con 4 dígitos por grupo pueden almacenar 10,000 nodos por nodo, y con 6 hasta 1 millón de nodos por nodo. Sin embargo, este valor lo deben definir antes de implementar el sistema, pues obviamente afecta el espacio de almacenamiento necesario,

3. Espero se haya hecho obvio que lo que hemos hecho para lograr esta optimización de lectura, es disminuir un poco la velocidad de escritura, ya que ahora antes de insertar un nodo hay que tomar un nodo relacionado para o (1) aumentarlo por 1 o (2) agregar un nuevo nodo iniciando desde cero, así como además pre-almacenar el orden de despliegue del árbol. Es decir, intercambiamos espacio de almacenamiento y velocidad de escritura (más un poco de complejidad a la hora de insertar los datos) por un aumento masivo en la velocidad de lectura.

4. Noten que esto además ofrece otros beneficios que no son aparentes a primera vista. Por ejemplo, este truco sirve no solo para obtener todo el árbol en un solo query, sino que para obtener también cualquier sub-nodo. Así que por ejemplo, si en el ejemplo anterior deseo obtener solo los comentarios del subnodo B2, yo solo tendría que escribir el siguiente SQL:

SELECT *
FROM COMENTARIOS
WHERE ORDEN_DE_DESPLIEGUE LIKE '001-002%'
ORDER BY ORDEN_DE_DESPLIEGUE

Y si quisiera borrarlos:

DELETE
FROM COMENTARIOS
WHERE ORDEN_DE_DESPLIEGUE LIKE '001-002%'

¿Sencillo, no? :)

Noten que aunque utilicé "LIKE" en este ejemplo (que puede ser una operación cara), que en la práctica nunca hay que utilizarlo, ya que uno siempre pide el árbol como en el ejemplo anterior. Este ejemplo solo lo utilicé para ilustrar otras ventajas no aparentes a simple vista.

Algo que quiero repetir, es que es importante que el campo ORDEN_DE_DESPLIEGUE sea indexado, ya que este es el campo por el cual siempre ordenaremos el query que nos devuelva todos los comentarios.

Así que ahí lo tienen, espero esto les haya sido tan útil a ustedes como lo fue para mi crearlo y utilizarlo. Cualquier pregunta que tengan, u observaciones, correcciones, o incluso otras técnicas para hacer lo mismo, agradecería que lo compartieran con todos los demás lectores en los comentarios acá abajo...

Nota: Si quieren ver esto en acción, he aquí un artículo reciente en eliax con más de 300 comentarios, que como podrán observar, se cargan todos de forma casi instantánea (el límite está más bien en tu linea de Internet que en la capacidad del servidor de servir los datos - hasta cierto punto obviamente, pero eso ya es material para otro artículo futuro sobre super-escalabilidad a cientos de millones de usuarios).

autor: josé elías