texto:   A-   A+
eliax

Un algoritmo eliax: Una forma super-eficiente de almacenar datos jerárquicos, linealmente
eliax id: 7303 josé elías en nov 8, 2010 a las 12:09 AM (00:09 horas)
eliax.com - Para Mentes CuriosasEste 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

Comentarios

  • Simplemente genial! Sé que ahora no tengo los conocimientos para usarlo, pero de aquí a unos años entraré a este post y lo usaré :)

  • Buenísima la idea! No dudes que lo vaya a implementar en cualquier sistema jerárquico que necesite jaja gracias ^^

  • Mi solución sería, guardar todos los comentarios en un archivo XML o JSON y cuando se consulten y se extraiga el registro, el mismo parcearlo del lado del cliente, asi el que se gasta en la consulta es el cliente y no el servidor. El servidor solo envia el contenido del resultado de evaluar la consulta de seleccion.

    • Carlos,

      El problema con esa solución (que me la encuentro bastante buena también), es que se vuelve cada vez más ineficiente conforme se agregan más comentarios (pues para insertar algo en el árbol de XML, hay que parsear y buscar en el arbol).

      Con mi solución, el tiempo de inserción de nodos en el árbol es siempre constante, independientemente del tamaño del árbol.

      • Bueno, el trabajo en definitiva es más o menos el mismo sólo que con tu solución el que se encarga de hacerlo es el motor SQL al generar el índice. Aunque, claro, es probable que el SQL sea más eficiente porque está especializado en eso.

        • exacto, además creo también que el predicado con LIKE hace mas lento el trabajo de consulta. ahora mismo no recuerdo donde dice que usar LIKE hace mas lento el motor de la db en los procesos de busqueda. Alguién podrìa tener tema tesis con esto que estamos hablando acá, jajaja.

      • Jejeje, realicè pruebas con tu soluciòn y la mìa y la verdad la diferencia no se nota..., es màs hice la prueba con arboles con n=300 de profundidad,... igual la computación avanza cada vez mas rapido y esto es imperceptible, sumándole el hecho que el desgaste de busqueda e inserción en el arbol se haría del lado del cliente, luego en el servidor se procede a insertar el registro y listo. Como duda quedaría probar con mas profundidad en busqueda, no se diría yo como un n=3000 o algo mayor, para ver las diferencias.

        • Carlos,

          Una cosa que siempre le decía a mis estudiantes universitarios era que es una cosa probar algo en tu PC, y otra probarlo en un ambiente con miles de usuarios simultáneos como ocurre normalmente con eliax.

          En una PC moderna, prácticamente cualquier algoritmo, por más ineficiente que sea, funcionará "rápidamente". La única manera de simularlo es o (1) haciendo casos extremos, como por ejemplo, con millones de nodos, o (2) con frameworks que te simulan al menos cientos de usuarios, o (3) en la vida real en un ambiente con mucho tráfico de datos.

          En mi caso, se que la solución que propongo es más rápida porque lo medí empíricamente.

          Aun así, no digo que lo que propones con XML no sea una buena solución, sino que para mi caso acá en eliax, mi método aparenta ser más eficiente.

          • Bueno, como lo que dices es para mì un reto, apenas saque tiempo harè las pruebas de fatiga con un blog sencillo implementando ambas soluciones y mirando con al menos 1 millon de nodos de profundidad para el caso del XML y tambien para el caso que implementas para la DB. Algo que podrìa ya visualizar en ambos casos es lo siguiente:
            - la consulta LIKE.... sobrecarga el servidor o conjunto de servidores que tengan la DB eso, ya ha sido demostrado en articulos. De hecho hay articulos en los cuales se proponen soluciones para optimizar el uso de las consultas en donde se usa el operador LIKE.
            - Usar un XML, aún del lado del cliente hace que el proceso con muchos nodos coloque el navegador lento. mmm, con mucha profundidad se hace ineficiente. Soluciòn, solo parsear un parte del XML, la que se necesite, y por decirlo asì "paginar el archivo XML".

            Apenas pueda como te dije, reviso ambos casos, con la extensión de chrome: Speed Tracer (by Google) - buen momento para checar esta extensión- y te paso los resultados.

            • Hola Carlos,

              Recuerda algo: En mi solución NO se necesita ni siquiera un solo LIKE. Simplemente utilicé un ejemplo de LIKE para demostrar otros posibles usos de este algoritmo.

              En realidad, y como expliqué en el artículo, el único código SQL que necesito para leer y para parsear todo el arbol para un artículo determinado (digamos, el artículo #123), es este:

              SELECT *
              FROM COMENTARIOS
              WHERE ARTICULO = 123
              ORDER BY ORDEN_DE_DESPLIEGUE

              Y es contra ese SQL que debes hacer tus pruebas, es decir:
              1. Leer el XML de la base de datos
              2. Parsear el árbol del artículo 123 de los nodos XML.

              Nota, y repito, que con mi solución NO es necesario parsear el árbol, ya que viene naturalmente ordenado. Debido a eso es que dudo mucho que una solución basada en XML sea más rápida que mi implementación.

              • Eliax, si es posible porfa, pasame tu algoritmo, para medir la complejidad del mismo, vs la opcion que tengo.

  • Me parece sencillamente genial!! Y vi el articulo con 300 comentarios y me sorprende la eficacia. Y es muy facil de entender cuando se indexa!
    Felicitaciones, y seguro lo tendré en cuenta cuando necesite de jerarquía y ramificaciones,
    Gracias y Felicitaciones!

  • Esto es muy comun en manejo de contenido de informacion y MySQL tiene muchas formas facil de manejarlo. Lo que estas haciendo es duplicando tiempo de lectura e incrementando el tamano de la base de datos al anadirle otro campo para almacenar un string con tu mapa de "que comentarios va primero".

    Esto se hace simplemente teniendo 2 llaves foraneas absolutas en las tablas de tus comentarios y relacionandolas entre si.

    Es truco viejo, no hay que reinventar la rueda, pero sirve para "prueba de concepto" ;)

    Saludos...

    • Juan,

      ¿Podrías explicar el truco de utilizar 2 llaves foráneas absolutas para ver si en realidad es una solución al problema? Este tipo de problemas me interesa y quisiera saber si de verdad lo que dices funciona y si tiene sus ventajas por sobre este método (pues siempre quiero optimizar cosas).

      Y nota que pregunto porque antes de crear mi método, analicé el código fuente de muchos sistemas de blogs y almacenamientos jerárquicos, y todos tienen la deficiencia que resuelvo con este método.

      • Entonces ha llegado la hora de patentar el algoritmo! Apúrese don Elias!

      • Jose, *asumiendo* que tienes 2 campos PADRE_ID y ORDEN_DE_DESPLEGUE.

        No seria mas eficiente quitar el padre_ID y calcularlo con la informacion del ORDEN_DE_DESPLEGUE ?....

        Osea si el orden_de_desplegue solo tiene ### es raiz, si es ###-###[-###...] es comentario de otro.. o, contar los "-" que tiene y asi determinar el padre_id.

        Por cierto, ya daba por olvidado esta entrada. Gracias por no olvidarlo :-)

        por cierto faltan los ICONOS y formatos en los comentarios :-P

        • Anonimo,

          En realidad, en mi caso decidí dejar el PADRE_ID deliberadamente, pues no afecta el rendimiento de los queries en la práctica, y el almacenamiento que ocupa es negligible.

          Una buena razón para dejarlo es que es más eficiente utilizar el PADRE_ID para aquellas operaciones en donde requiera el padre de un nodo (a diferencia de tener que deducirlo restando un grupo de dígitos del campo ORDEN_DE_DESPLIEGUE).

          Otra razón es que es también más eficiente conseguir los nodos hijos (pero sin los nietos) directamente pegados a un Nodo.

          Como dije al inicio del artículo, todo depende de las variables que manejes en tu aplicación, por eso la importancia de uno sentarse a pensar antes de escribir código :)

      • En normalizacion de base de datos este caso es una excepcion ya que por cada subnivel sale una nueva tabla, por lo tanto se resuelve realizando una foreign key a la misma tabla

        Id, ParentId
        FOREIGN KEY (ParentId) REFERENCES selfTable(Id))

        y para comodidad se le adiciona la columna Level

        Saludos

        • Eso es mucho menos eficiente que este método de eliax, y más complicado.

    • Yo llevo 20 años programando con SQL y desconozco 'el truco viejo' al que te refieres. Al igual que eliax estoy intrigado porque expliques cómo funciona.

    • Yo también espero ese "truco". Siempre es bueno aprender nuevas mañas : )

  • ¿Por cierto, cuando va a salir de la beta eliax 2.0,?

    Espero no cambies el estilo liquido de tu página web, pero si la hagas un poquito más 2.0, tipo html5 y para móviles :P... pero es solo una recomendación...

  • ¿Sencillo, no? :)
    R - jeje ..no.

    pero seguro en un tiempo lo voy a entender completamente, se ve interesante el truco, asi que gracias por adelantado por que se que me servira mas adelante XD

  • Genial Eliax! Tengo una pagina/blog personal y esto me va a venir genial! Gracias de nuevo

  • José Elías, ha ideado usted una versión muy simple de los "nested set" documentados en muchas web (una simple búsqueda le iluminará el camino).

    Los nested sets le liberaran de su restricción de Wx10 subcomentarios por nodo (donde W son los dígitos con los que quiera agrupar el "ORDEN_DE_DESPLIEGUE").

    Un saludo!

    • Hola Marc,

      La verdad es que conozco de Nested Sets desde que asistí a una clase de estructura de datos en la universidad hace ya muchos años :)

      Sin embargo, esa solución es muy complicada en relación con mi propuesta, así como requiere de operaciones SQL relativamente confusas y potencialmente caras en recursos.

      Ver por ejemplo este artículo de Nested Sets con MySQL: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

      Recuerda además que en el 99.999% de los casos la única operación que ejecuto en el blog para leer *todos* los comentarios de un artículo es este sencillo SQL:

      SELECT *
      FROM COMENTARIOS
      WHERE ARTICULO = 123
      ORDER BY ORDEN_DE_DESPLIEGUE

      Que no solo es más eficiente (pues recuerda que ORDEN_DE_DESPLIEGUE ya ha sido pre-indexado), sino que muchísimo más sencillo.

  • Muy bueno. Se parece bastante a la estructura que se suele utilizar en los planes de cuentas contables.

    • Ciertamente Fernando, este es un buen ejemplo de como una solución a un problema aparentemente difícil a veces es más sencillo cuando visto desde el punto de vista de otro dominio :)

      Y a propósito, este es un buen momento para hacer notar algo curioso... Esto sucede constantemente en matemáticas y física avanzada: Alguien resuelve un problema difícil con un conjunto de ecuaciones bastante complicadas, y posteriormente alguien se da cuenta que esas ecuaciones son equivalentes a otro juego de ecuaciones en un dominio totalmente distinto, como lo ocurrido en Termodinámica, y en épocas más recientes, en Teoría de Cuerdas. :)

      • Jejeje, eso es bien ceirto, y me recuerda un muchacho de la universidad que practicamente le dió catedra a un profesor con doctorado en fisica, con un tema de fisica electricidad; el muchacho en cuestión abordo el problema de una manera sencilla y mucho mas eficiente que la del docente, jajaja.

  • Muy bueno Elías!

    Me alegra ver que alguien se anima a publicar su implementación (solución) a un problema X.

    Hace 10 años implementé un algoritmo similar aprovechando la misma lógica para resolver un problema similar "con un solo golpe" a la base de datos.

    Cuando se me ocurrió hacerlo no había encontrado referencias similares en internet, sin embargo me costaba creer que nadie se le hubiera ocurrido antes, por lo que asumí en su momento que no inventé nada nuevo, simplemente aproveché algo que el SQL brinda para implementar una solución al problema.

    Lo usé para un motor que hace análisis jerárquico permitiendo búsquedas en la jerarquía hacia los dos lados (desde arriba y desde abajo, al almacenar el "hash" redundante de forma invertida).

    Hoy varios DBM's traen soporte de jerarquías, sin embargo este método "legacy" es bastante bueno y es mucho más simple de manejar que con la forma en que fue implementó actualmente (increíblemente internamente usan una solución similar).

    Lo malo de usar "Like" es que nos es muy bueno con el CPU, incorporando un índice por el "hash" ayuda a que de forma ordenada el Like haga el posicionamiento y corte. Brindándole suficiente información de filtrado a la sentencia SQL se obtienen muy buenos resultados.

    La solución es muy buena para minimizar la cantidad de golpes al DBMS y el resultado de mejora en performance es asombroso.

    Debería de ser "uno de los patrones" que debería de estar en la tapa del libro de los desarrolladores que manejen base de datos y tengan que manejar información jerárquica.

    Saludos
    David

    • David,

      Si notas, mi ejemplo de LIKE es solo para un caso muy específico y solo lo utilicé como ejemplo, pero en mi caso (comentarios para un motor de blog) esa operación prácticamente nunca ocurre, salvo por ejemplo que yo desee borrar toda una rama de comentarios.

      En el usuario diario, lo único que hago en el 99.999% de los casos es esto:

      SELECT *
      FROM COMENTARIOS
      WHERE ARTICULO = 123
      ORDER BY ORDEN_DE_DESPLIEGUE

      Que como puedes imaginar es una operación sumamente rápida.

      Sin embargo, tu comentario es importante porque como dije al inicio del artículo, depende de las variables que manejes. En el caso de un blog, incluso técnicas como Nested Sets son más lentas o complicadas.

  • En realidad esto lo usamos para las cuentas contables, es algo similar a lo de los comentarios, lo que haría es usar el mismo campo de padre y anexarle el que creaste nuevo y si hacemos un order by tendría el mismo efecto.
    Si el padre es 1 y soy el comentario 3 mi campo padre tendría 001003.

  • ¡Genial! Tengo años trabajando con bases de datos desde los viejos dbf hasta el sql, y este es el tipo de soluciones verdaderamente prácticas para los cada vez más comunes almacenamientos jerárquicos. Fíjate que sirve también para sistemas administrativos contables (las cuentas contables son jerárquicas) y al igual que este caso, son más comunes las lecturas que las escrituras.

  • Enhorabuena, y muchas gracias por compartirlo.
    Las más de las veces las ideas más simples - es simple el procedimiento - son las más efectivas.

    ¿Tienes pensado comercializar el motor privativa o abiertamente?

  • ¡Genial! Tengo años trabajando con bases de datos desde los viejos dbf hasta el sql, y este es el tipo de soluciones verdaderamente prácticas para los cada vez más comunes almacenamientos jerárquicos. Fíjate que sirve también para sistemas administrativos contables (las cuentas contables son jerárquicas) y al igual que este caso, son más comunes las lecturas que las escrituras.

  • Excelente Eliax, buén aporte la tuya.
    Excelente sigue así.
    "Cuando piensas que ya no hay nada que inventar, estás en lo falso".
    Saludos desde Campeche, México.

  • Bien Eliax... En el sistema en la empresa que trabajo tenían un sistema de menú fijos y no sabes el dolor de cabeza que era ingresar nuevos menús ya que, además de agregarlo al árbol debía agregar sus permisos asociados... (Esto es una simplificación, ya que no tiene sentido explicar todo lo que había que hacer).
    Resulta que hace 2 años tomé la tarea de hacer estos menús dinámicos y que se generarán de acuerdo a los privilegios del usuario. El punto es que la estructura de tus comentarios es similar a la de mis menús... Así que sin quererlo llegué a la misma solución tuya, agregué un nuevo campo también con 3 dígitos por nivel y de hecho cuando ví tu solución pensé que me la habías robado (jeje, es broma). Bueno, yo inventé esto hace 2 años, pero por lo que dices tú ya lo hiciste hace más de 10 así que el copión sería yo...
    Encuentro excelente que lo compartas, (ojala lo hubieras hecho 2 años atrás, jeje) por que siempre le puede servir a alguien...
    Saludos desde Temuco, Chile.

  • Simple, sencillo y lo mejor de todo... funciona

  • Elias no seria mas fácil para el servidor solo utilizar los números de lugar de en secciones definidas, en secciones indefinidas, separadas pro un carácter, de tal modo que para el ejemplo anteriormente descrito quedaría:


    A1
    B1
    C1
    B2
    C2
    D1
    D2
    C3
    C4
    B3
    A2
    B4
    C5
    D3
    C6
    C7
    Se almacenaría así:
    A1 = 1
    B1 = 1-1
    C1 = 1-1-1
    B2 = 1-2
    C2 = 1-2-1
    D1 = 1-2-1-1
    D2 = 1-2-1-2
    C3 = 1-2-2
    C4 = 1-2-3
    B3 = 1-3
    A2 = 2
    B4 = 2-1
    C5 = 2-1-1
    D3 = 2-1-1-1
    C6 = 2-1-2
    C7 = 2-1-3

    Sabiendo que va a mermar un poquito la optimización pues tendrá que buscar, en este caso el guion para saber en que momento pasar al siguiente nivel o jerarquía...

    en el cual bajo una suposición en la que tengamos un comentario

    Cx= 1-12-50 la base de datos buscara donde esta el guion y determinaría que los números que tiene que leer son 1, 12 y 50. me explico?

    esto eliminaría el limite de comentarios.

    • Cuando ideé esto originalmente pensé en lo mismo, pero tiene un problema, y es que esto no funciona desde que cambias el número de dígitos, ya que por ejemplo podrías tener esto:

      1-1-1
      10-1-1

      En donde el primer cero (0) de la segunda linea ocupa el mismo lugar lexicográficamente que el primer guión en la primera linea, lo que significa que no puedes ordenar lexicográficamente, y por tanto el truco no funciona.

      Buen intento sin embargo, y es bueno que lo hayas mencionado ya que sin duda otras personas pensarán en la misma optimización.

      • Asi es, mientras leia tu post, me iba imaginando esa forma de realizar lo mismo, pero no estaba considerando esta explicación que acabas de dar. ^^

  • A riesgo de recibir un "cocotazo" electrónico, haré el comentario de como he resuelto en el pasado este tipo de problemas. Aclaro que ha sido basado en mi trabajo diario, específicamente con un lenguaje (que limita el radio de acción de la solución)

    Llevo algún tiempo programando en Java, para este tipo de problemas que suelen ser un dolor de cabeza, existe una solución que el API proporciona.

    TreeSet es una estructura en forma de árbol binario balanceado, que ordena todo aquello que se le agrega, según el patrón que se establezca para el caso, solo se requiere implementar un objeto de tipo TreeSet, un objeto Comparable, y el Objeto o tipo de almacenamiento (en este caso comentarios).

    A groso modo la implementación sería así:

    Crear un objeto comparable
    Crear un TreeSet basado en en comparable
    Obtener datos
    Recorrer datos, creando objeto Comentario
    Agregar Comentario al objeto TreeSet

    Al terminar este proceso, los Comentarios ya estarían ordenados siguiendo el patron que se establece en Comparable, solo resta recorrer esa estructura linealmente para desplegarla.

    No espero ni prentendo establecer esto como una solución al problema, estoy de acuerdo con Jose en que existen muchas soluciones, esta se presta para ambientes donde modificar la estructura de datos no es una opción, pero se requiere mas velocidad, tomando en cuenta que es exclusiva para ambientes bajo el lenguaje.

    • Antonio,

      Recuerdo esto de mis días de Java :)

      En realidad la solución que sugieres es bastante buena cuando todo lo que haces es manejar objetos en memoria.

      El problema con esa solución es cuando tienes que serializarla y deserializarla de la base de datos. En particular al deserializarla, el árbol debe reconstruirse internamente en memoria, lo que de todas manera te devuelve al problema de rendimiento.

      Este caso es precisamente al que me refería cuando escribí:

      "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."

      Y a propósito, es bueno tu comentario porque una nota que debo hacer es sobre la importancia de saber cómo funcionan estas estructuras de datos internamente, pues aunque como se aprecia con esta librería de Java que le hace el trabajo bastante fácil al programador, el precio a pagar es que uno se desconecta de la implementación a bajo nivel y desconoce a veces que aunque la estructura es óptima en un dominio (manejos de árboles binarios en memoria), que estos no son óptimos en otros (con almacenamiento y extracción de base de datos).

      • Pues es exactamente a lo que me refería cuando comente que no pretendo sea la solución al problema (ni la única, mucho menos la mejor), solo es una alternativa para esos casos donde modificar la estructura de datos, como lo hiciste para tu blog, no es una opción.

        El costo en rendimiento es mayor que el de tu solución ciertamente, pero lo he implementado en servidores con varias aplicaciones simultáneas, que usaban otros algoritmos para crear el árbol, y resultó mas eficiente que los anteriores.

        Me pareció oportuno dado que se toca el tema de posibles soluciones al mismo problema. Conocer el lenguaje, y las operaciones de bajo nivel es importante, es parte de lo que se debe tomar en cuenta al implementar una solución

  • Realmente 1 solución bastante simple para despliegue de información, como veo en los comentarios, no dudo que muchas personas tengan su forma de "resolver" este tipo de casos, pero la solución que propones me parece super eficiente.
    Saludos ^^

  • Una columna de tipo XML puede haber solucionado el problema., no se qué tal iría en performance, pero debería funcionar, al menos en teoría ya que al menos en MsSql viene bastante optimizado.

    Un saludo, y si tengo un tiempito, intentaré ver si es factible o no la idea de un campo de TIPO XML, no xml y luego parsearlo fuera, ya que hasta se podría crear un índice Xml.

    Saludos!

    • Juan,

      Como expliqué en el artículo, eso se puede, el problema es que mueves la carga de computación de la base de datos al CPU, en donde aun tienes que parsear el árbol XML. ¡Y créeme que pensé mucho en XML cuando ideé esto! :)

  • Es decir, que lo que hacemos es asignarle una numeración al comentario que lo identifica con la manera en que debe ser desplegado visualmente.

    Si existe un Comentario: **0-Comentario A**

    Y almacenamos uno **1-Comentario B*- Este se desplegará como *hijo* del Comentario A, debido a la numeración que le hemos asignado.

  • Hola elias, este es mi primer comentario, sabes, hace unos meses participe en un proyecto donde se realizaba este tipo de ordenamiento, solo que no teniamos la restriccion de un solo padre por cada nodo, en el proyecto podrian existir cientos de padres para un nodo, sabes si este metodo funcionaria con el mismo desempeño si se utiliza en un proyecto con esta caracteristica?

    • En tu caso Eduardo, eso dependerá estrictamente de como se representarán los datos visualmente (que es el problema que abarco con este truco).

      Recuerda que al tener múltiples padres y múltiples hijos, tienes que decidir cómo planeas visualizar las jerarquías. Después que decidas eso es que procedes al próximo paso de cómo mejor representar loa datos.

      • La representación de los nodos es del mismo estilo en que se muestran los comentarios del blog (jerárquica, tipo árbol), la única diferencia es que si el nodo ya fue mostrado anteriormente entonces solo se debe mostrar el mismo nodo sin desplegar a sus "hijos", no se si se pueda hacer usando solo SQL, lo intente un par de veces pero llegaba a un loop infinito.

  • por mi y por otros como yo quedate como estas yo ni me he dado cuenta qu se cae por ratos y antes si te ivas por mucho tiempo lo estoy disfrutando mas

  • Este articulo habla de bases relacionales pero me sirvió para entender un poco mejor las bases BigTable.
    Si guardas los comentarios en una base BigTable con la clave = POST_ID+ORDEN_DE_DESPLIEGUE el motor los mantiene ordenados y el "Like" no es para nada costoso.

    • Jorge,

      En términos generales, y tal cual notaste, en bases de datos similares a BigTable (y todo lo que remotamente se parezca a un Hashtable) este tipo de trucos es la forma a implementar datos ordenados.

      Y a propósito, dale una miradita a Apache Cassandra: http://eliax.com/index.cfm?post_id=7507

  • Gracias por Publicar esto Abre el panorama a muchas cosas mas siempre lo he dicho y lo dire es mejor un codigo simple que un codigo largo y que no se entiende, me gusta la simplicidad en la programacion, como lo que se ve en tu sql me gusta tu concepto

    • Siempre lo he dicho (quizás tomando una página de Einstein), las soluciones más elegantes son por lo general las más sencillas :)

  • Mira que es un truco sencillo pero bastante interesante, llevo un tiempo trabajando con BD y no se me habia ocurrido algo como eso, tal vez porque no he tenido la necesidad de crear ese tipo de arboles gerarquicos, pero me has ahorrado varias noches de un posible futuro dolor de cabeza :)

    Yo mismo estoy planeando en un futuro no muy lejano crear mi minimotor de blog y publicarlo y esta es una idea que acuñare y no me olvidare de poner los creditos correspondientes en la seccion de "about" del blog que estoy (aunque aun no arranco por asuntos que no vienen al caso -trabajo, trabajo, etc. etc-) planeando crear.

    Ideas como esta son las que me inspiran a sacar mas tiempo para mi!, y es algo que recuerdo que varias personas (yo incluyendome) han pedido en ocasiones anteriores de añadir una parte (dentro de tus posibilidades) de tips y trucos de programacion para aquellos como yo que no tienen tanta experiencia en el campo!

    Este es un post que copiare en un archivo y lo guardare dentro de mi pequeña libreria de chucherias de computación para el momento que las necesite!

    Gracias nuevamente por tu aporte, me asegurare de que sea bien referenciado cada vez que utilice este o algun otro aporte que postees!

    Un saludo de Padowan a Master Jedi de mi parte para ti!!!!

    • Tux,

      Si tengo tiempo uno de estos días escribo otro artículo sobre una o dos optimizaciones más que son realmente útiles en este tipo de proyectos. :)

  • PostData: tienes filtros muy estrictos! ni se por que me dio el mensaje de requerimiento de aprobacion! pero ese es otro truco que algun dia pudieras explicar aqui tambien!

    • Sí, el filtro anti-SPAM a veces se pasa de la cuenta... :)

      Nota que es mi deseo el no poner ningún tipo de filtros, pero el grado de SPAM que recibo diariamente es incontrolable por otras formas, y eso a veces causa que comentarios perfectamente legítimos a veces se vayan al limbo del ciberspacio!!!

  • Genial!! ¿Porqué no se me habrá ocurrido a mi hace 6 años cuando lo necesité? Supongo que es la diferencia de un programador amateur ;-)

    Por cierto, hay una cosa que no entiendo. ¿Por qué en tu ejemplo el primer comentario tiene PADRE_ID=-1? ¿No debería ser PADRE_ID=0?

    ¡Ojalá escribas más artículos de este tipo, sencillamente genial!

    • Sí, tiene que ser 0 y no -1. Es un simple error tipográfico, pues inicié el artículo con -1 pero lo cambié por 0 para hacerlo más legible. :)

      Sin embargo, me imagino que casi nadie lo notó ya que posteriormente en donde doy ejemplos más detallados utilicé solo el 0.

      • Jaja; yo crei que el -1 era para distinguirte a ti como creador del articulo o algún comentario de respuesta; en el sentido de que cada comentario tuyo tiene un formato distinto al de nosotros (entiendase la capa de color amarilla) y que con ese -1 el código del motor distinguía si era tuyo o algún usuario.

        Pero veo que nada de eso, jaja.

        Saludos

  • Más eficiente y sobre todo más rápido aún sería utilizar tecnologia NOSQL

    • Pepe,

      Este esquema es precisamente una solucion NOSQL. Busca más arriba mi comentario sobre la base de datos Apache Cassandra. Este algoritmo se adapta perfectamente sin modificación alguna a ese tipo de entornos.

  • Eliax,

    seria interesante que prepararas un video detras de camaras (o detras del teclado) de ELIAX, y asi nos explicas como se usa tu motor de blog.

    en lo personal, la presentacion de tu blog es excelente, pero no tenemos idea de como creas los articulos, que tan facil es relacionarlo con otros, etc.

  • Si usas oracle (querys recursivos):
    http://www.adp-gmbh.ch/ora/sql/connect_by.html

    • Internamente estas implementaciones sufren del mismo problema detallado en el artículo, y aunque son bastante convenientes, son más lentas, sin nombrar que utilizan SQL no estándar.

  • Bueno parece que se encontraron todos los parientes aquí !!! jajaja
    Mis respetos a todos

  • "truco lineal de mi autoría" no es tan asi, ya que, esta forma de ordenar y/o clasificar los datos es ampliamente usada en contabilidad y si alguna vez desarrollaste un sistema contable me daras la razon, ya que solo aplicaste un metodo ya conosido de ordenacion y/o clasificacion de datos.

    • marcelinux,

      Creo que cualquier ingeniero, por mas inexperto que sea, y que haya visto un sistema de contabilidad vagamente de cerca, reconocerá sin la menor duda este patrón de ordenación. Eso nadie lo discute.

      Sin embargo, dado el caso que en todos mis años de programación, prácticamente nadie haya aplicado esto a este dominio de estructura jerárquica (y para convencerte, simplemente examina el código fuente y esquema de datos de los motores de blogs y comentarios más populares del momento), creo que eso ciertamente amerita que utilice la frase "truco lineal de mi autoría".

      Al menos, claro está, que tu ya hubieras pensado en esta simple solución antes de leer este artículo, y que lo hayas pensado unas 2 décadas atrás, en cuyo caso, te cedo la prioridad de invención... :)

      • Tu mismo me das la razon con tu respuesta...
        es por eso sigo manteniendo que "truco lineal de mi autoría" no es tan asi, y que si tubieses un poco mas de modestia hubieses dicho "aplicacion de un metodo de ordenacion y/o ordenacion lineal en un blog de mi autoría".....saludos

        • Si nos llevamos de tu forma de pensar entonces nadie inventara nada ya que todo tiene un antecedente en algún lado.

          • nico.. una cosa es inventar y otra muy diferente aplicar algo ya inventado o hacer una variacion del invento...

  • Order By Id Padre, donde ID padre=0 es comentario Raiz, aunque está interesante la propouesta, porque podría decirse que almacenas el path del Comentario, así llegas directamente al que quieres

  • estimado, patentelo y vendaselo a facebook, porque arta falta que hace en face comentar en grupos grandes donde es toda una odisea averiguar las repuestas que te dan cuando estan comentando mas de 500 personas.

    de hecho ocupan una tecnica bien burda para avisarte que te respondieron, hacen click en "me gusta" aun cuando no le gusta tu comentario.

  • Muy bueno, me gusto mucho. Lo tomare en cuenta cuando tenga una caso como ese.

  • Hola a todos, solo una corrección, si se puede realizar la consulta, de un jalón en Oracle y SQLServer se hace de la siguiente forma:

    /*Oracle*/
    select ra.*, level
    from tablaEjemplo ra
    start with idPadre = 21
    connect by prior ra.idHijo = ra.idPadre;

    /*SQL Server*/
    with prueba (campo1,campo2,replevel) as
    ( select campo1,campo2, 0 replevel
    from tablaEjemplo r1
    where idPadre = 21
    union all
    select e.campo1, e.campo2,replevel+1 as replevel
    from prueba r, tablaEjemplo e
    where r.idHijo = e.idPadre
    )
    select * from prueba
    ;


    Saludos a todos y espero que les sirva.

Añadir Comentario

tu nombre
tu email
(opcional)
web personal
(opcional)
en respuesta a...
comentario de caracteres máximo
2 + 7 = requerido (control anti-SPAM)
 

"Un nuevo paradima. Hoy, nuevamente, el mundo cambió."

por "LuisGo" en dic 2, 2010


en camino a la singularidad...

©2005-2014 josé c. elías
todos los derechos reservados
como compartir los artículos de eliax