Własności B*-drzewa

• Zrównoważone - maksymalna różnica poziomów liści =1

• Liście tworzą listę dwukierunkową

• Średnie wypełnienie węzłów = 3/4

• Nie przechowuje wartości pustych

• Porównanie kosztu wyszukania danych przez przeglądnięcie liniowe i za pomocą indeksu:

  • select * from pracownicy where id=3485;

Dane:

• średnia wielkość rekordu - 512B

• liczba rekordów - 10.000

• wielkość bloku dyskowego - 2KB

• wielkość klucza indeksu - 10B

• wielkość ROWID - 8B

• średnie wypełnienie węzłów = 3/4

Przeglądanie liniowe:

k=lr*śwr/wbd=10000*512B/2KB=2500 I/O

Indeks:

średni rząd drzewa=(śww*wbd-wROWID)/

=(wki+wROWID)=

=(3/4*2KB-8B)/(10B+8B)=85

max wysokość drzewa = log śrd lr=

=log 85 10000 = 3

k = mwd +1 I/O = 3+1 = 4 I/0

Poprzedni slajd

Następny slajd

Cofnij do pierwszego slajdu

Podgląd wersji graficznej