B+ Tree er en udvidelse af B Tree, som tillader effektiv indsættelse, sletning og søgeoperationer.
I B Tree kan nøgler og poster både gemmes i de interne såvel som bladknuder. Hvorimod poster (data) i B+ træ kun kan gemmes på bladknuderne, mens interne knudepunkter kun kan gemme nøgleværdierne.
Bladknuderne i et B+-træ er kædet sammen i form af en enkelt-linket liste for at gøre søgeforespørgslerne mere effektive.
B+ Tree bruges til at gemme den store mængde data, som ikke kan gemmes i hovedhukommelsen. På grund af det faktum, at størrelsen af hovedhukommelsen altid er begrænset, lagres de interne noder (nøgler til at få adgang til poster) i B+-træet i hovedhukommelsen, hvorimod bladknudepunkter er lagret i den sekundære hukommelse.
De interne knudepunkter i B+-træet kaldes ofte indeksnoder. Et B+ træ af størrelsesorden 3 er vist i den følgende figur.
Fordele ved B+ Tree
- Records kan hentes i samme antal diskadgange.
- Træets højde forbliver afbalanceret og mindre sammenlignet med B-træet.
- Vi kan få adgang til de data, der er gemt i et B+ træ sekventielt såvel som direkte.
- Nøgler bruges til indeksering.
- Hurtigere søgeforespørgsler, da dataene kun gemmes på bladknuderne.
B Træ VS B+ Træ
| SN | B Træ | B+ træ |
|---|---|---|
| 1 | Søgetaster kan ikke gemmes gentagne gange. | Redundante søgenøgler kan være til stede. |
| 2 | Data kan lagres i bladknuder såvel som interne knudepunkter | Data kan kun gemmes på bladknuderne. |
| 3 | At søge efter nogle data er en langsommere proces, da data kan findes på interne noder såvel som på bladknuderne. | Søgning er forholdsvis hurtigere, da data kun kan findes på bladknuderne. |
| 4 | Sletning af interne noder er så kompliceret og tidskrævende. | Sletning vil aldrig være en kompleks proces, da element altid vil blive slettet fra bladknuderne. |
| 5 | Bladknuder kan ikke kædes sammen. | Bladknuder er knyttet sammen for at gøre søgeoperationerne mere effektive. |
Indsættelse i B+ træ
Trin 1: Indsæt den nye node som en bladknude
java værdi af streng
Trin 2: Hvis bladet ikke har påkrævet plads, skal du opdele noden og kopiere den midterste node til den næste indeksnode.
Trin 3: Hvis indeksnoden ikke har den nødvendige plads, skal du opdele noden og kopiere det midterste element til næste indeksside.
Eksempel:
Indsæt værdien 195 i B+ træet af orden 5 vist i den følgende figur.
195 vil blive indsat i det højre undertræ af 120 efter 190. Indsæt det på den ønskede position.
Noden indeholder mere end det maksimale antal elementer, dvs. 4, opdel den derfor og placer median noden op til forælderen.
Nu indeholder indeksnoden 6 børn og 5 nøgler, hvilket overtræder B+ træets egenskaber, derfor skal vi opdele det, vist som følger.
Sletning i B+ træ
Trin 1: Slet nøglen og data fra bladene.
Trin 2: hvis bladknuden indeholder mindre end minimumsantallet af elementer, skal du flette knudepunktet ned med dens søskende og slette nøglen mellem dem.
Trin 3: hvis indeksnoden indeholder mindre end minimumsantallet af elementer, skal du flette noden med søskende og flytte tasten ned imellem dem.
Eksempel
Slet nøglen 200 fra B+ træet vist i den følgende figur.
200 er til stede i det højre undertræ af 190, efter 195. slet det.
Flet de to noder sammen ved at bruge 195, 190, 154 og 129.
Nu er element 120 det enkelte element, der er til stede i knudepunktet, som krænker B+-træets egenskaber. Derfor skal vi flette det ved at bruge 60, 78, 108 og 120.
Nu vil højden af B+ træ blive reduceret med 1.
