Før du forstår B tre og B+ tre forskjeller, bør vi kjenne B-treet og B+-treet separat.
Hva er B-treet?
B tre er et selvbalanserende tre, og det er et m-veis tre hvor m definerer rekkefølgen på treet. Btree er en generalisering av Binært søketre der en node kan ha mer enn én nøkkel og mer enn to barn avhengig av verdien av m . I B-treet er dataene spesifisert i en sortert rekkefølge med lavere verdier på venstre undertre og høyere verdier i høyre undertre.
hvor mange millioner er det i en milliard
Egenskaper til B-tre
Følgende er egenskapene til B-treet:
- I B-treet må alle bladnodene være på samme nivå, mens i tilfelle av et binært tre kan bladnodene være på forskjellige nivåer.
La oss forstå denne egenskapen gjennom et eksempel.
I treet ovenfor er ikke alle bladnodene på samme nivå, men de har de ytterste to barna. Derfor kan vi si at treet ovenfor er en binært tre men ikke et B-tre.
- Hvis Btreet har en rekkefølge på m, kan hver node ha maksimalt m Ved minimumsbarn har bladnodene null barn, rotnoden har to barn, og de interne nodene har et tak på m/2.
- Hver node kan ha maksimale (m-1) nøkler. For eksempel, hvis verdien av m er 5, er den maksimale verdien av nøkler 4.
- Rotnoden har minimum én nøkkel, mens alle de andre nodene unntatt rotnoden har (tak på m/2 minus - 1) minimumsnøkler.
- Hvis vi utfører innsetting i B-treet, blir noden alltid satt inn i bladnoden.
Anta at vi ønsker å lage et B-tre av orden 3 ved å sette inn verdier fra 1 til 10.
Trinn 1: Først lager vi en node med 1 verdi som vist nedenfor:
Steg 2: Det neste elementet er 2, som kommer etter 1 som vist nedenfor:
Trinn 3: Det neste elementet er 3, og det settes inn etter 2 som vist nedenfor:
Ettersom vi vet at hver node kan ha maksimalt 2 nøkler, vil vi dele denne noden gjennom midtelementet. Det midterste elementet er 2, så det flytter til sin overordnede. Noden 2 har ingen forelder, så den blir rotnoden som vist nedenfor:
Trinn 4: Det neste elementet er 4. Siden 4 er større enn 2 og 3, vil det bli lagt til etter 3 som vist nedenfor:
Trinn 5: Det neste elementet er 5. Siden 5 er større enn 2, 3 og 4, vil det bli lagt til etter 4 som vist nedenfor:
Ettersom vi vet at hver node kan ha maksimalt 2 nøkler, vil vi dele denne noden gjennom midtelementet. Det midterste elementet er 4, så det flytter til sin overordnede. Forelderen er node 2; derfor vil 4 bli lagt til etter 2 som vist nedenfor:
Trinn 6: Det neste elementet er 6. Siden 6 er større enn 2, 4 og 5, vil 6 komme etter 5 som vist nedenfor:
Trinn 7: Det neste elementet er 7. Siden 7 er større enn 2, 4, 5 og 6, vil 7 komme etter 6 som vist nedenfor:
Ettersom vi vet at hver node kan ha maksimalt 2 nøkler, vil vi dele denne noden gjennom midtelementet. Det midterste elementet er 6, så det flyttes til det overordnede elementet som vist nedenfor:
Men 6 kan ikke legges til etter 4 fordi noden kan ha maksimalt 2 nøkler, så vi deler denne noden gjennom midtelementet. Det midterste elementet er 4, så det flytter til sin overordnede. Siden node 4 ikke har noen forelder, vil node 4 bli en rotnode som vist nedenfor:
Hva er et B+-tre?
De B+ tre er også kjent som et avansert selvbalansert tre fordi hver vei fra roten til treet til bladet på treet har samme lengde. Her betyr samme lengde at alle bladnodene opptrer på samme nivå. Det vil ikke skje at noen av bladnodene oppstår på tredje nivå og noen av dem på andre nivå.
En B+-treindeks betraktes som en indeks på flere nivåer, men B+-trestrukturen ligner ikke på sekvensielle filer med flere nivåer.
Hvorfor brukes B+-treet?
Et B+-tre brukes til å lagre postene veldig effektivt ved å lagre postene på en indeksert måte ved å bruke den B+-treeindekserte strukturen. På grunn av indeksering på flere nivåer, blir datatilgangen raskere og enklere.
B+ tre Nodestruktur
Nodestrukturen til B+-treet inneholder pekere og nøkkelverdier vist i figuren nedenfor:
Som vi kan observere i B+ trenodestrukturen ovenfor at den inneholder n-1 nøkkelverdier (k1til kn-1) og n pekere (s1til sn).
Søketøkkelverdiene som er plassert i noden holdes i sortert rekkefølge. Så hvis jeg
Begrensning på ulike typer noder
La 'b' være rekkefølgen til B+-treet.
Node uten blader
linux kjøre kommando
La 'm' representere antall barn til en node, så kan forholdet mellom rekkefølgen til treet og antall barn representeres som:
La k representerer søkenøkkelverdiene. Forholdet mellom rekkefølgen til treet og søkenøkkelen kan representeres som:
Siden vi vet at antall pekere er lik søkenøkkelverdiene pluss 1, så matematisk kan det skrives som:
Antall pekere (eller barn) = Antall søketaster + 1
Derfor vil maksimalt antall pekere være 'b', og minimum antall pekere vil være takfunksjonen til b/2.
Bladknutepunkt
En bladnode er en node som oppstår på det siste nivået av B+-treet, og hver bladnode bruker bare én peker for å koble til hverandre for å gi sekvensiell tilgang på bladnivå.
I bladnoden er det maksimale antallet barn:
Maksimalt antall søkenøkler er:
Rotnoden
Maksimalt antall barn for rotnoden er: b
Minste antall barn er: 2
Spesielle tilfeller i B+ tre
Tilfelle 1: Hvis rotnoden er den eneste noden i treet. I dette tilfellet blir rotnoden til bladnoden.
I dette tilfellet er det maksimale antallet barn 1, det vil si selve rotnoden, mens minimumsantallet av barn er b-1, som er det samme som for en bladnode.
Representasjon av en bladnode i B+-tre
I figuren ovenfor, '.' representerer pekeren, mens 10, 20 og 30 er nøkkelverdiene. Pekeren inneholder adressen der nøkkelverdien er lagret, som vist i figuren ovenfor.
Eksempel på B+-tre
I figuren ovenfor inneholder noden tre nøkkelverdier, dvs. 9, 16 og 25. Pekeren som vises før 9, inneholder nøkkelverdiene mindre enn 9 representert av kJeg. Pekeren som vises før 16, inneholder nøkkelverdiene større enn eller lik 9, men mindre enn 16 representert ved kj. Pekeren som vises før 25, inneholder nøkkelverdiene større enn eller lik 16, men mindre enn 25 representert av kn.
Forskjeller mellom B-tre og B+-tre
Følgende er forskjellene mellom B-treet og B+-treet:
| B tre | B+ tre |
|---|---|
| I B-treet er alle nøklene og postene lagret i både interne så vel som bladnoder. | I B+-treet er nøkler indeksene som er lagret i de interne nodene, og poster lagres i bladnodene. |
| I B-treet kan ikke nøkler lagres gjentatte ganger, noe som betyr at det ikke er noen duplisering av nøkler eller poster. | I B+-treet kan det være redundans i forekomsten av nøklene. I dette tilfellet lagres postene i bladnodene, mens nøklene er lagret i de interne nodene, slik at redundante nøkler kan være tilstede i de interne nodene. |
| I Btree er ikke bladnoder knyttet til hverandre. | I B+-treet er bladnodene koblet til hverandre for å gi sekvensiell tilgang. |
| I Btree er søk lite effektivt fordi postene enten er lagret i blad- eller interne noder. | I B+-treet er søk veldig effektivt eller raskere fordi alle postene er lagret i bladnodene. |
| Sletting av interne noder er veldig sakte og en tidkrevende prosess da vi også må vurdere barnet til den slettede nøkkelen. | Sletting i B+-treet er veldig raskt fordi alle postene er lagret i bladnodene slik at vi ikke trenger å vurdere barnet til noden. |
| I Btree er sekvensiell tilgang ikke mulig. | I B+-treet er alle bladnodene koblet til hverandre gjennom en peker, så sekvensiell tilgang er mulig. |
| I Btree utføres flere kløyveoperasjoner på grunn av hvilken høyde øker sammenlignet med bredde, | B+ treet har mer bredde sammenlignet med høyden. |
| I Btree har hver node minst to grener og hver node inneholder noen poster, så vi trenger ikke å krysse før bladnodene for å få dataene. | I B+-treet inneholder interne noder kun pekere og bladnoder inneholder poster. Alle bladnodene er på samme nivå, så vi må krysse til bladnodene for å få dataene. |
| Rotnoden inneholder minst 2 til m barn der m er rekkefølgen til treet. | Rotnoden inneholder minst 2 til m barn der m er rekkefølgen til treet. |