Faux arbres : utiliser l’indentation pour une UI plus simple

Faux arbres : une UI plus simple grâce à l’indentation

• Lorsqu’on veut une liste en arborescence dans une UI, implémenter une relation parent-enfant demande beaucoup de travail et des structures de données complexes.
• Dans une base de données relationnelle, on peut utiliser des CTE récursives (Common Table Expressions) pour obtenir des données structurées en arbre.

Les données doivent-elles vraiment être arborescentes ?

• Il faut se demander si les éléments doivent réellement avoir une relation parent-enfant, ou s’ils doivent simplement en avoir l’apparence.
• Si une relation réelle n’est pas nécessaire, on peut stocker un arbre simplement avec les champs id, sort, indent et name.
• Cette méthode représente directement ce qui est affiché à l’écran, ce qui rend bien plus simple la création d’une interface pour afficher et modifier la liste.

Un autre exemple avec le « namespacing »

• Dans HissScript, lorsqu’un nom d’élément contient un point (.), la première partie est retirée et l’élément est indenté, ce qui permet d’implémenter une fonctionnalité de namespacing.
• Pour l’éditeur de jeu et le lecteur, le namespacing est important, mais en réalité il ne s’agit que d’un simple nom.
• Souvent, les gens n’ont pas besoin d’une véritable structure en arbre, mais seulement de son apparence.

Bonus : arbre-liste

• En imitant un véritable arbre, on stocke les chemins et les informations dans une liste plate, puis on trie les chemins pour un parcours en profondeur ou en largeur.
• Les listes plates sont généralement plus faciles à manipuler et mieux adaptées aux ordinateurs.

Analogie physique

• Quand on organise un scrapbook personnel, le fonctionnement des groupes est clair pour une personne, mais en réalité il n’existe sur le sol aucun mécanisme physique imposant de telles relations.

Attention : il n’existe pas de solution universelle

• Il faut appliquer la technique en fonction du scénario précis, et lorsqu’une véritable structure en arbre est nécessaire, il faut utiliser un arbre.
• Si l’on a besoin de connaître les relations réelles entre les éléments, il ne faut pas recourir à des bricolages comme l’indentation ou le comptage de symboles dans une chaîne.

Avis de GN⁺ :

• Cet article propose une manière de simplifier les interfaces utilisateur dans le développement logiciel en utilisant une indentation visuelle simple à la place de structures arborescentes complexes.
• Il offre aux développeurs une stratégie efficace pour réduire la complexité des structures de données, gagner du temps de développement et faciliter la maintenance.
• Il souligne qu’une structure en arbre n’est pas toujours nécessaire et que, parfois, une simple structure visuelle familière pour l’utilisateur suffit, offrant ainsi aux développeurs une nouvelle perspective pour améliorer l’expérience utilisateur.

[GN⁺]

Commentaire Hacker News

• La première approche, la « liste d’adjacence (adjacency list) », est considérée comme « manifestement la seule façon de faire ».

• La deuxième approche est une « méthode bien plus simple », jamais vue auparavant, avec des défauts évidents, mais suffisamment claire dans certains cas.

• La troisième approche, le « namespacing », est appelée « materialized path ».

• Une autre manière de représenter un arbre est celle des « nested sets », bien connue à l’époque où l’on traitait sérieusement les bases de données relationnelles.

• Postgres fournit un type de données ltree et des opérateurs de recherche, ce qui permet de manipuler naturellement des structures arborescentes. Par exemple, on peut créer une table avec ltree, insérer des données, puis interroger la structure avec de simples recherches.

• Les valeurs à l’intérieur de la structure correspondent souvent à une hiérarchie de données plutôt qu’à l’arbre affiché. On peut vouloir parcourir les données, montrer des relations ou les réordonner. Stocker des informations visuelles dans la structure de données en base peut sembler être une vision à court terme.

• J’ai créé une entreprise qui manipulait des données en arbre. Il est possible de transformer une structure arborescente en liste indentée en temps O(n). C’était l’une des questions d’entretien, et il existe dans les bases SQL plusieurs façons de récupérer et de rendre rapidement une partie d’un arbre, sans requêtes récursives.

• Une façon de récupérer des données arborescentes dans une base relationnelle avec SQL consiste à écrire des CTE récursifs (Common Table Expressions). Les CTE sont en réalité amusants et, une fois qu’on s’y habitue, ils n’ont rien d’effrayant.

• L’expérience montre que les gens ne veulent souvent pas vraiment un arbre, mais seulement son apparence. HN et Reddit diffèrent sur ce point. Sur HN, les commentaires enfants sont les frères suivants du commentaire parent, avec un niveau d’indentation supérieur d’une unité à celui du parent pour imiter l’apparence d’un arbre. Sur Reddit, en revanche, les commentaires enfants sont réellement imbriqués dans le commentaire parent.

• L’idée centrale de l’article est d’utiliser une structure adaptée au problème. Mais le développement de l’argumentation est défaillant. Il n’est pas nécessaire d’utiliser des CTE pour récupérer un arbre depuis une base de données, et on peut récupérer une liste plate puis construire l’arbre localement. De plus, avec un arbre suffisamment grand, déplacer des branches ou modifier la profondeur peut entraîner un coût linéaire.

• Pour décrire une taxonomie ou une autre hiérarchie, j’ai appris une méthode simple et rapide consistant à utiliser le système de fichiers local. Avec les commandes mkdir et tree, on peut copier-coller le résultat dans un e-mail, Slack, pastebin, etc.

• Si l’objectif est seulement de sauvegarder/charger, une solution plus simple peut être de sérialiser les données comme on le souhaite (par exemple en JSON) et de les stocker sous forme de chaîne. L’utilisation de la notation par points ressemble à la manière dont l’extension VsCode Dendron gère les hiérarchies de noms.

• Il y a quelques années, j’ai eu une révélation similaire à propos d’OpenGL : il n’est pas nécessaire de dessiner un monde d’objets 3D hiérarchiques, il suffit de dessiner une liste triée de triangles. Cela rend de nombreuses optimisations très faciles.