Omslaget. Klicka här för att gå till bokens hemsida.

Databasteknik: Svar till övningar - kapitel 22, övning 1, Diskblock på 1024 byte

(a) en heap, dvs en osorterad fil, utan index

Storleken på ett diskblock är 1 kilobyte, dvs 1024 byte. Det gäller både för data- och indexblock. Att läsa ett godtyckligt block tar i genomsnitt 5 millisekunder. Att läsa block som ligger i följd på disken tar 1 millisekund.

En datapost är 70 tecken. Blockningsfaktorn bfr för datablocken blir 1024 / 70, dvs 14. Det går alltså in 14 dataposter i ett datablock.

Tabellen innehåller 9 miljoner poster, vilket betyder att huvudfilen upptar 642857 block. Om vi antar att det sökta personnumret finns i tabellen, och vi vet att personnummerfältet är en nyckel, räcker det i genomsnitt med att läsa hälften av blocken, 321428 stycken. Om de ligger i följd på disken tar det 1 ms att läsa varje block, vilket ger en genomsnittlig tid för frågan på 321 sekunder, eller drygt 5 minuter. (Men i värsta fall tar det 643 sekunder, eller nästan 11 minuter.)

Eftersom varje block bara är en åttondel så stort som i exemplet i boken, blir det ungefär åtta gånger fler block att läsa, vilket tar åtta gånger längre tid. Det här är dock inte helt realistiskt, eftersom det kommer att gå fortare att läsa dessa mindre block, och i verkligheten blir det förmodligen inte så stor skillnad.

(b) en hashtabell, organiserad på Personnummer

Vi kan fortfarande hitta en post med ett visst värde på Personnummer genom att beräkna hashfunktionen för det givna personnumret, och värdet på hashfunktionen är fortfarande numret på den position i hashtabellen där posten finns. Vi läser in det diskblock i tabellen som ligger på den positionen, vilket tar i genomsnitt 5 millisekunder, dvs en halv hundradels sekund, så hela frågan tar alltså så lång tid att köra.

Det blir alltså ingen förändirng jämfört med bokens åtta gånger större diskblock. (Så länge vi inte har spillblock i den tabellpositionen.)

(c) ett primärindex i form av ett B+-träd, organiserat på Personnummer

Ett personnummer tar upp 11 byte, och en diskblockspekare 4 byte. Ordningen på B-trädet blir (1024 - 4) / (4 + 11) + 1, dvs 69. Den "effektiva ordningen" av B-trädet blir 46. Vi räknar alltså med att varje indexnod innehåller pekare till 46 indexnoder eller datablock.

Blockningsfaktorn för datablocken är ju, som vi räknade ut ovan, 14. Det finns plats för 14 dataposter i ett datablock. Men om huvudfilen, dvs datablocken, har byggst upp med hjälp av B+ -trädsindexet, så att vi använt indexet för att bestämma i vilket datablock en post ska placeras, så gäller samma resonemang som för indexblocken. Datablocken delas också i två när de blir fulla, och kommer därför i genomsnitt att vara två tredjedels fulla. Den "effektiva blockningsfaktorn" blir två tredjedelar av 14, dvs 9. Alltså har vi 1000000 datablock.

Den effektiva ordningen på trädet är 46, så för att peka ut de 1000000 datablocken behövs 21739 indexblock på den lägsta indexnivån. På nästa nivå i indexet behövs 473 indexblock, och på nästa 10. Sedan krävs en rotnod för att binda ihop dessa 10 indexnoder. Indexet får alltså 4 nivåer. För att hitta en datapost baserat på dess personnummer behövs det fem läsningar från disken: fyra indexblock och sen det utpekade datablocket. Eftersom läsning av ett block tar i genomsnitt 5 millisekunder, kan vi räkna med att hela SQL-frågan tar 25 millisekunder att köra, dvs 0.025 sekunder. Det är 10 millisekunder längre än i bokens exempel med de större diskblocken.

Sammanfattning

Lagringsstruktur Blockstorlek 8192 byte Blockstorlek 1024 byte Skillnad
Heap 38 sekunder 5 minuter 8 gånger längre tid
Hashtabell 0.005 sekunder 0.005 minuter Ingen skillnad
Klustrat B+-index 0.015 sekunder 0.025 minuter 0.010 sekunder längre tid


Av Thomas Padron-McCarthy (e-post: boken@databasteknik.se)
Senaste ändring: 30 juli 2005