Mřížkový soubor - Grid file
v počítačová věda, a mřížkový soubor nebo mřížka lopaty je metoda přístupu k bodu který rozděluje prostor na neperiodický mřížka kde jedna nebo více buněk mřížky odkazuje na malou sadu bodů. Soubory mřížky (a symetrický datová struktura ) poskytují efektivní metodu ukládání těchto indexů na disk za účelem provedení komplexního vyhledávání dat.
Poskytuje mřížku n-dimenziony kde n představuje, kolik klíčů lze použít k odkazu na jeden bod.
Soubory mřížky neobsahují žádná data, ale obsahují odkazy na správné Kbelík.
Použití
A mřížkový soubor se obvykle používá v případech, kdy lze na jednu hodnotu odkazovat více klíči.
Soubor mřížky se začal používat, protože „tradiční struktury souborů, které poskytují vícepodlažní přístup k záznamům, například obrácené soubory, jsou rozšířeními souborových struktur původně navržených pro přístup jedním klíčem. Projevují se různými nedostatky zejména u vícepodlažního přístupu k vysoce dynamickým souborům . “ [1]
V tradiční jednorozměrné datové struktuře (např. hash ), je vyhledávání na jednom kritériu obvykle velmi jednoduché, ale hledání druhého kritéria může být mnohem složitější.
Soubory mřížky představují speciální druh hashování, kde je tradiční hash nahrazen adresářem mřížky.
Příklady
Databáze sčítání lidu[2][3]
Zvažte databázi obsahující data ze sčítání lidu. Jediný záznam představuje jednu domácnost a všechny záznamy jsou seskupeny do kbelíků. Všechny záznamy v kbelíku lze indexovat buď podle jejich města (které je stejné pro všechny záznamy v kbelíku), tak podle ulic v tomto městě, jejichž jména začínají stejným písmenem.
Soubor mřížky lze použít k poskytnutí efektivního indexu pro tuto strukturu, kde záznamy přicházejí ve seskupeních 26, přičemž každý z nich se týká názvů ulic ve městě začínajících jedním z písmen abecedy. Tuto strukturu lze považovat za pole, stůl nebo mřížka se dvěma rozměry, kterým budeme říkat osy xay.
Jeden může považovat osu x za město a osu y za každé písmeno v abecedě nebo alternativně za první písmeno každé ulice.
Každý záznam v této struktuře je znám jako buňka. Každá buňka bude obsahovat a ukazatel do příslušného segmentu v databázi, kde jsou uložena skutečná data. K uložení názvu města může být zapotřebí další buňka nebo záhlaví záznamu. Ostatní buňky seskupené s ní budou muset obsahovat pouze ukazatel na jejich příslušný segment, protože první buňka odpovídá názvům ulic začínajících na „A“, druhá na „B“ atd.
Databázi lze dále rozšířit tak, aby obsahovala kontinentální pole pro rozšíření sčítání na další kontinenty. To by způsobilo, že záznamy ve stejném kbelíku odpovídají domácnostem na ulici začínající stejným písmenem, ve stejném městě, na stejném kontinentu.
Buňky v souboru mřížky by pak sestávaly ze záhlaví města a šesti (jedna pro každý kontinent, bez) Antarktida ) seskupení 26 buněk vztahujících se k ulicím se stejným počátečním písmenem, ve stejném městě, na stejném kontinentu a nyní je lze považovat za trojrozměrné pole.
Výhody
Jelikož jedna položka v souboru mřížky obsahuje ukazatele na všechny záznamy indexované zadanými klíči:[4]
- Nejsou nutné žádné speciální výpočty
- Načtou se pouze správné záznamy
- Lze také použít pro jednotlivé vyhledávací klíčové dotazy
- Snadné rozšíření na dotazy n vyhledávací klávesy
- Významné zlepšení doby zpracování pro dotazy s více klíči
- Má horní hranici přístupu pro dva disky pro přístup k datům.[1]
Nevýhody
Vzhledem k povaze souboru mřížky, který mu dává jeho výhody, však existují i některé nevýhody:[4]
- Ukládá prostor nad hlavou
- Režijní výkon při vkládání a mazání
Související datové struktury
Viz také
- Příhradový graf
- Mřížka (prostorový index)
- Rejstřík (databáze), Čtyřstrom, KD strom, UB-strom, R-strom, rozsah strom jako alternativy.
Reference
- ^ A b J. Nievergelt, H. Hinterberger Soubor mřížky: Adaptabilní, symetrická struktura více souborů. Institut fur Informatik, ETH a K. C. Sevcik, 1984. Abstrakt, s. 1.
- ^ Donald Knuth. Umění počítačového programování, Svazek 3: Třídění a vyhledávání, Druhé vydání. Addison-Wesley, 1998. ISBN 0-201-89685-0. Oddíl 6.5: Hledání, str. 564–566.
- ^ Elmasri a Navathe Základy databázových systémů, Třetí edice. Addison-Wesley, 2000. ISBN 0-201-54263-3. Oddíl 6.4.3: Soubory mřížky, s. 185.
- ^ A b "Soubor mřížky". cs.sfu.ca. Citováno 2016-11-27.