Par drobnosti

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í.
Medved
Admin(ka) level I
Příspěvky: 168
Registrován: 30. 5. 2006 21:18

Par drobnosti

Příspěvek od Medved »

Tak ja se pomalu zacinam ucit na zkousku a budu tady mit obcas nejake dotazy :)

1) Litwin: "predpoklada se hasovaci funkce h(K), ktera pro libovolny klic vrati binarni cele cislo v dostatecnem rozsahu" (skripta). Ale my jsme nikdy zadnou hasovaci funkci neuvazovali, a vkladali jsme rovnou to, co prislo. Tak jak to je? A jak ma takova hasovaci funkce prosim vypadat, kdyz se kazdou chvili zvetsuji cisla stranek?

2) B stromy s promennou delkou zaznamu: B strom je definovany svou hodnotou m, jinak to neni B strom (skripta). Jake m je prosim u stromu s promennou delkou zaznamu? Rekneme, ze velikost bloku je 15.
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Par drobnosti

Příspěvek od peterblack »

Medved píše:1) Litwin: "predpoklada se hasovaci funkce h(K), ktera pro libovolny klic vrati binarni cele cislo v dostatecnem rozsahu" (skripta). Ale my jsme nikdy zadnou hasovaci funkci neuvazovali, a vkladali jsme rovnou to, co prislo. Tak jak to je? A jak ma takova hasovaci funkce prosim vypadat, kdyz se kazdou chvili zvetsuji cisla stranek?
-no treba v posledni pisemce byly normalne cisla v desitkovy soustave + hashovaci funkce, takze cislo ji vzal, prohnal hashovaci funkci a nakonec jsi to preved do binaru a podle toho zaradil do stranek
-nekdy ale zase bejvalo zes dostal rovnou cisla v binaru a a zadnou funkci, takze jsi je jenom tak jak jsi je mel zaradil do stranek
->z toho vyplyva ze prevod do binaru se pouziva pouze pro zarazeni a nekdy byva podlozen i nejakou tou hashovaci funkci - mrkni na nejaky stary pisemky na studnici + reseny priklad na tohle je taky tady: http://forum.matfyz.info/viewtopic.php?f=386&t=2397
Medved
Admin(ka) level I
Příspěvky: 168
Registrován: 30. 5. 2006 21:18

Re: Par drobnosti

Příspěvek od Medved »

Tak nejdriv jedna odpoved:
2) B stromy s promennou delkou zaznamu: B strom je definovany svou hodnotou m, jinak to neni B strom (skripta). Jake m je prosim u stromu s promennou delkou zaznamu? Rekneme, ze velikost bloku je 15.
Je to tak, ze muzeme uvazovat, ze kazdy zaznam je velikosti 1 a z toho pak nejake omezeni na m vyjde, ale neni to treba takto formalne brat.

A ted otazka

3) Delete z B stromu. Puvodne jsem si myslel, ze kdyz mam B strom X1 a mazu prvek A, tak hledam takovy B strom X2, ze kdyz do nej pridam prvek A, dostanu strom X1, tedy proste inverzni operace. To ale neni pravda, protoze treba mazani z korene znamena, ze vezmu nejmensi vetsi v listech a vymenim. No takze ma otazka: dokaze nekdo definovat, jak spravne mazat v B stromech, aby to bylo vzdy korektni dle Zemlicky? Je mi jasny, ze ve skriptech je nakej algoritmus v PASCALu, ale nestiham ho trasovat. A ten stejny dotaz pro B* stromy.
Triebenekl
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 5. 2. 2007 20:55
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Par drobnosti

Příspěvek od Triebenekl »

Medved píše: 3) Delete z B stromu. Puvodne jsem si myslel, ze kdyz mam B strom X1 a mazu prvek A, tak hledam takovy B strom X2, ze kdyz do nej pridam prvek A, dostanu strom X1, tedy proste inverzni operace. To ale neni pravda, protoze treba mazani z korene znamena, ze vezmu nejmensi vetsi v listech a vymenim. No takze ma otazka: dokaze nekdo definovat, jak spravne mazat v B stromech, aby to bylo vzdy korektni dle Zemlicky? Je mi jasny, ze ve skriptech je nakej algoritmus v PASCALu, ale nestiham ho trasovat. A ten stejny dotaz pro B* stromy.
Na prednasce jsme konkretni algoritmus mazani prvku z B-stromu neresili.
Na cvikach jsme si rikali, ze vysledek po DELETE dokonce nemusi byt vzdy jednoznacny (napr. zalezi jestli pri mazani z korene beres nejvetsi prvek z leveho ci nejmensi z praveho podstromu, apod.). Mel by snad stacit libovolny algoritmus, po kterem zustane nejaky B-strom (neobsahuje vymazany prvek).
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Par drobnosti

Příspěvek od peterblack »

ja se delete z Bstromu ucil tady:
http://cs.wikipedia.org/wiki/B_strom
je to par jednoduchych pravidel

pripadne v priloze mas muj prepis co jsem si delal na ADS1 :)
Přílohy
bstrom.pdf
(104.37 KiB) Staženo 330 x
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Par drobnosti

Příspěvek od hippies »

Jestli se nepletu (je to uz davno:) ), tak delete z B stromu autori popsali nejak ve stylu "obdobne";) a u zkousky zemlickovy staci kdyz budes pouzivat konzistentni postup (vzdy nejmensi vetsi, vzdy nejvetsi mensi apod.) ale musi splnovat dve podminky - funguje na kazdem korektnim B-strome a ma pozadovanou slozitost.
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Odpovědět

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