Buffery/IO operace v B-stromech
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Buffery/IO operace v B-stromech
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.
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
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
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.
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
- Donátor
- Příspěvky: 178
- Registrován: 22. 9. 2004 00:13
- Typ studia: Informatika Bc.
- Bydliště: The city of Dobříš
- Kontaktovat uživatele:
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...
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...
Naposledy upravil(a) MyS dne 7. 1. 2007 13:42, celkem upraveno 1 x.
We don't need no education!
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re: Buffery/IO operace v B-stromech
Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?twoflower píše:
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.
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: Buffery/IO operace v B-stromech
To urcite jo, ale tady slo prave o minimalni pocet, takze to chapu pro INSERT bez stepeni.Trupik píše:Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?twoflower píše:
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.
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re: Buffery/IO operace v B-stromech
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 píše:To urcite jo, ale tady slo prave o minimalni pocet, takze to chapu pro INSERT bez stepeni.Trupik píše:Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?twoflower píše:
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.
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: Buffery/IO operace v B-stromech
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 píše: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 píše:To urcite jo, ale tady slo prave o minimalni pocet, takze to chapu pro INSERT bez stepeni.Trupik píše: Nemuze to byt kvuli tomu, ze se pri insertu muze zvetsit o jedna vyska stromu?
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re: Buffery/IO operace v B-stromech
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)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))
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: Buffery/IO operace v B-stromech
PravdaTrupik píše: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)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))
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
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?
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
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
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:twoflower píše: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?
3(s+r+btt) + 2r + 4(s+r+btt) = 103.2ms
Plug 'n' Pray.
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
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 píše: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:twoflower píše: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?
3(s+r+btt) + 2r + 4(s+r+btt) = 103.2ms
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
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.twoflower píše: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?
Plug 'n' Pray.