Fórum studentů MFF UK

Nevite nekdo, jak by se resily priklady 4 a 5 z te pisemky, ktera je nekde tu na foru nebo i ve studnici (nevim, jestli je z minuleho nebo z predminuleho roku)?

Rušíme záznam v souboru organizovaném v rozšířitelném (Faginově) hašování s adresářem ve dvou stránkách na disku.
· Kolik bufferů (1 buffer = 1 stránka) je třeba alokovat ve vnitřní paměti? 1
· Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?

5. Mějme redundantní B-strom (m = 6) se třemi úrovněmi, jehož část je zachycena na
obrázku.
· Zakreslete, jak bude vypadat odpovídající část uvedeného B-stromu po přidní
prvku 13.
· Jaký je minimální počet bufferů potřebný pro provedení uvedené operace
INSERT za předpokladu, že pro potřeby uvedené operace každou stránku
načítáme nejvýše 1x?
· Kolik stránek musíme mít pro danou operaci nejvíce zamčených, jsou-li operace
na uvedeném B-stromě prováděny paralelně?
· Kolik času bychom potřebovali na provedení dané operace za předpokladu, že
žádnou ze stránek nemáme v paměti (s=8,5ms, r=4,7ms, btt=0,2ms) a že s diskem
nepracuje žádný jiný proces?


Je to za spoustu bodu (zvlast ta 5) a ja vubec nevim jak se pracuje s tema bufferama a jak spocitat ten cas .

aja píše:Rušíme záznam v souboru organizovaném v rozšířitelném (Faginově) hašování s adresářem ve dvou stránkách na disku.
· Kolik bufferů (1 buffer = 1 stránka) je třeba alokovat ve vnitřní paměti? 1

1 buffer ti urcite nestaci, pokud by doslo na slevani stranek, potrebujes buffery na obe dotycne stranky. Aby se zbytecne znova nenacitalo z disku, potrebujes buffery 4.

aja píše:· Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?

READ 1. stranky adresare do bufferu 1
READ 2. stranky adresare do bufferu 2
READ stranky, ve ktere je vypousteny prvek, do bufferu 3, vypustime ho, spocteme prvky
READ stranky, ktera je s touto sdruzena, tj. jedina, s kterou ji lze slevat, do bufferu 4, spocteme prvky
Nyni mame tri moznosti:
1. Stranky neni nutne slevat => WRITE stranky v bufferu 3, dohromady 4 READ a 1 WRITE
2. Stranky slevame, ale adresar nezkracujeme. Nejhorsi je v tomto pripade, kdyby na obe stranky bylo pouzito mene bitu, nez je v adresari. Pointry ukazujici na jednu stranku je nutne prepsat - adresar je na 2 stranky. Nemohlo by se nam stat, ze bychom prepisovali pointery na obou z nich? Nemohlo, v takovem pripade bychom si vybrali tu druhou, a protoze jsou ostruvky pointeru souvisle, musi uz byt na jedne strance v adresari => WRITE nove stranky (jeji vytvoreni je mozne na miste z bufferu 3 a 4), WRITE adresare (vytvoreni taktez na miste), dohromady 4 READ a 2 WRITE.
3. Stranky slevame, adresar zkracujeme. WRITE nove stranky( jeji vytvoreni je opet mozne na miste), WRITE noveho adresare( jeho vytvoreni je mozne na miste posouvanim pointeru, novy adresar je polovicni, tedy na jednu stranku). Tedy 4 READ a 2 WRITE.
V nejhorsim pripade je to 6 I/O operaci.

aja píše:5. Mějme redundantní B-strom (m = 6) se třemi úrovněmi, jehož část je zachycena na
obrázku.
· Zakreslete, jak bude vypadat odpovídající část uvedeného B-stromu po přidní
prvku 13.
· Jaký je minimální počet bufferů potřebný pro provedení uvedené operace
INSERT za předpokladu, že pro potřeby uvedené operace každou stránku
načítáme nejvýše 1x?
· Kolik stránek musíme mít pro danou operaci nejvíce zamčených, jsou-li operace
na uvedeném B-stromě prováděny paralelně?
· Kolik času bychom potřebovali na provedení dané operace za předpokladu, že
žádnou ze stránek nemáme v paměti (s=8,5ms, r=4,7ms, btt=0,2ms) a že s diskem
nepracuje žádný jiný proces?

Pripomenuti: Strom je trojurovnovy, v koreni je jeste misto, mame zakreslenou jen cestu nejvice vlevo a uzly jsou plne. Doprostred toho nejvice vlevo patri cislo 13, tedy je nutne provest deleni na nejnizsi urovni, i o uroven vys.

Oznacme K koren stromu, S stredni uzel, L list, N novy list, R novy rozstepeny stredni uzel.
Prace je takova:
1) READ K do bufferu 1, zamek je nutny, cas s + r + btt (je to na nahodnem miste na disku)
2) READ S do bufferu 2, zamek je nutny, uzel je plny, takze zamky nad nim uvolnit nelze, cas s + r + btt (je to na nahodnem miste na disku).
3) READ L do bufferu 3, zamek je nutny, uzel je plny, takze zamky nad nim uvolnit nelze, cas s + r + btt (je to na nahodnem miste na disku).
4) Rozdelime L do bufferu 3 a 4.
5) Zapiseme L z bufferu 3, zamek uvolnime, cas 2r (je to rewrite, jsme na spravne stope, cekame na data), buffer 3 uvolnime.
6) Rozdelime S do bufferu 2 a 3.
7) Zapiseme S z bufferu 2, zamek uvolnime, cas s + r + btt (je to na nahodnem miste na disku), buffer 2 uvolnime.
Najdeme volne misto (??Lze predpokladat, ze mame dve volne stranky za sebou??), cas s + r
9) Zapiseme N z bufferu 4, cas btt, buffer 4 uvolnime.
10) Zapiseme R z bufferu 3, cas btt, buffer 3 uvolnime.
11) Zapiseme K z bufferu 1, zamek uvolnime, cas s + r + btt (je to na nahodnem miste na disku), buffer 1 uvolnime.

Celkem jsme tedy potrebovali 4 buffery (mezi kroky 4-5 a 6-7), 3 zamky (mezi kroky 3-5) a potrebny cas je 6s + 8r + 7btt = 90 ms.

Tyjo, pekny . Dik moc .

Ahoj a jak by se pocitalo tohle:

3. Mějme indexovaný soubor s blokovacím faktorem primárního souboru b = 6, v něm je
uložených 597 záznamů. Indexy jsou tvořeny B+-stromem (m = 60; primární klíč) a
bitovou mapou (příslušný atribut nabývá šesti hodnot). Předpokládejme, že žádná data
nejsou načtena do paměti.
· Spočtěte, kolik přístupů na disk bude třeba pro vyhledání záznamu podle
primárního klíče? Uveďte postup. 4
· Spočtěte, kolik nejméně přístupů na disk bude třeba na přidání nového záznamu
do uvedeného souboru? Odůvodněte. 4
· Předpokládejme, že uvedený soubor je umístěn na disku s parametry s = 8,5ms,
r = 4,2ms, btt = 0,2ms. Kolik času budeme přinejhorším potřebovat na přidání
záznamu? 5

Dik

Návštěvník píše:Ahoj a jak by se pocitalo tohle:

3. Mějme indexovaný soubor s blokovacím faktorem primárního souboru b = 6, v něm je
uložených 597 záznamů. Indexy jsou tvořeny B+-stromem (m = 60; primární klíč) a
bitovou mapou (příslušný atribut nabývá šesti hodnot). Předpokládejme, že žádná data
nejsou načtena do paměti.
· Spočtěte, kolik přístupů na disk bude třeba pro vyhledání záznamu podle
primárního klíče? Uveďte postup. 4
· Spočtěte, kolik nejméně přístupů na disk bude třeba na přidání nového záznamu
do uvedeného souboru? Odůvodněte. 4
· Předpokládejme, že uvedený soubor je umístěn na disku s parametry s = 8,5ms,
r = 4,2ms, btt = 0,2ms. Kolik času budeme přinejhorším potřebovat na přidání
záznamu? 5

Dik

Tento příklad je už rozebrán zde http://forum.matfyz.info/viewtopic.php?f=386&t=2380