Ruudukkotiedosto

Gridfile (engl. = Grid ritilä) on ainakin kaksiulotteinen indeksi rakenne , etsintää tietojen, jossa on 2 tai useampia kriteerejä suuresti kiihtynyt. Perinteisissä yksiulotteisissa tietorakenteissa (esim. Hajautustaulukko ) yhden kriteerin etsiminen on yleensä hyvin yksinkertaista, kun taas toisen kriteerin etsiminen on erittäin aikaa vievää . Ruudukkotiedostot edustavat erityistä hajautustyyppiä, jossa perinteinen hajautusfunktio korvataan ruudukkohakemistolla.

Yleisten ruudukkotiedostojen dimensio on k, mikä tarkoittaa, että ne tallentavat k-ulotteista tietoa näppäimillä S1 ... Sk. Ruudukkotiedostot ovat yksi symmetrisistä tietorakenteista , koska mikään avainarvoista ei ole suositeltava, mutta kaikki avaimet syötetään aina tasaisesti.

Esimerkiksi ruudukotiedostossa, kun etsitään kolmea ehtoa, kuten kolmiulotteinen kuutio, asiaankuuluva tietue löytyy suoraan. Useimmissa tapauksissa tietoja ei tallenneta itse ruudukkotiedostoon (mikä vie liikaa tilaa, jos kuutio on vain kohtalaisen täynnä), vaan vain viittaus ämpäriin , johon halutut tiedot on tallennettu. Ämpäri tallentaa useita vierekkäin olevia tietueita ruudukkotiedostoon .

Niin kutsuttu kahden levyn käyttöperiaate koskee ruudukkotiedostoa. Tämä tarkoittaa sitä, että pyydetty tietue on käytettävissä enintään kahden pyynnön jälkeen toissijaiseen muistiin. Tämän varmistamiseksi hakemistorakenne ja todelliset tiedot tallennetaan kahteen erilliseen tietorakenteeseen. Koska hakemistorakenne on suhteellisen pieni verrattuna käsiteltävään dataan, se voidaan ihanteellisesti pitää myös päämuistissa.

Kauhat käsitellään käyttämällä ns. Asteikoita, jotka muodostavat hakemistorakenteen. Kullekin ulottuvuudelle k luodaan asteikko, joka lajittelee ämpärien rajat vastaavaan ulottuvuuteen ja sisältää hakemiston tälle ulottuvuudelle. Yhdistämällä yksittäisten asteikoiden merkinnät voidaan määrittää vastaava ämpäri, joka sisältää haettujen koordinaattien tiedot.

Ruudukkotiedosto on epäherkkä tietoklustereille, koska se reagoi sisällön ominaisuuksiin mukautuvana tietorakenteena jakamalla tai ulottuvuuden tarkentamalla (ämpäriin ylivuototapauksessa) ja yhdistämällä (ämpäri alivuoto).

Katso myös

Tietokantaindeksissä , quadpuu , Kd puu , UB puu , R puu , alue puu vaihtoehtoina

nettilinkit