Indexering i databas med hashfunktion

Hej!

Jag har en uppgift i min databasteknikskurs som jag inte förstår hur jag ska lösa.
Jag utlyser inte en lösning här utan mer var jag kan hitta information om tillvägagångssätt för lösning av uppgiften. Anledningen till detta är att varken föreläsningar eller kurslitteraturen tar upp en algoritm för lösning av den här typen av problem.

Uppgiften är Upg3 i indexering på länken:
http://www.csc.kth.se/utbildning/kth...suppgifter.pdf

Tack på förhand!

hmm? Topic är lite missledande till uppgiften samt så skriver du konstig.

Menar du "Uppgiften har index 3 i länken"?
Varför inte bara säga uppgift 3?

Till uppgiften, den verkar inte alls komplicerad och är i samma klass som de andra uppgifterna.

Sökförslag:
http://lmgtfy.com/?q=database+design
http://lmgtfy.com/?q=database+modelling

Jag tror du har missuppfattat det hela lite. Länken består av olika avsnitt t.ex. normalisering, indexering osv. Upg3 finns i de flesta avsnitten, därav skriver jag inte bara upg3.

För att förtydliga. I avsnittet om indexering på sida 17 i pdf:en finns upg3 som jag behöver hjälp med

Är lite osäker faktiskt, det var ett tag sedan.
Antagligen så får "hinkarna"(gissar på logisk strukturobjekt typ Oracle's extent) antagligen ha block som ej är fulla eller en "hink" ha få block som innehåller poster.

2 468 357 poster / 25.5 poster per datablock, vi inte får använda samma datablock så får vi lite overhead, och behöver allokera ytterligare block för "överspillet".

(2468357 mod 25.5)*313 = 2504 totalt datablock med "overflow" (halva poster som inte kan återanvända samma diskblock i bucketen) optimalt.

2468357/25=98734.28 ~ 98735 "hela" datablock behövs också.

2504+98735=101239 i totalt antal "hela" datablock + overflow datablock.

101239/313=324 datablocks per bucket.


324*25.5 = 8262 poster per bucket.

8262*313 = 2586006 (plats för detta antalet poster, i de allokerade datablocken i alla buckets)

2586006-2468357 = 117649 poster.

117649/25.5=4613 datablock "extra" allokeras.


Optimalt skulle vi behöva läsa 101239 -98735=2504 extra datablock för att läsa alla poster (med överspill och optimalt allokerat) ... worst case ger att vi istället måste läsa
(324*313) - 98735=2677 datablock för att täcka in hela overflowdatablock. Det är en skillnad på 173 datablock reads mellan optimalt och worst case.

Sen har det ju att göra med blockstorleken på filsystemet osv. hur mycket extra disk i/o som faktiskt
genereras optimalt vs. worst case.

men 173 datablock * 8k block size ger 173 * 8 192 = 1 417 216, en dryg megabyte i extra läsning worst case. Körs queryn 2000 gånger om dagen kan du räkna själv hur mycket waste det blir.



Ja ungefär nåt sånt.