Deutsch
Menü

Datenstrukturen und Algorithmen

Was ist der Hauptgrund dafür, dass für Indizes in Datenbanken und Dateisystemen B-Bäume (einschließlich B+-Bäumen) statt binärer Suchbäume weit verbreitet sind?

  1. AJeder Knoten enthält viele Schlüssel; das hält den Baum flach und schränkt den Bereich mit jedem gelesenen Knoten stark ein, sodass weniger Blöcke von Festplatte oder ähnlichen Speichern gelesen werden müssen
  2. BJeder Knoten enthält nur einen Schlüssel, daher sind weniger Vergleiche nötig als in einem binären Suchbaum
  3. CDer Baum muss beim Einfügen nicht umgeformt werden und ist daher einfacher zu implementieren als ein binärer Suchbaum
Antwort und Erläuterung anzeigen

Antwort: A. Jeder Knoten enthält viele Schlüssel; das hält den Baum flach und schränkt den Bereich mit jedem gelesenen Knoten stark ein, sodass weniger Blöcke von Festplatte oder ähnlichen Speichern gelesen werden müssen

Festplatten und SSDs lesen Daten in Blöcken von einigen KB, selbst wenn nur ein Byte benötigt wird; es kommt daher darauf an, die Zahl der Lesevorgänge zu verringern. Ein B-Baum legt Hunderte von Schlüsseln in einen Knoten (einen Block), sodass jeder gelesene Knoten in Hunderte von Richtungen verzweigt; selbst 100 Millionen Datensätze sind in 3 bis 4 Ebenen erreichbar. Läuft ein Knoten durch Einfügen über, wird er geteilt, und wird er durch Löschen zu leer, wird er mit einem anderen verschmolzen; so bleiben alle Blätter auf derselben Tiefe. Ein binärer Suchbaum mit 100 Millionen Datensätzen braucht mindestens etwa 27 Ebenen, und auf jeder Ebene einen anderen Block zu lesen, ist langsam.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?
  2. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  3. In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?
  4. In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?
  5. Welche Bedingung an den Graphen ist erforderlich, damit der Dijkstra-Algorithmus korrekte kürzeste Wege findet?