Auswahl der optimalen Datenstruktur für hierarchische Daten

[vishal11]

Ich arbeite derzeit an einem Projekt, bei dem es um den Umgang mit hierarchischen Daten geht, und stehe vor einem Dilemma bei der Auswahl der am besten geeigneten Datenstruktur. Ich möchte eine effiziente Datenbearbeitung, -abfrage und -speicherung sicherstellen und dabei die besonderen Anforderungen meines Projekts berücksichtigen.

 

Ich möchte die Community um Rat fragen, wie ich die optimale Datenstruktur für diesen speziellen Anwendungsfall auswählen kann. Welche Faktoren sollte ich bei dieser Entscheidung berücksichtigen? Gibt es Best Practices oder Richtlinien, die befolgt werden müssen?

 

Darüber hinaus bin ich auch neugierig auf die Kompromisse zwischen verschiedenen Datenstrukturen in Bezug auf zeitliche Komplexität, räumliche Komplexität und Flexibilität. Wie kann ich diese Kompromisse abwägen, um eine fundierte Entscheidung zu treffen?

 

Wenn jemand Erfahrung mit der Arbeit an ähnlichen Projekten hat oder sich mit Datenstrukturen auskennt, würde ich mich sehr über einige Beispiele aus der Praxis oder Codeausschnitte freuen, die die Vorteile und Einschränkungen verschiedener Datenstrukturen für verschiedene Szenarien veranschaulichen.

 

Vielen Dank für Ihre wertvollen Erkenntnisse und Anregungen!

 

 

 

 

[Wodar Hospur]

Das klingt so gestellt wie eine typische Seminararbeit…

Was auch okay ist, wenn ein richtiger Austausch gewünscht ist, das heißt Antworten auf folgende Fragen:

- Was sind denn die besonderen Anforderungen des Projekts?

- Welche Faktoren siehst du selber?

- Welche operationelle Realitäten müssen berücksichtigt werden?

 

Ansonsten kann ich generisch nur das Buch: Designing Data Intensive Applications empfehlen.

 

[Whiz-zarD]

Es kommt auf den Zweck an, was man erreichen möchte. Auch die Speicherung könnte komplett unterschiedlich aussehen. Als Beispiel nehme ich mal Personendaten:

• Vorname
• Nachname
• Straße
• Hausnummer
• Postleitzahl
• Stadt
• Bundesland

Folgt man jetzt z.B. DDD und bei einer objektorientierten Sprache die sog. Object Calisthenics, ergibt das z.B. folgende Datenstukturen:

Person
  + Name : Name
  + Adresse : Adresse
  
Name
  + Vorname : String
  + Nachname : String
  
Adresse
  + Straße : Straße
  + Stadt : Stadt
  
Straße
  + Name : string
  + Nummer : string
  
Stadt
  + Name : string
  + Bundesland : string

Wenn die Normalisierung in einer relationalen Datenbank nicht wichtig oder sogar hinderlich ist, kann man die Daten ja auch denormalisiert speichern:

  Vorname  |  Nachname  |  Straße |  Hausnummer  |  Postleitzahl  |  Stadt  |  Bundesland
-----------+------------+---------+--------------+----------------+---------+--------------
           |            |         |              |                |         |

Der O/R-Mapper würde dir dann die Objekte zusammenbasteln, wie du sie brauchst.

Denormalisierte Tabellen sind z.B. für Auswertungen über SQL sinnvoller, da die ganzen Join-Ketten wegfallen. Joins verhalten sich immer sehr negativ zur Performance und erhöhen auch die Komplexität der Abfragen.

Oder man benutzt eine dokumentenbasierte Datenbank und speichert die Datenstruktur einfach als JSON-Objekt.

Auch sog. Value Objects könnten relevant sein, denn Wertetypen (int, double, ...) folgen oft einer Business-Logik. z.B. hat ein Spielwürfel sechs Seiten. Da kann es Probleme geben, wenn man dann einer Methode einen Integer-Wert zwischen 1 und 6 mitgibt. Dann muss die Methode überprüfen, ob der Wert wirklich zwischen 1 und 6 liegt. Eleganter wäre es, würde man es dann in ein Value Object verpacken und dort die Gültigkeit überprüft.

Wenn man aber die Daten sehr performant und speichersparend auswerten analysieren möchte, kann man sich an Datenstrukturen orientieren, wie sie auch z.B. in R vorkommen. Also anstatt ein "Array of objects" ein "Object of arrays". D.h. jede Eigenschaft ist ein Array und man greift mit der Indexierung auf die einzelnen Datensätze:

Persons
  + Vorname : string[]
  + Nachname : string[]
  + Straße : string[]
  + Hausnummer : string[]
  + Postleitzahl : string[]
  + Stadt : string[]
  + Bundesland : string[]

Dadurch spart man sich den ganzen Overhead der Objekte und auch die ganze (De-)Referenzierung. Das wirkt aber vielleicht gerade in objektorientierten Sprachen etwas komisch.

Ich persönlich würde immer aus Sicht der Domäne anfangen, denn die macht den Code verständlich und Rubust. Optimieren kann man aber später immer noch, wenn man merkt, dass es wirklich zwickt. Wichtig ist aber erstmal das Anfangen und nicht schon im Vorwege optimieren. Was bringt es einem, mehrere Tage eine Datenstruktur zu erarbeiten, die kaum jemand versteht aber nur wenig zur Performance beiträgt? Dann hat man die Tage mit Mikrooptimierungen verbracht.

[hellerKopf]

vor 5 Stunden schrieb vishal11:

.... mit hierarchischen Daten geht, ..... Auswahl der am besten geeigneten Datenstruktur.

Zwar muss ich raten, was hierarhische Daten alles umfassen könnte, aber ich denk jetzt mal Organisationsstrukturen, Stammbäume etc.

Dann Bäume aufgrund ihrer effizienten Suche, einfachen Navigation, natürlichen Repräsentation von Hierarchien und Erweiterbarkeit.
Diese werden in vielen Sprachen unterstützt werden.

Python bietet die tree-Bibliothek sowie die eingebaute dict-Datenstruktur

 In Java kann ein Baum mit Hilfe der Klassen und Schnittstellen aus dem java.util-Paket erstellt werden.
 TreeNode kann als Basis für die Implementierung von Baumstrukturen verwendet werden.

C++:  Die std::map und std::set Container

JavaScript: In JavaScript können Bäume mit Hilfe von Objekten und Referenzen erstellt werden. Durch die Verwendung von JavaScript-Bibliotheken wie d3.js (Data-Driven Documents) können Bäume erstellt und visualisiert werden.

Ruby: In Ruby können Bäume mithilfe von Bibliotheken wie rgl (Ruby Graph Library) oder tree erstellt werden. Darüber hinaus bietet Ruby eingebaute Klassen wie Hash und Array, die zur Implementierung von Baumstrukturen verwendet werden können.