Gridfile
aus Wikipedia, der freien Enzyklopädie
Ein Gridfile (engl. Grid = Gitter) ist eine mindestens zweidimensionale Indexstruktur, die das Suchen nach Daten mit 2 oder mehr Kriterien erheblich beschleunigt. Bei den traditionellen eindimensionalen Datenstrukturen (z. B. Hash) ist eine Suche nach einem Kriterium meist sehr einfach, die Suche nach einem zweiten Kriterium sehr zeitintensiv. Gridfiles stellen eine besondere Art von Hashing dar, in welchen der klassische Hash durch ein Grid-Verzeichnis ersetzt werden.
Allgemeine Gridfiles haben die Dimension k, was bedeutet, dass sie k-dimensionale Daten mit den Schlüsseln S1...Sk speichern. Gridfiles zählen zu den symmetrischen Datenstrukturen, da keiner der Schlüsselwerte bevorzugt wird, sondern immer alle Schlüssel gleichberechtigt eingehen.
Im Gridfile kann zum Beispiel bei der Suche nach drei Kriterien wie in einem dreidimensionalen Würfel direkt der betroffene Datensatz gefunden werden. Im Gridfile selbst sind meistens nicht die Daten abgelegt (was bei einem nur mäßig gefüllten Würfel viel zuviel Platz kosten würde) sondern nur ein Verweis in welchem GridBag die gewünschten Daten abgelegt sind. Ein GridBag speichert mehrere im Gridfile nebeneinanderliegende Datensätze ab.
Der Nachteil von Gridfiles liegt in seiner schlechten Eignung für korrelierte oder ungleichmäßig verteilte Daten. Hier fallen unter Umständen zuviele Daten in ein GridBag was zu einer schlechten Verteilung im Grid-Verzeichnis führt.
[Bearbeiten] Siehe auch
Quadtree, K-d-Baum, UB-Baum, R-Baum, Bereichsbaum als Alternativen
