Rozšiřitelné hašování - Fagin

Logické a fyzické schéma souboru, logický a fyzický záznam. Základní databázové operace. Hierarchie pamětí, magnetická páska, magnetický disk, RAID, jukebox. Halda, sekvenční soubor, index-sekvenční soubor, indexovaný soubor. Bitové indexy. Jednoduchá hašovací schemata. Perfektní hašování. Dynamické hašování, skupinové štěpení stránek. Hašovací schemata na částečnou shodu. B-stromy, B+-stromy. B*-stromy, (a,b)-stromy. Srovnání paralelního přístupu pomocí B-stromů a (a,b)-stromů. Struktury pro vícerozměrnou indexaci: VB-stromy, vícerozměrná mřížka. n-cestný algoritmus třídění.
Uživatelský avatar
DZuXO
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 20. 1. 2009 11:28
Typ studia: Informatika Bc.

Rozšiřitelné hašování - Fagin

Příspěvek od DZuXO »

Nazdar ludia,
po fiasku, ktore som zazil na poslednej skuske som bol nuteny poriadne pozriet tomu Fagin hashovaniu na zub.

Na cvikach to sice bolo fajn, skoda ze moje zapisky su smutne a ja si nepamatam delikatne situacie.
Na wikipedii je jeden clanok, ktory je ale uplne odveci a nepochopil som z toho nic.
V knihe Základy Implementace souborů a databazí je to fajn, az na nejasnosti, ktore ma doteraz sprevadzaju.
Teraz sa mi konecne podarilo najst nieco, co vyzera pomerne slusne. Je to subor (.pdf), ktory som vlozil do prilohy. Jedna sa o akysi clanok, ktoreho odkaz som nasiel na wikipedii. Nechal som ho nepozmeneny (su tam aj ine zaujimave veci) a Fagin tam zacina od strany 20. Je to pekne popisane s obrazkami a vysvetleniami krokov, ale POZOR, je tam jedna drobna chybicka. Na str. 25, posledny odsek, ma tam byt i3 namiesto i1. Aspon myslim, ine chybicky som si nevsimol.

Otazka je, v com sa ten clanok hlavne lisi od knihy ?
Napriklad v knihe (str. 51) je "dosahnuti maxima" hlbky stranky vyjadrene ako lambda=beta. Dodnes tomu nerozumiem, ale po skuske som si isty, ze je to dolezite. Podla clanku to vyzera, ze to "dosahnuti maxima" je dosiahnutie maximalnej velkosti stranky (pravdepodobne staticky zadana). Podla knihy som ani len netusil, ze tie stranky su obmedzene velkostou.
Dalej je tam napisane, ze po vlozeni do stranky, ktorej lokalna hlbka je rovna hlbke adresara, nastava zdvojnasobenie adresara. Podla clanku to sice je pravda, ale stranka musi byt navyse plna ! Naozaj neviem, ktore z toho je spravne, ale to s tou plnou strankou sa mi to paci viac :? .

Mohli by ste prosim niekto, kto mate chut, pripadne to riesite, alebo je vam to cele davno jasne, do tychto zalezitosti vniest trochu svetla ?
Budem nesmierne vdacny za akukolvek radu :) .
Přílohy
lecture.extendible.hashing.pdf
(85.09 KiB) Staženo 380 x
UIRA — UIRA Isn't a Recursive Acronym.
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Rozšiřitelné hašování - Fagin

Příspěvek od peci1 »

DZuXO píše: Mohli by ste prosim niekto, kto mate chut, pripadne to riesite, alebo je vam to cele davno jasne, do tychto zalezitosti vniest trochu svetla ?
Budem nesmierne vdacny za akukolvek radu :) .
Nazdar Martine, zkusim to sem hodit, aspon si v tom sam udelam jasno =)

Zakladem je adresar. To je struktura, kterou si drzis vetsinou v operacni pameti. Pokud by se tam nevesel, musi se to brat z disku, ale pak by cely algoritmus rapidne ztratil na efektivite. Adresar je tabulka (predstavuj si ho treba jako asociativni pole), kde kazdy radek obsahuje dve informace.
  • prefix - oznacme d delku toho prefixu (pro vsechny zaznamy v adresari je stejna)
  • pointer na prislusnou stranku
Krome adresare pak mas samozrejme stranky, do kterych strkas data. To jsou treba fyzicke stranky na disku. Tim padem maji pevnou velikost (na slidech oznacovanou B). Kazdy zaznam ve strance ma nejakou velikost (ve slidech R), takze se do jedne stranky vejde b ( = B/R ) zaznamu (b je blokovaci faktor).

Kdyz hledas prvek s klicem K, spocitas h(K) (zahashujes klic) a vezmes prvnich d bitu z te hodnoty (ono by nevadilo ani brat je odzadu, ale tak uz nam to nadefinoval). Tenhle prefix vyhledas v adresari a dostanes pointer na stranku, kde se zaznam nachazi. Tu nactes do operacni pameti a pak ji (zanedbatelne rychle) prohledas.

Insert probiha nasledovne. Stejne jako pri hledani zjistis pointer na stranku, kam zaznam patri. Pokud se tam zaznam vejde, vlozis ho tam. Pokud ne, musi se stranka rozstepit. U kazde stranky si drzis hodnotu d', ktera rika, podle kolika bitu jsou rozlisovany zaznamy ve strance (tyhle hodnoty si drzis v operacni pameti). Pokud d' < d, tak urcite na stranku vedou z adresare aspon 2 pointery. V tom pripade staci naalokovat novou stranku, prevest na ni prislusny pointer v adresari, a pak vezmes zaznamy z pretecene stranky a ty rozdelis mezi ty dve stranky podle toho, kteremu prefixu odpovidaji. Pak obema strankam zvysis d'. V pripade, ze d = d', na stranku vede jen jeden pointer. Ted prichazi chvile na stepeni adresare. Zvetsis d o jednicku (prodlouzis prefixy v adresari). Kazdy zaznam v adresari zduplikujes (velikost adresare se zdvojnasobi), vzdycky udelas jeden radek, kde k prefixu pridas 0, a druhemu pridas k prefixu 1. Tim docilis, ze na kazdou stranku ukazujou aspon 2 pointery a muzes postupovat podle pripadu d' < d.

Delete je celkem easy, proste zaznam oznacis za neplatny (nebo ho fyzicky smazes). Problem muze byt, pokud by melo dojit ke slucovani stranek. Po delete se ujistis, jestli by nesla ta stranka spojit se sesterskou (tj. tou, jejiz prefix konci na opacny bit). Pokud by sla (tj. dohromady ty stranky obsahuji min prvku nez b), pak je sloucis. Po slouceni se jeste podivas na d' vsech stranek. Pokud by vsechna byla ostre mensi nez d, pak muzes sloucit adresar - tj. zmensit d o jednicku a provest opacnou operaci ke stepeni adresare. U delete je dobre pouzit nejaky treshold pro slucovani stranek/adresare, aby ti po sobe jdouci inserty a delety stejnych prvku nezpusobily caste "pulzovani" adresare nebo slucovani a rozdelovani stranek.

Mne samotneho by zajimaly pocty IO operaci, tak se je pokusim nacrtnout.
  • fetch - vzdycky staci precist 1 stranku (adresar je v pameti), tedy TF = r + s + btt
  • insert - pokud nestepis, tak staci TF + 2r (nactes stranku, pockas, az se plotna otoci, a zapises zpatky); pokud stepis (a je jedno, jestli jen stranku, nebo cely adresar!), tak TF + 2r + s + r (jednu stranku prectes, zapises ji zpatky, a pak zapises novou stranku - ta muze byt na disku uplne jinde)
  • delete - stejne jako insert (pri slucovani stranek u te smazane musis poznacit, ze je neplatna, takze do ni stejne musis zapsat).
No, snad jsem to vysvetlil pochopitelne, a bez chyb. Kdyby tam neco nesedelo, dejte vedet, taky budu rad =)
steves
Matfyz(ák|ačka) level I
Příspěvky: 33
Registrován: 13. 12. 2008 16:29
Typ studia: Informatika Bc.

Re: Rozšiřitelné hašování - Fagin

Příspěvek od steves »

Ještě bych dodal, že insert/delete to může být trochu složitější.

U deletu lze teoreticky slučovat opakovaně (třeba až do chvíle, kdy se adresář zmenší na velikost 1), pseudokód ve skriptech tuhle možnost neobsahuje a v odstavci pod ním je jenom napsáno něco jako, že pro zjednodušení neuvažujeme opakované slučování. Když jsem před zkouškou zkoumal, jak vlastně ten delete má fungovat, vygooglil jsem tenhle dokument
http://www.site.uottawa.ca/~lucia/cours ... /lect19.ps
(pozor: narozdíl od toho, jak se to učíme my, tady berou bity od konce, ale jinak by to mělo být stejné.) Tam je příklad, kdy delete vyvolá hned několik slučování.

U insertu se může stát, že vkládaný záznam se do stránky nejenže nevejde, ale s ostatními záznamy ve stránce nelze rozlišit podle (d+1) bitu, ale třeba až podle (d+3) bitu, tím pádem musíme adresář rozšířit hned 3x, abychom ty problematické záznamy mohli rozhodit do dvou stránek.
Odpovědět

Zpět na „DBI007 Organizace a zpracování dat I“