Gridfile

Gridfile

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. Hashtabelle) 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 welcher die klassische Hashfunktion durch ein Grid-Verzeichnis ersetzt wird.

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 zu viel Platz in Anspruch nehmen würde), sondern nur ein Verweis in welchem Bucket die gewünschten Daten abgelegt sind. Ein Bucket speichert mehrere im Gridfile nebeneinanderliegende Datensätze ab.

Bei einem Gridfile gilt das so genannte two-disk-access Prinzip. D.h., dass ein gesuchter Datensatz nach spätestens zwei Anfragen auf einen Sekundärspeicher vorliegt. Um dies zu gewährleisten werden die Indexstruktur und die eigentlichen Daten in zwei separaten Datenstrukturen abgelegt. Da die Indexstruktur im Vergleich zu den zu adressierenden Daten relativ klein ist, kann diese im Optimalfall auch im Hauptspeicher gehalten werden.

Die Adressierung der Buckets geschieht hierbei durch die Benutzung sogenannter Skalen, welche die Indexstruktur bilden. Für jede Dimension k wird eine Skala erstellt, welche die Grenzen der Buckets in der entsprechenden Dimension sortiert hinterlegen und einen Index für diese Dimension enthalten. Durch die Kombination der Einträge in den einzelnen Skalen kann somit der entsprechende Bucket ermittelt werden welcher die Daten für die gesuchten Koordinaten enthält.

Ein Gridfile ist unempfindlich gegenüber Datenhäufungen, da es als adaptive Datenstruktur durch Splittung oder Dimensionsverfeinerung (bei Bucketüberlauf), sowie Verschmelzung (bei Bucketunterlauf) auf die Eigenschaften des Inhalts reagiert.

Siehe auch

Datenbankindex, Quadtree, K-d-Baum, UB-Baum, R-Baum, Bereichsbaum als Alternativen

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • K-d-Baum — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • Kd-Baum — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • Kd-Tree — Ein k dimensionaler Baum oder k d Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher,… …   Deutsch Wikipedia

  • R*-Baum — Ein Beispiel eines R Baums Ein R Baum (eng. R tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur. Inhaltsverzeichnis 1 Verwendungszweck 2 …   Deutsch Wikipedia

  • R-tree — Ein Beispiel eines R Baums Ein R Baum (eng. R tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur. Inhaltsverzeichnis 1 Verwendungszweck 2 …   Deutsch Wikipedia

  • Range tree — Ein Bereichsbaum (engl.: range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k dimensionalen reellen Raum . Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient… …   Deutsch Wikipedia

  • Rtree — Ein Beispiel eines R Baums Ein R Baum (eng. R tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur. Inhaltsverzeichnis 1 Verwendungszweck 2 …   Deutsch Wikipedia

  • Sekundärindex — Ein Datenbankindex, oder kurz Index (im Plural Indexe oder Indizes ), ist eine von der Datenstruktur getrennte Indexstruktur in einer Datenbank, die die Suche und das Sortieren nach bestimmten Feldern beschleunigt. Ein Index besteht aus einer… …   Deutsch Wikipedia

  • Universal B-Tree — Der UB Baum („Universal B Tree“) wurde von Rudolf Bayer und Volker Markl vorgeschlagen und ist eine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein B+ Baum, bei dem die Daten nach der Z Kurve (Berechnen der Z Werte durch bitweise… …   Deutsch Wikipedia

  • Bereichsbaum — Ein Bereichsbaum (englisch range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k dimensionalen reellen Raum . Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”