Hallo Gemeinde,
als Schüler (Gymnasium, nicht Berufsschule) ist es äußerst schwierig an verständliches Material aus einem Informatikstudium - speziell zum Thema Datenstrukturen - zu kommen.
Ich möchte eine Struktur, sagen wir mal ein B-Baum oder B+-Baum, in eine Datei speichern.
Es gibt tolle Quellen im Internet, die erklären, wie man so einen Baum erstellt, wie man Knoten rotieren lässt und wie man ihn durchsucht.
Leider beziehen sich all diese Quellen auf einen Baum, welcher im Arbeitsspeicher vorgehalten wird und somit behandelt werden kann, wie jedes andere Objekt.
Mir geht es aber an dieser Stelle darum, einen Baum zu erstellen, ihn in eine Datei zu speichern und ihn - ohne ihn noch einmal komplett in den Speicher einzulesen - manipulieren zu können.
Ich habe aber keinen Schimmer wie ich das Speichern oder Durchsuchen praxisnah anstellen soll. Das einzige Beispiel (STRG + F + "Inorder Traversierung" - dann ist man im richtigen Absatz), was einen guten Speicher-Denkanstoß lieferte, zielte auf einen völlig ausgeglichenen Baum ab. Das mein Baum ausgeglichen ist, ist ein schönes Ziel, kann aber niemals garantiert werden - oder etwa doch?
Weiterhin frage ich mich, wie ich so eine Datei dann durchsuchen soll, ohne sie komplett einzulesen.
Schließlich kann ich nicht sagen, dass ich 10 Bytes weiterspringen muss, um an das Kind zu kommen, weil nicht klar ist, ob die Knoten dazwischen nicht deutlich länger sind und man somit im falschen Knoten landet.
Ziel ist es, nachvollziehen zu können, wie z.B. Datenbanken ihre Daten ablegen und auch den größten Index in so rasanter Geschwindigkeit durchsuchen können.
Ich erhielt hierzu einen Beitrag aus einem Fachinformatiker-Forum:
Leider ging man dann auf weiterführende Fragen nicht mehr ein, z.B. wie so eine Speicherung in der Praxis dann aussehen soll (z.B. vom 500. Knoten bis zum Blatt? -> Das ergibt in der Datei eine umgekehrte Pyramide in meiner Vorstellung).
Ich bin gespannt auf eure Denkanstöße und Referenzen, ein paar Diskussionen zu diesem Thema gab es schließlich schon in dieser Community.
Danke!
Kleine Anmerkung vielleicht noch hinten dran:
Da das Thema - zumindest für mich - etwas exotischer zu sein scheint, habe ich diese Fragen auch in anderen Communities gestellt. Wenn es von deren Seite ein paar Rückmeldungen gibt, bring' ich die hier mal direkt mit ein.
als Schüler (Gymnasium, nicht Berufsschule) ist es äußerst schwierig an verständliches Material aus einem Informatikstudium - speziell zum Thema Datenstrukturen - zu kommen.
Ich möchte eine Struktur, sagen wir mal ein B-Baum oder B+-Baum, in eine Datei speichern.
Es gibt tolle Quellen im Internet, die erklären, wie man so einen Baum erstellt, wie man Knoten rotieren lässt und wie man ihn durchsucht.
Leider beziehen sich all diese Quellen auf einen Baum, welcher im Arbeitsspeicher vorgehalten wird und somit behandelt werden kann, wie jedes andere Objekt.
Mir geht es aber an dieser Stelle darum, einen Baum zu erstellen, ihn in eine Datei zu speichern und ihn - ohne ihn noch einmal komplett in den Speicher einzulesen - manipulieren zu können.
Ich habe aber keinen Schimmer wie ich das Speichern oder Durchsuchen praxisnah anstellen soll. Das einzige Beispiel (STRG + F + "Inorder Traversierung" - dann ist man im richtigen Absatz), was einen guten Speicher-Denkanstoß lieferte, zielte auf einen völlig ausgeglichenen Baum ab. Das mein Baum ausgeglichen ist, ist ein schönes Ziel, kann aber niemals garantiert werden - oder etwa doch?
Weiterhin frage ich mich, wie ich so eine Datei dann durchsuchen soll, ohne sie komplett einzulesen.
Schließlich kann ich nicht sagen, dass ich 10 Bytes weiterspringen muss, um an das Kind zu kommen, weil nicht klar ist, ob die Knoten dazwischen nicht deutlich länger sind und man somit im falschen Knoten landet.
Ziel ist es, nachvollziehen zu können, wie z.B. Datenbanken ihre Daten ablegen und auch den größten Index in so rasanter Geschwindigkeit durchsuchen können.
Ich erhielt hierzu einen Beitrag aus einem Fachinformatiker-Forum:
Du speicherst, zuerst die Baumstruktur (mindestens von der letzten Abzweigung bis zum Blatt) und danach den Wert
Solange du hier mit einer Datei arbeitest, ist das sehr ineffizent, da du die Datei immer Durchsuchen musst weil du keinen direkten Zugriff auf eine bestimmte Stelle nehmen kannst.Wie nutze ich den in der Datei gespeicherten Index, ohne ihn vollständig in den Arbeitsspeicher einzulesen?
Du musst also die Datei Stück für Stück nach dem gesuchten Wert durchlaufen bis du auf ihn gestoßen bist.
Effizienter wäre zumindest den Baum in verschiedene Dateien zu unterteilen, oder sich am besten ganz von Dateien zu verabschieden um direkten Zugriff auf einzelne Blöcke zu bekommen
Leider ging man dann auf weiterführende Fragen nicht mehr ein, z.B. wie so eine Speicherung in der Praxis dann aussehen soll (z.B. vom 500. Knoten bis zum Blatt? -> Das ergibt in der Datei eine umgekehrte Pyramide in meiner Vorstellung).
Ich bin gespannt auf eure Denkanstöße und Referenzen, ein paar Diskussionen zu diesem Thema gab es schließlich schon in dieser Community.
Danke!
Kleine Anmerkung vielleicht noch hinten dran:
Da das Thema - zumindest für mich - etwas exotischer zu sein scheint, habe ich diese Fragen auch in anderen Communities gestellt. Wenn es von deren Seite ein paar Rückmeldungen gibt, bring' ich die hier mal direkt mit ein.