Buffery/IO operace v B-stromech

[twoflower]

V testech jsou casto otazky typu "Jaky je minimalni pocet bufferu potrebny pro provedeni operace INSERT na danem strome?".

S jakou velikosti bufferu se vlastne pocita? Predpoklada se buffer velikosti jedne stranky, tzn. jednoho uzlu stromu?

Pokud ano, nerozumim tomu, proc na slidech je jako minimalni pocet bufferu pro INSERT uvedeno h+1 (h je vyska stromu).

Proc to neni jen h? Nez dojdu do listu, kam budu vkladat, nactu h stranek = h bufferu a potom uz jen vlozim prvek (mluvime o minimalnim poctu, tzn. zadne stepeni). K cemu je navic ten jeden buffer?

Diky za vysvetleni.

[twoflower]

Taky nevim, jaka je odpoved na nasledujici otazku vztahujici se k vlozeni prvku 13 do tohoto redundantniho B-stromu (m = 6):



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ě?

Jaka je vlastne strategie uzamykani/odemykani stranek? Nevzpominam si, ze bychom to na cviceni delali, tak si nejsem jisty.

Diky.

[MyS]

A neni to treba pocet I/O operaci? hxR + 1xW. Jinak taky bych rekl, ze h bufferu. Ale defakto ani buffery nepotrebuju a stacil by jen jeden;).

A k tomu zamykani. Co mam z prednaky: pri pristupu na stranku ji zamknu. Pokud ma volno, muzu odemknout stranky nad ni (protoze stepeni skonci maximalne tady), jinak nic neodemykam a jdu dolu. Takze tady bych to videl na ty vsechny 3 stranky...

[twoflower]

A neni to treba pocet I/O operaci? hxR + 1xW. Jinak taky bych rekl, ze h bufferu. Ale defakto ani buffery nepotrebuju a stacil by jen jeden;).

Prave ze ne, jde o buffery. Je to s nimi vubec takove pofiderni.

[D]

Este by chcelo dodat ze kazdu strnku chcem citat maximalne jeden krat, tedy vsetky co precitam davam do buffrov

[Trupik]

Pokud ano, nerozumim tomu, proc na slidech je jako minimalni pocet bufferu pro INSERT uvedeno h+1 (h je vyska stromu).

Proc to neni jen h? Nez dojdu do listu, kam budu vkladat, nactu h stranek = h bufferu a potom uz jen vlozim prvek (mluvime o minimalnim poctu, tzn. zadne stepeni). K cemu je navic ten jeden buffer?

Diky za vysvetleni.

Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?

[twoflower]

Pokud ano, nerozumim tomu, proc na slidech je jako minimalni pocet bufferu pro INSERT uvedeno h+1 (h je vyska stromu).

Proc to neni jen h? Nez dojdu do listu, kam budu vkladat, nactu h stranek = h bufferu a potom uz jen vlozim prvek (mluvime o minimalnim poctu, tzn. zadne stepeni). K cemu je navic ten jeden buffer?

Diky za vysvetleni.

Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?

To urcite jo, ale tady slo prave o minimalni pocet, takze to chapu pro INSERT bez stepeni.

[Trupik]

Pokud ano, nerozumim tomu, proc na slidech je jako minimalni pocet bufferu pro INSERT uvedeno h+1 (h je vyska stromu).

Proc to neni jen h? Nez dojdu do listu, kam budu vkladat, nactu h stranek = h bufferu a potom uz jen vlozim prvek (mluvime o minimalnim poctu, tzn. zadne stepeni). K cemu je navic ten jeden buffer?

Diky za vysvetleni.

Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?

To urcite jo, ale tady slo prave o minimalni pocet, takze to chapu pro INSERT bez stepeni.

Aha, tak to ja to chapu obracene. Kdyz se me zepta kolik budu minimalne potrebovat stranek pro insert, tak reknu tolik, kolik mi bude opravdu vzdycky stacit...

[twoflower]

Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?

To urcite jo, ale tady slo prave o minimalni pocet, takze to chapu pro INSERT bez stepeni.

Aha, tak to ja to chapu obracene. Kdyz se me zepta kolik budu minimalne potrebovat stranek pro insert, tak reknu tolik, kolik mi bude opravdu vzdycky stacit...

Neni ale na otazku "Kolik bufferu mi bude vzdy stacit pro INSERT?" odpoved 2h+1 bufferu? (h (nacteni smerem dolu) + h (stepeni na kazde urovni smerem nahoru) + 1 (vytvoreni noveho korene))

[Trupik]

Neni ale na otazku "Kolik bufferu mi bude vzdy stacit pro INSERT?" odpoved 2h+1 bufferu? (h (nacteni smerem dolu) + h (stepeni na kazde urovni smerem nahoru) + 1 (vytvoreni noveho korene))

Ale buffery, které potřebuješ na štěpení na nižších úrovních můžeš po štěpení hned zapsat na disk a použít znova při dalším štěpení, nebo ne? (nejsem žádnej OZD bossman, ale myslim, že jo)

[twoflower]

Neni ale na otazku "Kolik bufferu mi bude vzdy stacit pro INSERT?" odpoved 2h+1 bufferu? (h (nacteni smerem dolu) + h (stepeni na kazde urovni smerem nahoru) + 1 (vytvoreni noveho korene))

Ale buffery, které potřebuješ na štěpení na nižších úrovních můžeš po štěpení hned zapsat na disk a použít znova při dalším štěpení, nebo ne? (nejsem žádnej OZD bossman, ale myslim, že jo)

Pravda

[twoflower]

Vite nekdo, jak by se u tohoto stromu resilo tohle?

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?

Budu potrebovat 3 READ operace, to je 3*(s + r + btt) (pocitam, ze ta data mohou byt na ruznych cylindrech) a 5 WRITE operaci (resp. 3x REWRITE a 2x INSERT). Nejsem si uplne jisty, ale podle mne by techto 5 WRITE operaci melo trvat 2r + btt (to je rewrite stranky, kterou jsem jako posledni precetl, tj. te nejspodnejsi) + 4*(s + r + btt).

Je to dobre?

[Tuetschek]

Vite nekdo, jak by se u tohoto stromu resilo tohle?

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?

Budu potrebovat 3 READ operace, to je 3*(s + r + btt) (pocitam, ze ta data mohou byt na ruznych cylindrech) a 5 WRITE operaci (resp. 3x REWRITE a 2x INSERT). Nejsem si uplne jisty, ale podle mne by techto 5 WRITE operaci melo trvat 2r + btt (to je rewrite stranky, kterou jsem jako posledni precetl, tj. te nejspodnejsi) + 4*(s + r + btt).

Je to dobre?

Podle me ne tak docela -- REWRITE muzes pouzit jen za predpokladu ze se s hlavickami disku nehybalo -- tedy jen pokud pises na uplne stejne misto odkud jsi cetl. No a ty stranky musis nacist v poradi koren -> 1. uroven -> 2.uroven (proste NEJDRIV nacist VSECHNY 3 urovne) a potom teprve delat nejaky stepeni a zapisy -- takze REWRITE muzes pouzit jen 1x na naposledy prectenou uroven a pak zapsat zbytek normalnim INSERTEM, tedy:

3(s+r+btt) + 2r + 4(s+r+btt) = 103.2ms

[twoflower]

Vite nekdo, jak by se u tohoto stromu resilo tohle?

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?

Budu potrebovat 3 READ operace, to je 3*(s + r + btt) (pocitam, ze ta data mohou byt na ruznych cylindrech) a 5 WRITE operaci (resp. 3x REWRITE a 2x INSERT). Nejsem si uplne jisty, ale podle mne by techto 5 WRITE operaci melo trvat 2r + btt (to je rewrite stranky, kterou jsem jako posledni precetl, tj. te nejspodnejsi) + 4*(s + r + btt).

Je to dobre?

Podle me ne tak docela -- REWRITE muzes pouzit jen za predpokladu ze se s hlavickami disku nehybalo -- tedy jen pokud pises na uplne stejne misto odkud jsi cetl. No a ty stranky musis nacist v poradi koren -> 1. uroven -> 2.uroven (proste NEJDRIV nacist VSECHNY 3 urovne) a potom teprve delat nejaky stepeni a zapisy -- takze REWRITE muzes pouzit jen 1x na naposledy prectenou uroven a pak zapsat zbytek normalnim INSERTEM, tedy:

3(s+r+btt) + 2r + 4(s+r+btt) = 103.2ms

V podstate si rozumime - REWRITEm jsem nazval vsechny prepisy, ale shodneme se v tom, ze jen u te posledni nactene stranku usetrim seek time. Jedine, cemu jeste nerozumim, proc nepocitas btt na ten jeden "rychly" REWRITE (tzn. proc tam mas jen 2r a ne 2r + btt). Vzdyt nejdriv se mi disk otoci na zacatek bloku (to je 2r) a pak jeste musim ten blok zapsat, takze + btt, nebo ne?

[Tuetschek]

V podstate si rozumime - REWRITEm jsem nazval vsechny prepisy, ale shodneme se v tom, ze jen u te posledni nactene stranku usetrim seek time. Jedine, cemu jeste nerozumim, proc nepocitas btt na ten jeden "rychly" REWRITE (tzn. proc tam mas jen 2r a ne 2r + btt). Vzdyt nejdriv se mi disk otoci na zacatek bloku (to je 2r) a pak jeste musim ten blok zapsat, takze + btt, nebo ne?

Jo aha ... promin ... asi jsem to necetl dost detailne. S tou operaci REWRITE nam ten cas rikali na cvikach a myslim ze je to tak i ve skriptech. Ja myslim ze je to tim, ze kdyz ten blok poprve nacitas, disk uz se zaroven otaci, takze vlastne spotrebujes (s + r) + (2r + btt), takze oproti jenom nacteni o 2r navic.