|
|
| (Egy közbenső módosítás, amit egy másik szerkesztő végzett, nincs mutatva) |
| 42. sor: |
42. sor: |
|
| |
|
| '''5. Egy 10 000 000 rekordból álló állományt szeretnénk''' B* '''fa szervezéssel tárolni. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell. Legalább hány blokkra van szükség? Mennyi az átlagos rekordelérési idő, ha a memóriában egy blokk fér el?''' | | '''5. Egy 10 000 000 rekordból álló állományt szeretnénk''' B* '''fa szervezéssel tárolni. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell. Legalább hány blokkra van szükség? Mennyi az átlagos rekordelérési idő, ha a memóriában egy blokk fér el?''' |
| | | [[Media:AB_gyakfeladat_5_mo.pdf | Megoldás]] |
| 850 byte / rekord és 4000 byte / blokk, <math> \lfloor 4000/850 \rfloor = 4 </math> rekord / blokk → <math> \lceil 10000000/4 \rceil = 2500000 </math> blokk kell az adatoknak.
| |
| | |
| Egy indexstruktúra 50 + 18 = 68 byte, <math> \lfloor 4000/68 \rfloor = 58 </math> index / blokk → <math> \lceil 10000000/58 \rceil = 172414 </math> blokk a sűrű indexeknek.
| |
| | |
| 172414 ritka index bejegyzés, ennyi levele van a B*-fának, ennek tárolásához <math> \lceil 172414/58 \rceil = 2973 </math> blokk kell. A fa korábbi szintjeihez <math> \lceil 2973/58 \rceil = 52 </math> és <math> \lceil 52/58 \rceil = 1 </math> blokk kell. Ha a blokkok számára nem lenne szükség, a fa szintjeinek számát logaritmussal is megkaphatjuk: <math> \lceil \log_{58} 2973 \rceil + 1 = 3 </math>.
| |
| | |
| <math> 2500000 + 172414 + 2973 + 52 + 1 = 2675440 </math> blokk szükséges összesen a teljes struktúra tárolásához. Az átlagos blokkelérési idő a B*-fa bejárása a gyökértől egy levélig, a sűrű index olvasása és az adatblokk olvasása: <math> 3 + 1 + 1 = 5 </math> blokkművelet.
| |
| | |
| -- [[VargaNikolett|csacsiga]] - 2008.12.02.
| |
| -- [[OcsvariAdam|ocsi]] - 2009.11.11.
| |
| | |
| A megoldás szerintem rossz. 59 index/blokk van, mival a B*-fában szokás k-1 kulcsot tárolni k mutatóhoz (könyv). 58*68=3944 bájt, így még a 18 bájtos mutatónak ott a hely. Innentől ugyanúgy kell számolni, csak 59-cel.
| |
| -- [[BartokFerenc|Fonok]] - 2012.01.10.
| |
|
| |
|
| '''6. Gondolkodtató kérdések''' | | '''6. Gondolkodtató kérdések''' |