Rutnätfil - Grid file

Inom datavetenskap är en rutnätfil eller skopgaller en punktåtkomstmetod som delar upp ett utrymme i ett icke-periodiskt rutnät där en eller flera celler i rutnätet hänvisar till en liten uppsättning punkter. Rutnätfiler (en symmetrisk datastruktur ) ger en effektiv metod för att lagra dessa index på disken för att utföra komplexa datasökningar.

Det ger ett rutnät med n -dimensioner där n representerar hur många nycklar som kan användas för att referera till en enda punkt.

Rutfiler innehåller inga data själva utan innehåller istället referenser till rätt hink .

Användningar

En rutnätfil används vanligtvis i fall där ett enda värde kan refereras med flera nycklar.

En rutnätfil började användas på grund av att "traditionella filstrukturer som ger åtkomst till multikey till poster, till exempel inverterade filer, är förlängningar av filstrukturer som ursprungligen var utformade för enkelnyckelåtkomst. De uppvisar olika brister, särskilt för multikey-åtkomst till mycket dynamiska filer . "

I en traditionell endimensionell datastruktur (t.ex. hash ) är en sökning på ett enda kriterium vanligtvis mycket enkel men sökning efter ett andra kriterium kan vara mycket mer komplex.

Rutfiler representerar en speciell typ av hashing, där den traditionella hash ersätts med en rutnätkatalog.

Exempel

Folkräkningsdatabas

Tänk på en databas som innehåller data från en folkräkning. En enda post representerar ett enda hushåll, och alla poster grupperas i hinkar. Alla poster i en skopa kan indexeras av antingen deras stad (vilket är detsamma för alla poster i skopan) och gatorna i den staden vars namn börjar med samma bokstav.

En rutnätfil kan användas för att tillhandahålla ett effektivt index för denna struktur, där poster finns i grupperingar om 26, var och en av dem relaterar till gatunamn i en stad som börjar med en av bokstäverna i alfabetet. Denna struktur kan ses som en matris , tabell eller rutnät med två dimensioner som vi kommer att kalla x- och y-axlarna.

Man kan betrakta x-axeln som staden och y-axeln som var och en av bokstäverna i alfabetet, eller alternativt den första bokstaven i varje gata.

Varje post i denna struktur är känd som en cell. Varje cell innehåller en pekare till lämplig hink i databasen där den faktiska informationen lagras. En extra cell eller posthuvud kan behövas för att lagra stadens namn. Andra celler grupperade med det behöver bara innehålla pekaren till respektive hink, eftersom den första cellen motsvarar gatunamn som börjar med "A", den andra till "B" och så vidare.

Databasen kan utökas ytterligare så att den innehåller ett kontinentfält för att utöka folkräkningen till andra kontinenter. Detta skulle orsaka att poster i samma hink motsvarar hushållen på en gata som börjar med samma bokstav, i samma stad, på samma kontinent.

Cellerna i rutnätfilen skulle då bestå av en stadsrubrik och sex (en för varje kontinent, exklusive Antarktis ) grupperingar av 26 celler relaterade till gatorna med samma startbokstav, i samma stad, på samma kontinent och kan nu ses som en tredimensionell matris.

Fördelar

Eftersom en enda post i rutnätfilen innehåller pekare till alla poster som indexeras av de angivna nycklarna:

  • Inga speciella beräkningar krävs
  • Endast rätt poster hämtas
  • Kan också användas för enkla söknyckelfrågor
  • Lätt att utöka till frågor på n söktangenter
  • Betydande förbättring av bearbetningstiden för frågor med flera nycklar
  • Har en övre gräns för två skivåtkomst för åtkomst till data.

Nackdelar

På grund av karaktären på rutnätfilen, vilket ger den dess fördelar, finns det dock också några nackdelar:

  • Imponerar utrymme över huvudet
  • Prestandakostnader vid införande och radering

Relaterade datastrukturer

Se även

Referenser