Fake Trees: Einrückungen für einfachere UIs nutzen

 (ratfactor.com)
4 Punkte von GN⁺ 2024-01-01 | 1 Kommentare | Auf WhatsApp teilen
  • Auch wenn eine hierarchische UI nötig erscheint, sollte man zuerst prüfen, ob die Daten wirklich eine Eltern-Kind-Beziehung haben müssen – oder ob es nur so aussehen muss
  • Wenn kein echter Baum nötig ist, lässt sich die sichtbare Struktur statt über Parent-IDs allein über die absolute Sortierreihenfolge der Gesamtliste und einen indent-Wert darstellen
  • Der Spiele-Editor Hiss sortiert Namen wie banana.eat und zeigt den Teil nach dem Punkt (.) eingerückt an; so entsteht eine UI, die wie ein Namespace wirkt
  • Dieser Ansatz ähnelt eher dem Bearbeiten wie in einer Textverarbeitung, bei dem Nutzer Einträge nach oben und unten verschieben sowie ein- und ausrücken, und reduziert die Last einer Baumdatenstruktur
  • Wenn Beziehungen zwischen Einträgen tatsächlich abgefragt oder gepflegt werden müssen, braucht es statt Einrückungen oder Hacks mit String-Symbolen ein echtes Baummodell

Eine Liste, die wie ein Baum aussieht, aber keiner ist

  • Wenn man in einer Anwendung eine dynamische Liste wie Foo, Bar als Tree View anzeigen möchte, denkt man meist an eine Struktur, bei der jeder Eintrag mit einem Elterneintrag verknüpft ist
  • In einer relationalen Datenbank könnte man zum Beispiel in einer parent-Spalte die Parent-ID speichern
    • Der parent von Foo ist null
    • Der parent von Foo 1 ist Foo
    • Der parent von Foo 1.a ist Foo 1
  • Um solche Baumdaten per SQL abzurufen, können Verfahren wie rekursive CTEs nötig sein
  • In vielen Listen kann jedoch die für Menschen gut organisierte Darstellung wichtiger sein als die tatsächliche Beziehung

Einrückungswerte als Daten speichern

  • Wenn keine echte Eltern-Kind-Beziehung nötig ist, kann die Liste nur mit den folgenden Feldern gespeichert werden
    • id
    • sort
    • indent
    • name
  • sort steht nicht für die Reihenfolge innerhalb von Untereinträgen, sondern für die absolute Reihenfolge der gesamten Liste
  • indent gibt direkt die Menge an Leerraum vor dem Eintrag an, wodurch das Rendering der Oberfläche einfach wird
  • Auch die Bearbeitungs-UI kann einfacher werden als Tree-Manipulation
    • Nutzer können Einträge nach oben und unten verschieben
    • Sie können Einträge einrücken oder ausrücken
    • Bei Bedarf lassen sich einfache Regeln hinzufügen, die korrekte Einrückungen erzwingen
  • Dadurch ähnelt die Erfahrung eher dem Bearbeiten einer Liste in einer Textverarbeitung, statt direkt eine datenstrukturartige Lösung aus dem Informatiklehrbuch zu manipulieren

Hiss’ Fake-Namespace auf Basis von Punkten (.)

  • Der Text-Adventure-Spiele-Editor Hiss zeigt Namen wie banana, banana.eat, banana.peel in der UI wie eine Hierarchie an
  • In HissScript wurde keine echte Namespace-Funktionalität implementiert
  • Die Umsetzung ist simpel
    • Objektnamen werden alphabetisch sortiert
    • Wenn ein Name einen Punkt (.) enthält, wird der vordere Teil abgeschnitten
    • Der verbleibende Teil wird eingerückt ausgegeben
  • Die Kernlogik des Beispielcodes folgt demselben Ablauf
    • things.keys wird sortiert
    • Wenn ein Name einen Punkt enthält, wird er nach dem Einrücken ohne den Teil vor dem Punkt ausgegeben
    • Wenn kein Punkt vorhanden ist, wird der Name unverändert ausgegeben
  • Später wurden noch ein paar Zeilen hinzugefügt, die prüfen, ob ein „Parent“-Eintrag mit dem gegebenen Präfix existiert
  • Verschachtelung in beliebiger Tiefe ließe sich ebenfalls ergänzen, aber man wartet damit, bis tatsächlich Bedarf entsteht
  • Diese UI, die wie ein Namespace wirkt, ist für Menschen wichtig, die das Spiel organisieren, hat aber für den Spiele-Editor und die Spieler keine besondere Bedeutung
    • Namen mit Punkten sind einfach Namen
    • Der Teil, der wie ein Namespace wirkt, dient nur dazu, Namen eindeutig zu halten

Baumähnliche Fälle als flache Liste behandeln

  • Dave Long schlägt mit „Low-Tech Real-World Trees“ vor, Pfade und Informationen in einer flachen Liste zu speichern
  • Das beruht auf einer ähnlichen Einsicht wie das Beispiel banana.eat
  • Man kann sich eine Pfadliste wie bei der Ausgabe von find vorstellen
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Wenn eine Tiefensuche nötig ist, reicht es, die Pfade lexikografisch zu sortieren
  • Wenn eine Breitensuche nötig ist, kann man die Pfade anhand des Pfadtrennzeichens umkehren, leere Elemente zum Angleichen der Tiefe hinzufügen und anschließend sortieren
  • Dieses Beispiel soll das Konzept zeigen; in der Praxis ist es natürlicher, die Zeilen am Trennzeichen zu splitten und als Arrays zu verarbeiten
  • Flache Listen sind insgesamt angenehm zu handhaben, und wenn möglich, wird der Ansatz bevorzugt, Einträge in plain old lists zu packen

Die Scrapbook-Metapher auf dem Boden

  • Bei persönlicher Scrapbook-Arbeit kann man Fotos, Notizen, Postkarten und Tickets auf dem Boden ausbreiten und Gruppen bilden
  • Für Menschen mögen die Gruppenbeziehungen klar erkennbar sein, aber der Boden selbst hat keine physische Vorrichtung, die diese Beziehungen erzwingt
  • Kern dieser Metapher ist, dass sich dargestellte Beziehungen und tatsächliche strukturelle Beziehungen unterscheiden können
  • Dasselbe gilt für UI-Listen: Eine Anordnung, die Menschen wie eine Hierarchie erscheint, muss keine echte Hierarchie im internen Datenmodell bedeuten

Wann ein echter Baum nötig ist

  • Ansätze auf Basis von Einrückungen oder String-Symbolen müssen stark an die jeweilige Situation angepasst werden und dürften in allgemeinen Programmierkontexten als Hack gelten
  • Wenn man die Beziehungen zwischen Einträgen tatsächlich kennen muss, sollte man eine zum Datenmodell passende echte Baumstruktur verwenden, etwa Parent-IDs oder eine Eltern-Kind-Join-Tabelle
  • Wenn man Organisationskraft auf dem Niveau physischer Aktenschränke und Ordner braucht, etwa beim Klassifizieren großer Forschungsprojekte, ist die „Bodenmethode“ nicht geeignet
  • Wenn ein Projekt später tatsächlich Beziehungen zwischen Einträgen kennen muss und man die Struktur mit Einrückungen oder der Anzahl von Symbolen in Strings nachahmt, kann das über die gesamte Lebens- und Wartungsdauer des Projekts zu einem schmerzhaften Weg werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-01-01
Hacker-News-Kommentare

  • Die erste Variante, also die, die wie „offensichtlich gibt es nur diesen Weg“ aussieht, nennt man eine Adjazenzliste (adjacency list)
    Die zweite, „viel einfachere Methode“ kannte ich vorher nicht; sie hat offensichtliche Nachteile, wirkt aber in manchen Fällen ausreichend
    Die dritte, „Namespacing“, nennt man materialized path; das ist eine weitere Art, Bäume darzustellen, daneben gibt es auch Nested Sets: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    Als Leute relationale Datenbanken noch ernsthaft behandelt haben, war das alles allgemein bekannt; es gibt zum Beispiel auch Artikel wie http://www.dbazine.com/oracle/or-articles/tropashko4/
    Inzwischen wirkt es wie vergessenes Wissen

    • Einer der Momente, die ich in meinem früheren Job am meisten gehasst habe, war, wenn ich mich abgemüht habe, ein Problem zu erklären, und dann jemand erkannt hat, dass es ein bereits benanntes und erforschtes bestehendes Konzept ist
      Wenn man verschiedene Aspekte eines Problems selbst herausarbeitet, ist es wirklich schwer, den etablierten Namen dieses Konzepts zu finden
    • Stimmt. Die jungen Absolventen, die heute eingestellt werden, stopfen alles in NoSQL-Dokumente und wollen über Datenmodellierung fast gar nicht nachdenken
      Am Ende landet die gesamte Logik zur Darstellung von Bäumen im Code, obwohl viele Anwendungsfälle sich mit modernen relationalen Datenbanken und ein paar CTEs elegant und praktisch kostenlos lösen lassen, was schade ist
    • Ich würde es nicht als vergessenes Wissen bezeichnen. Es gibt auch ein Buch namens „Joe Celko's Trees and Hierarchies in SQL“
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Wenn dich das Thema interessiert, würde ich zuerst empfehlen, nach den Büchern auf https://en.m.wikipedia.org/wiki/Joe_Celko zu schauen

  • In Postgres gibt es dafür den nativen ltree-Datentyp samt Suchoperatoren: https://www.postgresql.org/docs/current/ltree.html
    Man kann zum Beispiel CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy'); verwenden
    Mit SELECT path FROM test WHERE path <@ 'Top.Science'; findet man dann Top.Science und Top.Science.Astronomy

    • Hinweis für Programmierer: Eine Besonderheit von ltree ist, dass Zwischenpfade, die in einer Baumdarstellung Elternknoten wären, nicht tatsächlich existieren müssen
      Im obigen Beispiel wird der Datensatz Top.Science.Astronomy nicht abgeschnitten, selbst wenn man den Datensatz Top.Science löscht
      Die Labels eines ltree-Werts implizieren über den materialized path zwar einen logischen Baum, erzwingen aber nicht die Existenz von Datensätzen für alle implizierten Elternknoten
      Je nach Anwendung kann das genau das gewünschte Verhalten sein oder das genaue Gegenteil. Im letzteren Fall braucht man einen separaten Mechanismus, um die Integrität sicherzustellen
    • Ich frage mich, ob man zum Speichern von Dateipfaden / als Trennzeichen verwenden kann
    • Mich würde interessieren, ob jemand Performance-Erfahrungen damit hat. Es sieht nach viel Regex-Verarbeitung aus
    • In SQL Server gibt es etwas sehr Ähnliches[1], und meiner Erfahrung nach funktioniert es ziemlich gut
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Ich frage mich, ob man dasselbe auch mit einer JSON-Spalte machen kann. Dann könnte man für Knoten auch Datentypen statt nur Strings verwenden
      Allerdings habe ich die Sorge, dass JSON-Indizes nicht so gut funktionieren wie ltree-Indizes

  • Das Problem hier ist, dass der Wert der Struktur meist nicht in einem Anzeige-Baum liegt, sondern in der Hierarchie der Daten
    Wahrscheinlich wird man Dinge wie das Traversieren der Daten, das Anzeigen von Beziehungen oder das Umordnen tun wollen
    Visuelle Informationen in der Datenstruktur einer Datenbank zu speichern, wirkt riskant und kurzsichtig

    • Der Autor hat bereits ausdrücklich gesagt: „Menschen denken immer, dass Eltern-Kind-Beziehungen formal kodiert werden müssen, aber tatsächlich ist das nicht immer so, und manchmal braucht man nur eine verschachtelte Darstellung“; die Reaktion darauf wirkt daher etwas seltsam
      Ist die Antwort dann „Nein, das kann nicht sein“?
      Es gibt einen Grund, warum YAGNI eine bekannte Design-Heuristik ist. „Nimm immer an, dass es nötig sein wird“ ist nicht richtig
    • Ironischerweise wird in den Daten immer noch eine Parent-ID verwendet
      Sie wurde nur dem Daten-String vorangestellt, statt in einer eigenen Spalte mit optimiertem Datentyp gespeichert zu werden
      Sie muss keine Zahl sein und keine ID-Spalte, aber sie bleibt ein Bezeichner, der auf einen anderen erwarteten Wert verweist; nur weil sich das Format geändert hat, ist es nicht plötzlich keine Parent-ID mehr
    • Auch bei der Kodierung über Reihenfolge/Einrückung im Originaltext sollte sich die Eltern-Kind-Beziehung leicht rekonstruieren lassen
      Natürlich muss sichergestellt werden, dass keine ungültigen Einrückungen wie Kinder ohne Eltern gespeichert werden
      Deshalb scheint der einfachste Weg zu sein, zuerst als Reihenfolge/Tiefe zu speichern und erst dann auf ein Eltern/Kind-Modell zu migrieren, wenn die nötigen Funktionen implementiert werden
      Dabei sollte „Einrückung“ besser abstrakter als Tiefe im Baum definiert werden und nicht als Anzahl gerenderter Leerzeichen. So lassen sich fehlerhafte Daten leichter finden, spätere Migrationen werden einfacher, und man gewinnt Flexibilität bei der Darstellung für Nutzer mit verschachtelten /, Tabs, 8 Leerzeichen, 4 Leerzeichen, 1 Leerzeichen usw.
    • Wenn es eine Datenstruktur wie struct item_t { char key[255]; char display_value[255]; } gibt und der Schlüssel einen konsistenten Pfadtrenner wie a/b/c hat, dann ist es sehr einfach, Eltern und Kinder zu finden
      Im schlimmsten Fall durchsucht man das Array linear, und wenn es sortiert ist, muss man nur die vorherigen Einträge ansehen, bis man beim Elternteil angekommen ist
    • Stimme stark zu. Denormalisierung kann manchmal eine gute Wahl sein, aber ich sehe in diesem Fall keine vernünftige Rechtfertigung dafür

  • Ich habe einmal ein Unternehmen gegründet, das viele baumförmige Daten hatte. Eine Baumstruktur in eine eingerückte Liste umzuwandeln, geht in O(n)-Zeit
    Das war damals eine meiner Interviewfragen, und es gibt Methoden, so etwas in verschiedenen SQL-Datenbanken zu speichern, damit man Teile des Baums schnell ohne rekursive Abfragen holen und rendern kann
    Wenn man diese Konzepte einmal verstanden hat, hat das saubere Speichern der Daten als Baum deutlich mehr Vorteile als solche Einrückungstricks

    • Wenn man diese Vorteile nicht braucht, ist das allerdings kaum wichtig

  • „Eine Möglichkeit, Baumstrukturdaten aus einer relationalen Datenbank per SQL-Abfrage zu holen, ist die Verwendung rekursiver CTEs (Common Table Expressions), und das macht ungefähr so viel Spaß, wie der Name vermuten lässt“
    CTE sind nicht beängstigend, auch rekursive CTEs nicht, und ich behaupte, wenn man sich daran gewöhnt hat, machen sie tatsächlich Spaß

    • CTEs machen nicht wirklich Spaß. Einen ganzen Stapel von CTEs in ein anderes SQL-Fenster zu kopieren, nur um den interessierenden Teil zu debuggen, ist nicht meine Vorstellung von Unterhaltung
    • Rekursive CTEs waren extrem langsam, wenn man Baumdaten aus einer normalisierten Darstellung zusammensetzen musste
      Um einen Knotenpfad mit Hierarchietiefe d zusammenzusetzen, dauerte es mindestens d-mal länger, bis das Abfrageergebnis vorlag
      Der Vorteil war, dass Bearbeitungen am Baum billig waren, aber sie kamen viel seltener vor als Lesezugriffe
    • CTEs sind in Ordnung. Der Autor hätte auch statt diese Information in die Tabelle einzubacken per CTE eine View mit formatierten Namen erstellen können

  • Beim Punkt „Oft wollen oder brauchen Menschen in Wirklichkeit keinen Baum, sondern nur etwas, das wie ein Baum aussieht“ sieht man den Unterschied zwischen HN und Reddit
    Bei HN ist ein Kindkommentar das nextSibling des Elternkommentars und wird durch eine um 1 erhöhte Einrückung des Elternteils wie ein Baum dargestellt
    Bei Reddit, zumindest auf old.reddit.com, sind Kindkommentare tatsächlich innerhalb des Elternkommentars verschachtelt. Wie es auf der neuen Seite ist, weiß ich nicht

    • Du meinst die HTML-Struktur, nicht die tatsächliche Darstellung? Das sichtbare Ergebnis ist fast identisch
    • Schwer vorstellbar, dass das im Backend wirklich so gespeichert wird
      Jede Operation auf den Daten würde zu einem komplizierten Durcheinander werden, bei dem man erst die Baumstruktur erschließen und sie dann wieder in ein implizites Baumformat zurückübersetzen müsste
    • Dann frage ich mich, wie das Einklappen funktioniert

  • Die zentrale Idee des Artikels ist einfach: Man sollte die Struktur verwenden, die zum Problem passt
    Ich halte nur die Erzählung für falsch. Man braucht keine CTE, um einen Baum aus der Datenbank zu holen; man kann eine flache Liste laden und den Baum lokal zusammensetzen. Für spätere Manipulationen würde man das ohnehin vermutlich tun
    Nach derselben Logik könnte man Leuten, die zum Speichern einer Liste eine relationale Datenbank verwenden, auch sagen, sie sollten sie einfach in eine Textdatei schreiben. Warum überhaupt die Kosten von Netzwerklatenz zahlen?
    Umgekehrt verhält sich die vorgeschlagene Struktur bei ausreichend großen Bäumen schlecht, wenn man Äste verschieben und Tiefen ändern will, weil das linear kostet
    Die Absicht hätte von Anfang an klar benannt werden sollen. Nicht erst drei Beispiele erklären und dann im Fazit mit „Wenn du einen Baum brauchst, dann verwende einen Baum“ wieder entwerten. Wäre das gleich am Anfang gestanden, wäre es allerdings deutlich weniger Clickbait gewesen

  • Vor ein paar Jahren hatte ich eine ähnliche Erkenntnis bei OpenGL. Ich musste nicht eine Welt aus hierarchischen 3D-Objekten zeichnen, sondern einfach nur eine sortierte Liste von Dreiecken
    Dieser Gedanke hat bei mir einen Schalter umgelegt, und viele Optimierungen wurden plötzlich sehr einfach

    • Genau. In 3D-Spielen seit 2000 ist Einfachheit eine große Stärke
      Selbst in Spielen mit komplexen Entity-Hierarchien muss man beim Einfügen in die Render-Queue oft auf eine flache Struktur reduzieren, etwa wegen Transparenzsortierung
      „Eine flache Liste von Dingen“ ist auch die Grundlage von ECS/DOD

  • Es gibt ganze Bücher darüber, wie man solche Dinge in Datenbanken behandelt
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • Angeblich sollen ja alle Bücher für Anfänger sein — gefällt mir

  • Eine weitere Methode, einen Fake-Baum zu bauen, ist das Speichern eines JSON-Blobs
    Wenn die Daten nur interne Beziehungen haben, kann das einfacher sein, als eine Sortiernummer eindeutig und geordnet zu halten

    • Man könnte sogar sagen, dass ein als verschachteltes JSON dargestellter Baum eher ein „echter“ Baum ist als ein virtueller Baum, der durch Parent-Referenzen in einer Datenbank entsteht