Daten in Baumstruktur speichern

[Michael Schröpl]

Hi Andreas,

Soweit ich das jetzt verstanden habe gibt es sowohl die Möglichkeit in PERL einen B-Baum zu speichern, wo ich mir halt noch nicht wirklich vorstellen kann wie das funkionieren soll

wenn Du eine Speicherstruktur irgendwohin duplizieren willst, dann gibt es (mindestens) zwei Möglichkeiten:
a) Du versuchst, sie zu verstehen, und ihren Inhalt (in einer ggf. anderen Form) auf dem Zielmedium irgendwie darzustellen. In diesem Fall ist der Aufwand mindestens linear zur Anzahl der Elemente Deiner Speicherstruktur - ganz einfach, weil Du sie elementweise verarbeitest.
b) Du verzichtest darauf, sie zu verstehen, und wendest Dich statt dessen an eine "tiefere Ebene". Im Falle eines Baums könnte dies darin bestehen, daß Du einfach den kompletten RAM-Bereich auslagerst, in welchem dieser Baum enthalten ist. Das kann bezogen auf den I/O-Traffic "etwas zuviel" sein, aber der Aufwand ist nun unabhängig davon, wieviele Knoten Du hast - er ist nur noch abhängig davon, in wie vielen Seiten diese Knoten dargestellt sind.
Während Du bei b) den exakten Originalzustand des Baums wiederherstellen wirst, hast Du bei a) die Möglichkeit, zusätzlich sekundäre Ziele zu verfolgen - beispielsweise die physikalische Struktur Deiner logischen Daten zu beeinflussen. Stell Dir vor, Du weißt, wie viele Knoten ein Baum enthält - dann kannst Du beim Kopieren des Baums nebenbei dafür sorgen, daß die Kopie wieder optimal balanciert ist ... der Ziel-Baum hat dann eine andere Struktur, aber (bezüglich der Anordnung seiner Knoten für eventuelle Traversierungsoperationen) immer noch denselben Inhalt.

genausowenige verstehe ich wei man eine Hash speichern können soll

Meinst Du hier intern oder extern? (Wobei beides im Falle von b) identisch sein könnte, im Falle von a) nicht unbedingt.)

nur habe ich mit solchen Dingen noch nie zu tun gehabt und kann es mir halt nicht vorstellen.

Informatik III, Algorithmen und Datenstrukturen. (Das gleichnamige Buch von Niklaus Wirth ist in dieser Hinsicht immer noch lesenswert, auch wenn meine uralte Auflage von 1980 drucktechnisch miserabel war und Wirth zur Notation seiner Algorithmen PASCAL verwendet.)

nur würde mir hier keine Struktur für einen Hash und einen B-Baum einfallen,

Eine Struktur ist generell nicht "an sich gut", sondern immer nur in Bezug auf eine gestellte Aufgabe. Welche Randbedingungen sollte diese Struktur erfüllen? Welche Arten von Operationen möchtest Du auf dieser Datenstruktur durchführen können? Welche Operationen soll mit welchen Kosten (komplexitätstheoretisch betrachtet) realisierbar sein?

daher vermute ich das das nicht in FlatFiles gespeichert wird, sondern in irgendeinem binären Format, was ich mir sowieso nicht angucken kann ...

Erstens kannst Du das im Quelltext des entsprechenden Programms nachlesen (beispielsweise demjenigen der mySQL-Tabellentreiber), und zweitens ist es relativ egal, ob diese Daten binär oder menschenlesbar gespeichert sind: Das ist lediglich eine zusätzliche polynomielle Transformation, die komplexitätstheoretisch nicht ins Gewicht fällt.

naja, ich muß noch vieles lernen ;-)
Vor allem PERL und C(++)

Ich denke, eher Datenstrukturen und Algorithmen. Die Umsetzung in eine konkrete Sprache ist das kleinere Problem: Entweder hat diese Sprache ein fertige Modul dafür, oder Du schreibst Dir eines.

Was ich für wichtiger halte, ist das Verständnis dafür, daß manche Datenstrukturen bestimmte Operationen auf bestimmten Daten in bestimmten Kostenfunktionen erlauben ... die Erkenntnis, _wieso_ Bäume und logarithmische Zugriffe zueinander gehören, ist ein wichtiger Lernerfolg, und die Verallgemeinerung auf B*-Bäume mit dem entsprechenden Folgen für die Komplexität der Algorithmen ist dann nicht mehr schwer.
Im Vergleich dazu funktionieren gehashte Daten (also solche, die über eine Hash-Funktion statt einen Baum adressiert werden), durchaus anders ... und Du hast dabei mehr Schräubchen, an denen Du drehen kannst (und mußt) als bei einem (binären) Baum.

Viele Grüße
      Michael