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

Read other articles:

9M337 Sosna-R

9M337 Sosna-R Sosna surface-to-air missile system. Jenis Surface to air missile Negara asal Russian Federation Sejarah pemakaian Masa penggunaan May 2019 Digunakan oleh Russian Federation Sejarah produksi Tahun 2017 Produsen High Precision Systems Diproduksi 2022 Varian See variants 9M337 Sosna-R atau SA-24 adalah rudal dua tahap supersonik dipandu radar dan laser buatan Rusia. Rudal ini digunakan dalam sistem rudal pertahanan udara jarak pendek. Sosna-R dirancang untuk melind...

 

 

Gempa bumi Bengkulu Agustus 2020

Gempa Bumi Bengkulu 2020Waktu UTC2020-08-18 21:23:57ISCUSGS-ANSSTanggal setempat19 Agustus 2020 (2020-08-19)Waktu setempat05:23:56 WIB 05:29:35 WIBKekuatan6,8 Mw 6,9 MwKedalaman11 km (6,8 mi) 10 km (6,2 mi)Episentrum4°30′S 100°55′E / 4.50°S 100.91°E / -4.50; 100.91Koordinat: 4°30′S 100°55′E / 4.50°S 100.91°E / -4.50; 100.91 3°44′S 101°31′E / 3.74°S 101.51°E /...

 

 

Victorian Women's Football League

Australian rules football league for women Victorian Women's Football LeagueSportAustralian rules footballFirst season1981Ceased2016Replaced byVFL Women's South Eastern Women's FootballNo. of teams31 (final season)CountryAustraliaHeadquartersMelbourne, AustraliaLastchampion(s)Deer Park (2016)Most titlesScorpions (11)TV partner(s)C31Official websiteVictorian Women's Football League The rucks reach for the ball after the umpire (in orange) has balled it up. A Melbourne University player jostles...

Stasiun Settai

Stasiun Settai摂待駅Stasiun Settai pada Mei 2009LokasiTarō-aze Settai, Miyako-shi, Iwate-ken 027-0000JepangKoordinatKoordinat: 39°48′33.51″N 141°57′43.74″E / 39.8093083°N 141.9621500°E / 39.8093083; 141.9621500OperatorSanriku Railway CompanyJalur■ Rias LineLetak113.5 km dari SakariJumlah peron1 peron sampingJumlah jalur1KonstruksiJenis strukturAtas tanahInformasi lainStatusTanpa stafSitus webSitus web resmiSejarahDibuka1 April 1984PenumpangFY20157 per...

 

 

Sie Gubba

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Sie Gubba – news...

 

 

Enoch W. Eastman

American politician An illustration of Eastman Enoch W. Eastman (April 30, 1810 – January 9, 1885) was an American politician. Born in Deerfield, New Hampshire, Enoch Worthen Eastman studied law in New Hampshire and was admitted to the bar. He then moved to Iowa. Although a Democrat, he distinguished himself the first year of his residence in Iowa by taking the stump against the adoption of the Constitution recently framed by his party and helped to defeat it at the election. Under this Con...

Associazione Sportiva Bari 1950-1951

Voce principale: Associazione Sportiva Bari. AS BariStagione 1950-1951Sport calcio Squadra Bari Allenatore Federico Allasio (1ª-7ª) Ambrogio Alfonso e Raffaele Costantino (8ª-12ª) Mario Sandron (13ª-19ª) Francesco Capocasale (20ª-21ª) Paolo Giammarco (22ª) Pietro Piselli (23ª-24ª) Paolo Giammarco (25ª) Raffaele Costantino e Francesco Capocasale (26ª-42ª) Presidente Rocco Scafi Serie B18º posto. Retrocesso in Serie C. Maggiori presenzeCampionato: Griffith(37) Miglior marca...

 

 

Battle of Khartoum (2023–present)

Battle during the 2023 Sudan conflict For the 1884–1885 siege, see Siege of Khartoum. Not to be confused with Battle of Kutum. This article needs to be updated. Please help update this article to reflect recent events or newly available information. (October 2023) Battle of KhartoumPart of the war in SudanSituation in and around Khartoum and Omdurman as of February 2024   Sudanese Armed Forces presence   Rapid Support Forces presence   Contested (most likely wi...

 

 

Gregorio Manzano

Spanish football manager In this Spanish name, the first or paternal surname is Manzano and the second or maternal family name is Ballesteros. Gregorio Manzano Manzano as manager of Mallorca in 2009Personal informationFull name Gregorio Manzano Ballesteros[1]Date of birth (1956-03-11) 11 March 1956 (age 68)[1]Place of birth Bailén, Spain[1]Managerial careerYears Team1983–1985 Santisteban1985–1986 Villacarrillo1986–1988 Iliturgi1988–1989 Villanueva...

Comparative anatomy

Study of similarities and differences in the anatomy of different species Comparative anatomy studies similarities and differences in organisms. The image shows homologous bones in the upper limb of various vertebrates. Comparative anatomy is the study of similarities and differences in the anatomy of different species. It is closely related to evolutionary biology and phylogeny[1] (the evolution of species). The science began in the classical era, continuing in the early modern perio...

 

 

Joseph Plateau

Joseph Plateau Joseph Antoine Ferdinand Plateau (Bruxelles, 14 ottobre 1801 – Gand, 15 settembre 1883) è stato un fisico belga. È noto, in particolare, per l'invenzione, nel 1832[1], di uno strumento ottico, il fenachistoscopio, che permetteva di visualizzare immagini animate:[2][3][4] questa invenzione contribuì allo sviluppo della tecnica cinematografica.[5] Indice 1 Biografia 2 Opere 3 Note 4 Voci correlate 5 Altri progetti 6 Collegamenti estern...

 

 

Robert Goodwill

Robert Goodwill Robert Goodwill (lahir 31 Desember 1956) adalah seorang petani dan politikus Partai Konservatif Britania Raya yang menjabat sebagai anggota parlemen sejak 2005. Ia sebelumnya menjadi anggota parlemen Eropa.[1] Referensi ^ Robert Goodwill MP: Current Roles. UK Government.  Pranala luar Robert Goodwill MP official site Profil di Parlemen Britania Raya Kontribusi di Parlemen di Hansard Catatan suara di Public Whip Catatan di Parlemen di TheyWorkForYou Robert Goodwill...

Ponce metropolitan area

Statistical area in Puerto Rico Metropolitan area in Puerto Rico, United StatesPonce metropolitan area Mayagüez metropolitan areaMetropolitan areaPonce–Coamo, PR CSA   Ponce MSA   Coamo μSA   Other Statistical Areas in Puerto Rico Country United StatesTerritory Puerto RicoPrincipal cities Ponce Coamo Time zoneUTC−4 • Summer (DST)AST The Ponce Metropolitan Statistical Area is a United States Census Bureau defined Metropolitan Statistica...

 

 

Natchez Trace

Historic trail in the southern United States Part of the original Natchez Trace near Natchez, Mississippi Old Trace historical marker The Natchez Trace, also known as the Old Natchez Trace, is a historic forest trail within the United States which extends roughly 440 miles (710 km) from Nashville, Tennessee, to Natchez, Mississippi, linking the Cumberland, Tennessee, and Mississippi rivers. The trail was created and used by Native Americans for centuries, and was later used by early Euro...

 

 

1993 Western Australian state election

1993 Western Australian state election ← 1989 6 February 1993 (1993-02-06) 1996 → All 57 seats in the Western Australian Legislative Assemblyand all 34 seats in the Western Australian Legislative Council29 Assembly seats were needed for a majority   First party Second party   Leader Richard Court Carmen Lawrence Party Liberal/National coalition Labor Leader since 12 May 1992 12 February 1990 Leader's seat Nedlands Glendalough Last ...

داكوتا الشمالية

داكوتا الشمالية  علم شعار الشعار:(باللاتينية: Serit ut alteri saeclo prosit)‏ (11 مارس 2011–)    الإحداثيات 47°30′N 100°30′W / 47.5°N 100.5°W / 47.5; -100.5   [1] تاريخ التأسيس 2 نوفمبر 1889  سبب التسمية قبيلة داكوتا  تقسيم إداري  البلد الولايات المتحدة[2][3]  التقس...

 

 

Landry N'Guémo

Landry N'Guémo Informasi pribadiNama lengkap Landry Joel Tsafack N'GuémoTanggal lahir 28 November 1985 (umur 38)Tempat lahir Yaoundé, KamerunTinggi 1,74 m (5 ft 8+1⁄2 in)Posisi bermain GelandangInformasi klubKlub saat ini BordeauxNomor 7Karier junior2001–2005 NancyKarier senior*Tahun Tim Tampil (Gol)2005–2011 Nancy 127 (4)2009–2010 → Celtic (pinjaman) 30 (0)2011– Bordeaux 35 (1)Tim nasional‡2006– Kamerun 28 (3) * Penampilan dan gol di klub senior ha...

 

 

Lee Morgan

American jazz trumpeter (1938–1972) Lee MorganMorgan in 1959Background informationBirth nameEdward Lee MorganBorn(1938-07-10)July 10, 1938Philadelphia, Pennsylvania, U.S.DiedFebruary 19, 1972(1972-02-19) (aged 33)New York City, U.S.GenresJazzhard boppost-bopOccupation(s)MusicianInstrumentsTrumpetflugelhornYears active1956–1972LabelsBlue NoteVee-JayFormerly ofThe Jazz MessengersMusical artist Edward Lee Morgan (July 10, 1938 – February 19, 1972) was an American jazz trumpeter and co...

Geschichte der Juden in Polen

Polnische Jüdinnen und Juden des 17. und 18. Jahrhunderts in typischer Kleidung Die Geschichte der Juden in Polen beginnt im späten 10. Jahrhundert und reicht von einer langen Periode religiöser Toleranz sowie relativen Wohlstands bis zur fast vollständigen Vernichtung der jüdischen Bevölkerung während der deutschen Besetzung Polens. Seit seiner Konsolidierung ab 960 galt das Königreich Polen als einer der religiös tolerantesten Staaten Europas. Mit dem 1264 von Herzog Bole...

 

 

Internazionali di Tennis Castel del Monte

Internazionali di Tennis Castel del MonteSport Tennis CategoriaATP Challenger Tour Paese Italia LuogoAndria ImpiantoPalaSport SuperficieCemento indoor DirettoreVincenzo Ormas CadenzaAnnuale DisciplineSingolare e doppio maschile Partecipanti32S/16D StoriaFondazione2013 Numero edizioni7 (2022) Detentore Leandro Riedi Detentori Julian Cash Henry Patten Ultima edizioneInternazionali di Tennis Castel del Monte 2022 Modifica dati su Wikidata · Manuale Gli Internazionali di Tennis Castel ...