Árboles falsos: usar sangría para una UI más simple

 (ratfactor.com)
4 puntos por GN⁺ 2024-01-01 | 1 comentarios | Compartir por WhatsApp
  • Aunque parezca que necesitas una UI jerárquica, lo primero que conviene comprobar es si los datos realmente deben tener una relación padre-hijo, o si solo necesitan verse así
  • Si no necesitas un árbol real, puedes representar la estructura en pantalla usando solo el orden absoluto de toda la lista y un valor indent, en vez de un ID de padre
  • El editor de juegos Hiss ordena nombres como banana.eat y luego muestra con sangría lo que va después del punto (.), creando una UI que parece un namespace
  • Este enfoque se parece más a la edición tipo procesador de texto, donde el usuario mueve elementos arriba y abajo y aplica sangría o quita sangría, reduciendo la carga de una estructura de datos de árbol
  • Si de verdad necesitas consultar o mantener relaciones entre elementos, hace falta un modelo de árbol real en lugar de hacks con sangría o símbolos en strings

Una lista que parece árbol, no un árbol

  • Cuando en una aplicación se intenta mostrar una lista dinámica como Foo, Bar en una vista de árbol, normalmente se piensa en una estructura que conecta cada elemento con su elemento padre
  • En una base de datos relacional, por ejemplo, se puede guardar el ID del padre en una columna parent
    • El parent de Foo es null
    • El parent de Foo 1 es Foo
    • El parent de Foo 1.a es Foo 1
  • Para traer estos datos de árbol con SQL, puede hacer falta un enfoque como una CTE recursiva
  • Pero en muchas listas puede ser más importante una presentación ordenada y fácil de leer que una relación real

Guardar el valor de sangría como dato

  • Si no necesitas una relación padre-hijo real, puedes guardar la lista solo con estos campos
    • id
    • sort
    • indent
    • name
  • sort representa el orden absoluto de toda la lista, no el orden interno dentro de los subelementos
  • indent representa directamente la cantidad de espacio que se pondrá antes del elemento, así que el renderizado en pantalla se simplifica
  • La UI de edición también puede volverse más simple que manipular un árbol
    • El usuario puede mover elementos hacia arriba y hacia abajo
    • Puede aplicar sangría o quitar sangría a los elementos
    • Si hace falta, se pueden agregar reglas simples para forzar una sangría correcta
  • Como resultado, la experiencia se parece más a editar una lista en un procesador de texto que a manipular directamente una estructura de datos de manual de ciencias de la computación

Namespaces falsos basados en puntos (.) en Hiss

  • El editor de juegos de aventura de texto Hiss muestra nombres como banana, banana.eat, banana.peel como si fueran jerárquicos en la UI
  • No es que se haya implementado una función real de namespaces en HissScript
  • La implementación es simple
    • Ordena los nombres de objetos alfabéticamente
    • Si un nombre contiene un punto (.), recorta la parte inicial
    • Imprime el resto con sangría
  • La lógica central del código de ejemplo sigue el mismo flujo
    • Ordena things.keys
    • Si cada nombre contiene un punto, aplica sangría y elimina la parte anterior al punto antes de imprimirlo
    • Si no contiene punto, imprime el nombre tal cual
  • Luego se agregan unas líneas más para comprobar si existe un elemento “padre” con el prefijo dado
  • También se podría agregar anidamiento de profundidad arbitraria, pero queda pendiente hasta que surja una necesidad real
  • Esta UI que parece un namespace es importante para quien organiza el juego, pero no tiene un significado especial para el editor ni para el jugador
    • Un nombre con punto sigue siendo simplemente un nombre
    • La parte que parece un namespace solo ayuda a mantener los nombres únicos

Casos parecidos a árboles tratados como listas planas

  • Dave Long propuso, como “árboles reales de baja tecnología”, una forma de guardar rutas e información en una lista plana
  • Es una intuición similar al ejemplo de banana.eat
  • Podemos imaginar una lista de rutas como la salida de find, con esta forma
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Si necesitas un recorrido en profundidad, basta con ordenar las rutas lexicográficamente
  • Si necesitas un recorrido en anchura, puedes invertir las rutas usando el separador de ruta como criterio, agregar elementos vacíos para igualar la profundidad y luego ordenar
  • Este ejemplo es solo para mostrar el concepto; en la práctica, lo natural sería dividir las líneas por el separador y procesarlas como arreglos
  • En general, las listas planas son fáciles de manejar, y cuando se pueda se prefiere el enfoque de poner los elementos en plain old lists

La analogía del scrapbook en el piso

  • En un proyecto personal de scrapbook, puedes colocar fotos, notas, postales, boletos, etc. en el piso y formar grupos
  • Para una persona, las relaciones entre grupos pueden verse claras, pero el piso en sí no tiene ningún mecanismo físico que las imponga
  • El punto central de esta analogía es que una relación representada y una relación estructural real pueden ser cosas distintas
  • Lo mismo ocurre con las listas de UI: una disposición que para una persona parece jerárquica no necesariamente implica una jerarquía real en el modelo de datos interno

Cuándo hace falta un árbol real

  • Los enfoques basados en sangría o símbolos dentro de strings deben ajustarse bastante según el contexto, y en contextos generales de programación probablemente se consideren hacks
  • Si realmente necesitas conocer las relaciones entre elementos, deberías usar una estructura de árbol real acorde al modelo de datos, como IDs de padre o una tabla de joins padre-hijo
  • Si necesitas un nivel de organización similar al de un gabinete físico con carpetas, como al clasificar un proyecto de investigación grande, el “enfoque del piso” no es adecuado
  • Si en un proyecto más adelante vas a necesitar conocer de verdad las relaciones entre elementos, imitar una estructura mediante sangría o contando símbolos dentro de strings puede convertirse en un camino doloroso durante toda la vida del proyecto y su mantenimiento

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-01-01
Opiniones de Hacker News

  • El primer enfoque, es decir, el que parece “obviamente la única forma de hacerlo”, se llama lista de adyacencia (adjacency list).
    No recuerdo haber visto antes el segundo “método mucho más simple”, y aunque tiene desventajas evidentes, en algunos casos parece suficiente.
    El tercer enfoque de “usar espacios de nombres” se llama ruta materializada (materialized path), y otra forma de representar árboles son los conjuntos anidados (nested sets): https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    Todo esto era bien conocido en la época en que la gente se tomaba en serio las bases de datos relacionales; por ejemplo, también hay artículos como http://www.dbazine.com/oracle/or-articles/tropashko4/
    Ahora parece conocimiento olvidado.

    • Uno de los momentos que más odiaba en un trabajo anterior era cuando me esforzaba muchísimo por explicar un problema y alguien lo reconocía como un concepto existente que ya tenía nombre y había sido estudiado.
      Siento que, cuando uno está descubriendo por su cuenta las distintas facetas de un problema, es realmente difícil encontrar el nombre ya establecido de ese concepto.
    • Es cierto. Los jóvenes graduados que contratamos hoy en día intentan meter todo a la fuerza en documentos NoSQL y casi no quieren pensar en modelado de datos.
      Al final terminan manejando en el código toda la lógica para mostrar árboles, lo cual es una lástima porque con una base de datos relacional moderna y algunos CTE se pueden resolver muchos casos de uso de forma elegante y gratis.
    • No diría que sea conocimiento olvidado. También existe el libro “Joe Celko's Trees and Hierarchies in SQL”.
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Si te interesa este tema, recomiendo empezar por buscar los libros de https://en.m.wikipedia.org/wiki/Joe_Celko.

  • Postgres tiene un tipo de dato ltree y operadores de búsqueda que funcionan de forma nativa así: https://www.postgresql.org/docs/current/ltree.html
    Por ejemplo, puedes insertar datos con CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy');
    y con SELECT path FROM test WHERE path <@ 'Top.Science'; puedes encontrar Top.Science y Top.Science.Astronomy.

    • Nota para programadores: una peculiaridad de ltree es que, si lo dibujas como árbol, las rutas intermedias que serían nodos padre no tienen que existir realmente.
      En el ejemplo anterior, aunque borres el registro Top.Science, el registro Top.Science.Astronomy no se corta ni desaparece.
      Las etiquetas de un valor ltree insinúan un árbol lógico mediante una ruta materializada, pero no obligan a que existan registros para todos los nodos padre implícitos.
      Según la aplicación, esto puede ser exactamente lo que quieres, o justo lo contrario. Si es esto último, tendrás que poner algún mecanismo aparte para mantener la integridad.
    • Me pregunto si para almacenar rutas de archivos se puede usar / como separador.
    • Me pregunto si alguien tiene experiencia con el rendimiento. Parece implicar bastante procesamiento de expresiones regulares.
    • SQL Server también tiene una funcionalidad muy parecida[1], y por mi experiencia funciona bastante bien.
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Me pregunto si se podría hacer lo mismo con una columna JSON. Así también se podrían usar tipos de datos que no sean cadenas en los nodos.
      Aunque me preocupa que los índices JSON quizá no funcionen tan bien como los índices ltree.

  • El problema aquí es que el valor dentro de la estructura normalmente no está en el árbol para mostrar, sino en la jerarquía de los datos.
    Es muy probable que termines haciendo cosas como recorrer los datos, mostrar relaciones o reordenarlos.
    Meter información visual en la estructura de datos de la base de datos se ve peligroso y cortoplacista.

    • El autor ya dijo explícitamente que “la gente siempre piensa que hay que codificar formalmente la relación padre-hijo, pero en la práctica a veces no es así y solo se necesita una visualización anidada”, así que como respuesta a eso suena un poco raro.
      ¿La respuesta es “no, eso no puede ser”?
      Hay una razón por la que YAGNI es una heurística de diseño famosa. “Asume siempre que lo vas a necesitar” no es correcto.
    • Irónicamente, todavía se está usando un ID de padre dentro de los datos.
      Solo lo pusieron al principio de la cadena de datos en vez de guardarlo en una columna dedicada con un tipo de dato optimizado.
      Puede que no sea un número ni una columna de ID, pero sigue siendo un identificador que apunta a otro valor esperado, así que no deja de ser un ID de padre solo porque haya cambiado el formato.
    • En el esquema de codificación por orden/indentación del texto original, también debería ser fácil reconstruir las relaciones padre-hijo.
      Claro, hay que garantizar que no se guarde una indentación inválida, como un hijo sin padre.
      Por eso creo que la forma más sencilla es guardar primero orden/profundidad y, cuando implementes las funciones necesarias, migrar a un modelo padre/hijo.
      Eso sí: conviene definir la “indentación” de forma más abstracta como la profundidad en el árbol, no como la cantidad de espacios que se renderizan. Así es más fácil encontrar datos inválidos, también es más fácil migrar después, y además permite flexibilidad de renderizado por usuario: / anidados, tabs, 8 espacios, 4 espacios, 1 espacio, etc.
    • Si tienes una estructura de datos como struct item_t { char key[255]; char display_value[255]; } y las claves tienen un separador de ruta consistente como a/b/c, encontrar padres e hijos es muy fácil.
      En el peor caso haces una búsqueda lineal en el arreglo, y si está ordenado solo tienes que mirar los elementos anteriores hasta llegar al padre.
    • Muy de acuerdo. La desnormalización a veces puede ser una buena opción, pero no creo que este caso sea una justificación razonable.

  • Una vez fundé una empresa con muchos datos en forma de árbol. Convertir una estructura de árbol en una lista indentada se puede hacer en tiempo O(n).
    Era una de nuestras preguntas de entrevista en ese momento, y hay formas de almacenar esto en varias bases de datos SQL para poder traer y renderizar rápido partes de un árbol incluso sin consultas recursivas.
    Una vez que entiendes esos conceptos, guardar los datos correctamente como árbol tiene muchísimas más ventajas que este tipo de indentación.

    • Si no necesitas esas ventajas, entonces no importa mucho.

  • “Una forma de traer datos con estructura de árbol desde una base de datos relacional con una consulta SQL es usar CTE recursivas (Common Table Expressions), que son tan divertidas como suenan”.
    Las CTE, incluso incluyendo CTE recursivas, no dan miedo, y te aseguro que cuando te acostumbras de verdad son divertidas.

    • Las CTE no son particularmente divertidas. Copiar y pegar toda la torre de CTE en otra ventana SQL para depurar la parte que me interesa no es mi idea de entretenimiento.
    • Al armar datos de árbol a partir de una representación normalizada, las CTE recursivas eran tremendamente lentas.
      Para armar la ruta de un nodo con profundidad jerárquica d, obtener el resultado de la consulta tardaba al menos d veces más.
      La ventaja era que editar el árbol era barato, pero eso ocurría con mucha menos frecuencia que las lecturas.
    • Las CTE están bien. En vez de hornear esta información dentro de la tabla, el autor podría haber creado una vista con un nombre formateado mediante una CTE.

  • En la idea de que “la gente en realidad muchas veces no quiere ni necesita un árbol, sino algo que parezca un árbol”, se ve la diferencia entre HN y Reddit.
    En HN, un comentario hijo es el nextSibling del comentario padre y se muestra como árbol sumándole 1 al valor de indentación del padre.
    En Reddit, al menos en old.reddit.com, los comentarios hijos están realmente anidados dentro del comentario padre. No sé cómo será en el sitio nuevo.

    • Te refieres a la estructura HTML, no a la visualización real, ¿verdad? Lo que se ve en pantalla es casi idéntico.
    • Me cuesta imaginar que en el backend realmente se guarde así.
      Todas las operaciones sobre los datos se volverían un enredo complejo de inferir la estructura de árbol y luego volver a traducirla al formato de árbol implícito.
    • Si es así, me pregunto cómo funciona el colapsado.

  • La idea central del artículo es simple: usar la estructura adecuada para el problema.
    Pero creo que la narrativa está mal planteada. No necesariamente necesitas CTE para traer un árbol desde la base de datos; puedes traer una lista plana y construir el árbol localmente. De todos modos, es muy probable que hagas eso para manipularlo después.
    Con la misma lógica, también podrías decirle a alguien que usa una base de datos relacional para guardar una lista que la guarde en un archivo de texto. ¿Para qué pagar el costo de latencia de red?
    Por otro lado, la estructura propuesta no se comporta bien si en un árbol suficientemente grande quieres mover ramas y cambiar profundidades, porque tiene costo lineal.
    Debió haber dejado clara la intención desde el principio. No explicar tres ejemplos y luego invalidarlos en la conclusión con “si necesitas un árbol, usa un árbol”. Aunque si hubiera puesto eso al inicio, habría sido mucho menos clickbait.

  • Hace unos años tuve una revelación parecida sobre OpenGL. No necesitaba dibujar un mundo de objetos 3D jerárquicos, sino una lista ordenada de triángulos.
    Esa idea me prendió un interruptor en la cabeza e hizo que varias optimizaciones fueran muy fáciles.

    • Sí. En los juegos 3D posteriores al 2000, la simplicidad se vuelve una gran fuerza.
      Incluso en juegos con jerarquías complejas de entidades, al meter cosas en la cola de render muchas veces hay que aplanarlas por razones como el ordenamiento por transparencia.
      Una “lista plana de cosas” también es la base de ECS/DOD.

  • Hay libros enteros sobre cómo manejar este tipo de trabajo en bases de datos.
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • Y luego dicen que todos los libros son para principiantes; qué bien.

  • Otra forma de hacer árboles falsos es guardar un blob JSON.
    Si los datos solo tienen relaciones internas, puede ser más fácil que intentar mantener números de orden únicos y ordenados.

    • Un árbol representado como JSON anidado incluso podría considerarse un árbol más “real” que el árbol virtual que obtienes guardando referencias al padre en la base de datos.