Bplus

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

B+ index je dinamičen. Njegova struktura se dinamično prilagaja spremembam v osnovni datoteki B+ drevo predstavlja iskalno strukturo. To je uravnoteženo drevo, katerega vozlišča usmerjajo iskanje, listi pa vsebujejo podatke (ključe). Listi v B+ drevesu so povezani v dvosmerni urejen seznam strani.

Bplus1.png

Vsebina

Lastnosti B+ drevesa

  • Operacije vstavljanja/brisanja (insert, delete) ohranjajo drevo uravnoteženo,
  • Vozlišča (razen root-a) morajo biti vsaj 50% zasedena,
  • Iskanje določene vrednosti zahteva le pot od root vozlišča do ustreznega listnega vozlišča. Poti do vseh vozlišč so zaradi uravnoteženosti enake in določajo višino drevesa.
  • Vsako vozlišče B+ drevesa vsebuje m vpisov; d=<m=<2d
  • d je parameter B+ drevesa (red drevesa) in predstavlja kapaciteto vozlišča. Edina izjema je korensko vozlišče, za katerega velja 1=<m=<3d
  • Lastnosti B+ dreves si poglejmo skozi uporabo operacij iskanja, vstavljanja in brisanja. Predpostavili bomo, da v osnovni datoteki ni duplikatov. Primer našega B+ indeksa prikazuje slika (d=2)

Iskanje

Algoritem išče list, v katerem se nahaja iskalni ključ Če iščemo vrednost 5, sledimo levemu kazalcu, ker je 5 < 13 Pri iskanju 14 ali 15 sledimo 2. kazalcu. Vrednosti 15 v listu ne najde, zato iskanje ne uspe

Vstavljanje

Algoritem za vstavljanje poišče list, v katerega spada nova vrednost in jo vanj vstavi, če to dopušča zasedenost lista Lahko je potrebno opraviti distribucijo ali razcepljanje strani

Vstavljanje vrednosti 8 z uporabo razcepljanja

Bplus1.png

Bplus2.png

Bplus3.png

Vstavljanje vrednosti 8 z uporabo redistribucije

Bplus1.png

Bplus4.png

Brisanje

  • Algoritem za brisanje poišče list, kjer je podatek za brisanje in ga odstrani iz drevesa
  • Lahko se zgodi, da se zasedenost vozlišča po brisanju zniža pod dovoljeno mejo (50%)
  • V tem primeru je potrebno uporabiti redistribucijo ali pa zlivanje dveh vozlišč v eno (v tem primeru posodobiti tudi prednike)


Brisanje ključev 19 in 20 z uporabo redistribucije:

Bplus3.png

Bplus5.png

Duplikati

  • Lahko se poslužujemo overflow strani, kot v ISAM
  • Lahko jih vstavljamo “normalno”, potrebno pa je spremeniti algoritem iskanja tako, da bo vedno poiskal “najbolj levi element” z iskano vrednostjo ključa
  • Uporaba podatkovni vpis je par <k, rid-list> je najbolj naravna v tem primeru

Zunanje povezave

Vzpostavljeno iz »http://www.e-studij.si/Bplus«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja