Hallo,

ich beschäftige mich seit einiger Zeit mit verschiedenen Indexstrukturen und fand im Netz auch einige Referenzen, die mal veranschaulichen, wie man die Struktur von B-Bäumen und B+-Bäumen implementiert.

Allerdings sehe ich in allen entdeckten Implementierungen folgendes Problem:

Die Daten werden in einem Objekt vorgehalten. Daten, die in einem Objekt vorgehalten werden, werden im Arbeitsspeicher gesichert.

Wenn ich mir nun eine MySQL-Datenbank ansehe, dann nutzt die ihren Index, ohne ihn zwangsläufig komplett in den Arbeitsspeicher einzulesen.

Darauß ergeben sich für mich folgende Fragen:

Wie speichere ich eine Baumstruktur (egal welcher Art) in eine Datei?

Wie nutze ich den in der Datei gespeicherten Index, ohne ihn vollständig in den Arbeitsspeicher einzulesen?

Dabei gibt es für mich (vorerst) folgende Annahme:

Ich kann nicht davon ausgehen, dass der Server die gesamte Indexdatei in den Arbeitsspeicher aufnehmen kann, da dieser zu klein ist.

Hintergründe zu mir:

- ich bin kein Fachinformatiker oder Student, ich bin Schüler an einem Gymnasium. Da ich Informatik auch nicht belege, handelt es sich hierbei auch um keine Hausaufgabe. Antworten nach längerer Zeit sind also ebenso gerne gesehen!

- ich bin gut in PHP bewandert und steige gerade in Java ein, wobei ich mittelfristig meine Kenntnisse in Java mit Hilfe dieses Projektes etwas schärfen möchte

Ich würde mich über Ansätze, Referenzen und Ähnliches sehr freuen.

Wie speichere ich eine Baumstruktur (egal welcher Art) in eine Datei?

Du speicherst, zuerst die Baumstruktur (mindestens von der letzten Abzweigung bis zum Blatt) und danach den Wert

Wie nutze ich den in der Datei gespeicherten Index, ohne ihn vollständig in den Arbeitsspeicher einzulesen?

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.

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

Hallo und danke für Dein Feedback!

Du speicherst, zuerst die Baumstruktur (mindestens von der letzten Abzweigung bis zum Blatt) und danach den Wert

Ich verstehe das gerade so:

Von Knoten 500 aus, sind es noch mindestens 300 Knoten bis zum ersten Blatt.

Also speichere ich insgesamt 300 Knoten in eine Dateizeile.

Das würde für mich eine Art umgekehrte Pyramide ergeben.

Lieg ich damit richtig?

Oder meinst Du, dass die letzten Knoten, die auf ein Blatt zeigen, abgespeichert werden sollten?

Quasi: letzter Knoten vor Blatt (5), Blatt(links), Blatt(rechts), Blatt(Mitte)?

Oder wie veranschaulicht man sich das?

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.

Bei MySQL ist es eigentlich auch nur eine Datei. Aber klar: Ich kann den Index natürlich auch aufsplitten, sodass ich in jedem Teilindex Werte aus einem bestimmten Wertebereich habe.

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

So ein Block muss doch auch ein Dateiformat besitzen, oder nicht?