B+ Tree je proširenje B Tree-a koje omogućuje učinkovite operacije umetanja, brisanja i pretraživanja.
U stablu B, ključevi i zapisi mogu se pohraniti u interne kao iu lisne čvorove. Dok, u B+ stablu, zapisi (podaci) mogu biti pohranjeni samo na lisnim čvorovima, dok unutarnji čvorovi mogu pohraniti samo ključne vrijednosti.
c++ int u niz
Lisni čvorovi B+ stabla međusobno su povezani u obliku jednostruko povezanih popisa kako bi upiti za pretraživanje bili učinkovitiji.
B+ Tree se koriste za pohranu velike količine podataka koji se ne mogu pohraniti u glavnu memoriju. Zbog činjenice da je veličina glavne memorije uvijek ograničena, interni čvorovi (ključevi za pristup zapisima) B+ stabla pohranjeni su u glavnoj memoriji, dok su lisni čvorovi pohranjeni u sekundarnoj memoriji.
Interni čvorovi B+ stabla često se nazivaju indeksni čvorovi. B+ stablo reda 3 prikazano je na sljedećoj slici.
Prednosti B+ stabla
- Zapisi se mogu dohvatiti u jednakom broju pristupa disku.
- Visina stabla ostaje uravnotežena i manja u usporedbi s B stablom.
- Podacima pohranjenima u B+ stablu možemo pristupiti sekvencijalno kao i izravno.
- Ključevi se koriste za indeksiranje.
- Brži upiti za pretraživanje jer se podaci pohranjuju samo na lisnim čvorovima.
B stablo VS B+ stablo
| S N | B Drvo | B+ Drvo |
|---|---|---|
| 1 | Ključevi za pretraživanje ne mogu se više puta pohraniti. | Mogu biti prisutni suvišni ključevi za pretraživanje. |
| 2 | Podaci se mogu pohraniti u lisne čvorove kao i unutarnje čvorove | Podaci se mogu pohraniti samo na listovima čvorova. |
| 3 | Traženje nekih podataka sporiji je proces budući da se podaci mogu pronaći na unutarnjim čvorovima kao i na čvorovima lista. | Pretraživanje je relativno brže jer se podaci mogu pronaći samo na lisnim čvorovima. |
| 4 | Brisanje unutarnjih čvorova je tako komplicirano i dugotrajno. | Brisanje nikada neće biti složen proces jer će element uvijek biti izbrisan iz lisnih čvorova. |
| 5 | Listni čvorovi ne mogu se međusobno povezati. | Lisni čvorovi međusobno su povezani kako bi operacije pretraživanja bile učinkovitije. |
Umetanje u B+ stablo
Korak 1: Umetnite novi čvor kao listni čvor
Korak 2: Ako list nema potreban prostor, podijelite čvor i kopirajte srednji čvor u sljedeći indeksni čvor.
Korak 3: Ako čvor indeksa nema potreban prostor, podijelite čvor i kopirajte srednji element na sljedeću stranicu indeksa.
Primjer :
Umetnite vrijednost 195 u B+ stablo reda 5 prikazano na sljedećoj slici.
195 će biti umetnuto u desno podstablo od 120 nakon 190. Umetnite ga na željenu poziciju.
Čvor sadrži više od maksimalnog broja elemenata, tj. 4, stoga ga podijelite i postavite srednji čvor do roditelja.
algoritam dubina prvo pretraživanje
Sada, indeksni čvor sadrži 6 djece i 5 ključeva što krši svojstva B+ stabla, stoga ga moramo podijeliti, prikazano na sljedeći način.
Brisanje u B+ stablu
Korak 1: Izbrišite ključ i podatke s listova.
Korak 2: ako lisni čvor sadrži manje od minimalnog broja elemenata, spojite čvor sa svojim bratom i izbrišite ključ između njih.
Korak 3: ako indeksni čvor sadrži manje od minimalnog broja elemenata, spojite čvor sa srodnim i pomaknite dolje ključ između njih.
Primjer
Izbrišite ključ 200 iz B+ stabla prikazanog na sljedećoj slici.
200 je prisutan u desnom podstablu od 190, nakon 195. izbrišite ga.
Spojite dva čvora koristeći 195, 190, 154 i 129.
Sada je element 120 jedini element prisutan u čvoru koji krši svojstva B+ stabla. Stoga ga trebamo spojiti pomoću 60, 78, 108 i 120.
Sada će se visina B+ stabla smanjiti za 1.
