Metraipolis › archive › dc_07ff862735a8

Gridfile — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Gridfile
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T01:06:37.546Z
SHA-256 of the archived text
2a55076c09a993f11fb67eef75a8893e5539c6aec626b2ec88c16e1bca6c118b
Stable URL of this page
https://metraipolis.com/documento/dc_07ff862735a8

How to cite

Gridfile — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Gridfile (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_07ff862735a8 (Metraipolis archive dc_07ff862735a8, sha256 2a55076c09a993f11fb67eef75a8893e5539c6aec626b2ec88c16e1bca6c118b)
BibTeX
@misc{dc07ff862735a8,
  title = {Gridfile — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Gridfile},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_07ff862735a8; sha256 2a55076c09a993f11fb67eef75a8893e5539c6aec626b2ec88c16e1bca6c118b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Gridfile. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Gridfile» — https://de.wikipedia.org/wiki/Gridfile
Wikidata Q1546257: «mehrdimensionale Indexstruktur für Daten in der Informatik» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1546257
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Gridfile?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 250345582, consultata il 2026-11-08T01:02:59.404Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ee2f1dffd9c20a7550dc152c1bfa6ee9026ba58f087d02201950297f85b363f5