Cviceni 2

• umožňuje rychlé nalezení ID
• I/O = I(A,R)
• pro přístup k datům musíme do datových bloků (I(A,R)+1)

• I/O stejné jako B-strom, ale data jsou v blocích za sebou

• data jsou fyzicky setříděná
• data jsou přímo ve stromu (nemusíme do datových bloků)

• průměrná délka pro řádek relace EMP = 60B
• průměrná délka pro řádek relace DEPT = 100B

EMP:

• RowAvg = 60B
• Br (blokovací faktor) = 60 ~ (4096 - 300) * 0,9 / 60
• Nr (počet řádek) = 30 000
• Pr (počet stránek pro uložení relace) = 30 000 / 60 ~ 500
• V(DEPTNO, EMP) = 100
• V(EMPNO, EMP) = 30000
• Max(EMPNO,EMP)=30000, MIN(EMP,EMPNO)=1
• Index nad EMPNO:
• Bi ~ 150 … max. mozna arita B+ stromu
• Fi (počet větvení ve vnitřním bloku indexu) … tato hodnota rozhodně nemůže být větší než Bi. V praxi bývá v rozmezí (50 - 100)% Bi.
• Pro náš příklad položme Fi = 100.
• I(EMP,EMPNO) (hloubka stromu) ~ log(Nr)/log(Fi) ~ log(30 000) / log(100) = 4.47/2 ~ 5/2 ~ 3

DEPT:

• RowAvg = 100B
• Bdept ~ 40
• Ndept = 100
• Pdept = 100 / 40 ~ 3
• Index nad DEPTNO: Fi = 100
• I(DEPT, DEPTNO) ~ log(100) / log(100) = 2/2 = 1

• FULL TABLE SCAN: I/O = Pemp = 500
• INDEX: I/O = I(EMP, EMPNO) + 1 = 3 + 1 = 4
  • průchod stromem indexu + načtení odkazovaného datového bloku

• FULL TABLE SCAN: I/O = Pemp = 500
• INDEX:
  • I/O = I(EMP, EMPNO) + [(MAX(EMPNO)-hranice)/Bemp]+(MAX(EMPNO)-hranice)
  • I/O = 3+(30000-150)/150+(30000-150)=3+29850/150+29850=3+199+29850= 30052
  • cesta dolu indexem + cesta doprava listovými uzly + jednotlivé návštěvy datových bloků; každý index může odkazovat na jiný datový blok → musím načítat datový blok pro každý index
• CLUSTER INDEX:
  • I/O = I(EMP, EMPNO) + [(MAX(EMPNO)-hranice)/Bemp]+[(MAX(EMPNO)-hranice)/Bemp]
  • I/O = 3 + [(30000-150)/150] + [(30000-150)/150] = 3 + 199 + 29850/60 = 202 + 498 ~ 700 > 500
  • datové řádky sousedních klíčů jsou vedle sebe v datových blocích, datové bloky však řazené nejsou → je třeba načítat všechny klíče
• INDEX ORGANISED TABLE:
  • I/O = I(EMP, EMPNO) + [(MAX(EMPNO)-hranice)/Bemp]
  • I/O = 3 + [(30000-150)/150] = 3 + 199 = 202
  • nejdeme do datových bloků, data jsou přímo ve stromě

• FULL TABLE SCAN: I/O = Pemp = 500
• INDEX:
  • I/O = I(EMP, EMPNO) + [(hranice - MIN(EMPNO))/Bi]+( hranice - MIN(EMPNO)
  • I/O = 3+(150)/150+(150)=3+1+150= 153 < 500
  • cesta dolu indexem + cesta doleva listovými uzly + jednotlivé návštěvy datových bloků
• CLUSTER INDEX:
  • I/O = 3+ 1 + [150/Bemp] = 3+1+150/60 ~ 7 < 500

• S*R, platí S<R
• množství paměti M=3 (minimum)
• jedna buňka pro R, jedna pro výstup, zbytek (N) pro menší relaci - S
• I/O = P_S + (P_S/N)*P_R
• Vylepšení ZIK-ZAK: P_S + (P_S/N)*P_R - (P_S/N)-1]

• M=3: I/O = P_dept + P_dept*P_emp = 3 + 3*500 = 1503 (1501)
• M=4: I/O = Pdept + (Pdept/2)*Pemp = 3 + 2*500 = 1003 (1002)
• …

• N = stranek v relaci, B = velikost pameti (bufferu)
• SORT:
  • I/O = 2 * N * [log_B-1(N)+1]
  • (načtení stránek + zapsání stránek) * počet kroku
• MERGE:
  • I/O = N1+N2
  • slití relací
• TOTAL:
  • I/O = SORT(N1)+SORT(N2) +N1 +N2