Rasterbestand - Grid file

In de informatica is een rasterbestand of emmerraster een punttoegangsmethode die een ruimte opsplitst in een niet-periodiek raster waarbij een of meer cellen van het raster naar een kleine reeks punten verwijzen. Rasterbestanden (een symmetrische gegevensstructuur ) bieden een efficiënte methode om deze indexen op schijf op te slaan om complexe gegevensopzoekingen uit te voeren.

Het biedt een raster van n -dimensies waarbij n staat voor hoeveel sleutels kunnen worden gebruikt om naar een enkel punt te verwijzen.

Grid-bestanden bevatten zelf geen gegevens, maar bevatten verwijzingen naar de juiste bucket .

Toepassingen

Een rasterbestand wordt meestal gebruikt in gevallen waarin naar een enkele waarde kan worden verwezen door meerdere sleutels.

Een rasterbestand begon te worden gebruikt omdat "traditionele bestandsstructuren die toegang met meerdere toetsen tot records bieden, bijvoorbeeld omgekeerde bestanden, extensies zijn van bestandsstructuren die oorspronkelijk zijn ontworpen voor toegang met één toets. Ze vertonen verschillende tekortkomingen, met name voor toegang met meerdere toetsen tot zeer dynamische bestanden ."

In een traditionele eendimensionale datastructuur (bijv. hash ) is zoeken op een enkel criterium meestal heel eenvoudig, maar zoeken naar een tweede criterium kan veel complexer zijn.

Rasterbestanden vertegenwoordigen een speciaal soort hashing, waarbij de traditionele hash wordt vervangen door een rastermap.

Voorbeelden

Census-database

Denk aan een database met gegevens van een volkstelling. Een enkele record vertegenwoordigt een enkel huishouden en alle records zijn gegroepeerd in buckets. Alle records in een bucket kunnen worden geïndexeerd op hun stad (die hetzelfde is voor alle records in de bucket), en de straten in die stad waarvan de naam met dezelfde letter begint.

Een rasterbestand kan worden gebruikt om een ​​efficiënte index voor deze structuur te bieden, waarbij records in groepen van 26 komen, elk met betrekking tot straatnamen in een stad die beginnen met een van de letters van het alfabet. Deze structuur kan worden gezien als een matrix , tabel of raster met twee dimensies die we de x- en y-assen zullen noemen.

Men kan de x-as beschouwen als de stad en de y-as als elk van de letters in het alfabet, of als alternatief de eerste letter van elke straat.

Elk record in deze structuur staat bekend als een cel. Elke cel bevat een verwijzing naar de juiste bucket in de database waar de feitelijke gegevens zijn opgeslagen. Er kan een extra cel of recordkop nodig zijn om de naam van de stad op te slaan. Andere cellen die ermee zijn gegroepeerd, hoeven alleen de aanwijzer naar hun respectieve emmer te bevatten, aangezien de eerste cel overeenkomt met straatnamen die beginnen met "A", de tweede met "B", enzovoort.

De database kan verder worden uitgebreid met een continentveld om de volkstelling uit te breiden naar andere continenten. Dit zou ertoe leiden dat records in dezelfde emmer overeenkomen met huishoudens in een straat die met dezelfde letter begint, in dezelfde stad, op hetzelfde continent.

De cellen in het rasterbestand zouden dan bestaan ​​uit een stadskop en zes (één voor elk continent, exclusief Antarctica ) groepen van 26 cellen die betrekking hebben op de straten met dezelfde beginletter, in dezelfde stad, op hetzelfde continent en kan nu worden gezien als een driedimensionale array.

Voordelen:

Aangezien een enkele vermelding in het rasterbestand verwijzingen bevat naar alle records die zijn geïndexeerd door de opgegeven sleutels:

  • Er zijn geen speciale berekeningen vereist
  • Alleen de juiste records worden opgehaald
  • Kan ook worden gebruikt voor zoekopdrachten met één zoeksleutel
  • Eenvoudig uit te breiden tot zoekopdrachten op n zoeksleutels
  • Aanzienlijke verbetering van de verwerkingstijd voor zoekopdrachten met meerdere toetsen
  • Heeft een bovengrens voor toegang tot gegevens via twee schijven.

nadelen

Vanwege de aard van het rasterbestand, dat het zijn voordelen geeft, zijn er echter ook enkele nadelen:

  • Legt ruimte boven je hoofd
  • Prestatieoverhead bij invoegen en verwijderen

Gerelateerde gegevensstructuren

Zie ook

Referenties