https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Gridfile 2026-05-26T03:23:16Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Gridfile&diff=165148&oldid=prev 2024-11-14T16:37:17Z

<p>BKS-Link entfernt - keine Zuordnung</p> <p><b>Neue Seite</b></p><div>Ein &#039;&#039;&#039;Gridfile&#039;&#039;&#039; (engl. Grid = Gitter) ist eine mindestens [[zweidimensional]]e [[Indexstruktur]], die das Suchen nach Daten mit 2 oder mehr [[Kriterium|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 [[Zeitkomplexität|zeitintensiv]]. Gridfiles stellen eine besondere Art von Hashing dar, in welcher die klassische [[Hashfunktion]] durch ein Grid-Verzeichnis ersetzt wird.<br /> <br /> Allgemeine Gridfiles haben die Dimension k, was bedeutet, dass sie k-dimensionale Daten mit den Schlüsseln S1...Sk speichern.<br /> Gridfiles zählen zu den symmetrischen [[Datenstruktur]]en, da keiner der Schlüsselwerte bevorzugt wird, sondern immer alle Schlüssel gleichberechtigt eingehen. <br /> <br /> Im Gridfile kann zum Beispiel bei der Suche nach drei Kriterien wie in einem dreidimensionalen [[Würfel (Geometrie)|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 [[Hashtabelle|Bucket]] die gewünschten Daten abgelegt sind. Ein Bucket speichert mehrere im Gridfile nebeneinanderliegende [[Datensatz|Datensätze]] ab.<br /> <br /> 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. <br /> <br /> 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.<br /> 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.<br /> <br /> 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.<br /> <br /> == Siehe auch ==<br /> [[Datenbankindex]], [[Quadtree]], [[K-d-Baum]], [[UB-Baum]], [[R-Baum]], [[Bereichsbaum]] als Alternativen<br /> <br /> == Weblinks ==<br /> * [http://www-lehre.inf.uos.de/~dbs/ Vorlesung Datenbanksysteme an der Universität Osnabrück], Kap. 5<br /> * [http://www.inf.uni-konstanz.de/dbis/teaching/ws0304/datatypes/download/paper-grid-file.pdf Übersicht über Gridfiles] (PDF-Datei; 350 kB, nicht mehr verfügbar, [https://web.archive.org/web/20160523011642/http://www.inf.uni-konstanz.de/dbis/teaching/ws0304/datatypes/download/paper-grid-file.pdf archivierte Version])<br /> <br /> [[Kategorie:Datenbankindex]]</div>

imported>Alossola