Hva er et B + Tree?
Et B + -treet brukes primært til å implementere dynamisk indeksering på flere nivåer. Sammenlignet med B-Tree lagrer B + Tree datapekerne bare ved bladnodene til treet, noe som gjør søk mer prosess mer nøyaktig og raskere.
I denne B + Tree-opplæringen lærer du:
- Hva er et B + Tree?
- Regler for B + Tree
- Hvorfor bruke B + Tree
- B + Tree vs. B Tree
- Søkeoperasjon
- Sett inn operasjon
- Slett operasjon
Regler for B + Tree
Her er viktige regler for B + Tree.
- Blad brukes til å lagre dataposter.
- Den lagres i de interne nodene i treet.
- Hvis en målnøkkelverdi er mindre enn den interne noden, følges punktet rett til venstre side.
- Hvis en målnøkkelverdi er større enn eller lik den interne noden, følges punktet rett til høyre side.
- Roten har minimum to barn.
Hvorfor bruke B + Tree
Her er grunner til å bruke B + Tree:
- Nøkkel brukes primært til å hjelpe søket ved å lede til riktig blad.
- B + Tree bruker en "fyllfaktor" for å håndtere økningen og reduksjonen i et tre.
- I B + -trær kan mange nøkler lett plasseres på minnesiden fordi de ikke har dataene knyttet til de indre noder. Derfor vil den raskt få tilgang til tredata som er på bladnoden.
- En omfattende fullskanning av alle elementene er et tre som trenger bare ett lineært pass, fordi alle bladnodene til et B + -tre er knyttet til hverandre.
B + Tree vs. B Tree
Her er de viktigste forskjellene mellom B + Tree vs. B Tree
| B + tre | B Tre |
| Søketaster kan gjentas. | Søketaster kan ikke være overflødige. |
| Data lagres bare på bladnodene. | Både bladnoder og interne noder kan lagre data |
| Data lagret på bladnoden gjør søket mer nøyaktig og raskere. | Søket er tregt på grunn av data lagret på Leaf og interne noder. |
| Sletting er ikke vanskelig ettersom et element bare fjernes fra en bladnode. | Sletting av elementer er en komplisert og tidkrevende prosess. |
| Koblede bladnoder gjør søket effektivt og raskt. | Du kan ikke koble bladnoder. |
Søkeoperasjon
I B + Tree er et søk en av de enkleste prosedyrene for å utføre og få raske og nøyaktige resultater av det.
Følgende søkealgoritme gjelder:
- For å finne den nødvendige posten, må du utføre det binære søket på tilgjengelige poster i treet.
- I tilfelle nøyaktig samsvar med søketasten, blir den tilsvarende posten returnert til brukeren.
- Hvis den eksakte nøkkelen ikke er lokalisert ved søket i foreldre-, nåværende- eller bladnoden, vises en "ikke funnet melding" for brukeren.
- Søkeprosessen kan kjøres på nytt for bedre og mer nøyaktige resultater.
Søk i operasjonsalgoritme
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Utgang :
Den samsvarende posten som er satt mot den eksakte nøkkelen, vises for brukeren; Ellers vises et mislykket forsøk for brukeren.
Sett inn operasjon
Følgende algoritme gjelder for innsettingsoperasjonen:
- 50 prosent av elementene i nodene flyttes til et nytt blad for lagring.
- Forelderen til det nye bladet er nøyaktig knyttet til minimum nøkkelverdi og en ny plassering i treet.
- Del foreldrenoden på flere steder i tilfelle den blir fullt utnyttet.
- Nå, for bedre resultater, er midtnøkkelen assosiert med toppnivået i bladet.
- Inntil toppnivået ikke blir funnet, fortsett å gjenta prosessen som er forklart i trinnene ovenfor.
Sett inn operasjonsalgoritme
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
Utgang :
Algoritmen vil bestemme elementet og sette det inn i den nødvendige bladnoden.
Ovennevnte eksempel på B + Tree er forklart i trinnene nedenfor:
- For det første har vi 3 noder, og de første 3 elementene, som er 1, 4 og 6, blir lagt til på passende steder i nodene.
- Den neste verdien i rekken av data er 12 som må gjøres til en del av treet.
- For å oppnå dette, del noden, legg til 6 som et pekerelement.
- Nå opprettes et høyrehierarki av et tre, og gjenværende dataverdier justeres tilsvarende ved å huske gjeldende regler som er lik eller større enn verdier mot nøkkelverdienodene til høyre.
Slett operasjon
Kompleksiteten til slettingsprosedyren i B + -treet overgår den for innsettings- og søkefunksjonaliteten.
Følgende algoritme gjelder når du sletter et element fra B + -treet:
- For det første må vi finne en bladoppføring i treet som holder nøkkelen og pekeren. , slett bladoppføringen fra treet hvis bladet oppfyller de eksakte vilkårene for sletting av posten.
- Hvis bladnoden bare oppfyller tilfredsstillende faktor for å være halvfull, er operasjonen fullført. Ellers har Leaf-noden minimumoppføringer og kan ikke slettes.
- De andre koblede nodene til høyre og venstre kan fraflytte alle oppføringer og deretter flytte dem til bladet. Hvis disse kriteriene ikke er oppfylt, bør de kombinere bladnoden og den tilknyttede noden i trehierarkiet.
- Ved sammenslåing av bladnode med naboene til høyre eller venstre, slettes oppføringer av verdier i bladnoden eller koblet nabo som peker til toppnoden.
Eksemplet ovenfor illustrerer fremgangsmåten for å fjerne et element fra B + -treet i en bestemt rekkefølge.
- For det første identifiseres de nøyaktige stedene for elementet som skal slettes i treet.
- Her kan elementet som skal slettes bare identifiseres nøyaktig på bladnivå og ikke på indeksplasseringen. Derfor kan elementet slettes uten å påvirke slettingsreglene, som er verdien av den minste minimumsnøkkelen.
- I eksemplet ovenfor må vi slette 31 fra treet.
- Vi må finne forekomster av 31 i Index og Leaf.
- Vi kan se at 31 er tilgjengelig både på indeks- og bladnodenivå. Derfor sletter vi det fra begge tilfeller.
- Men vi må fylle indeksen som peker til 42. Vi vil nå se på det rette barnet under 25 år og ta minimumsverdien og plassere den som en indeks. Så, som 42 er den eneste verdien som er tilstede, blir den indeksen.
Slett operasjonsalgoritme
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Utgang :
Nøkkelen "K" slettes, og nøklene lånes fra søsken for å justere verdiene i n og dens overordnede noder om nødvendig.
Sammendrag:
- B + Tree er en selvbalanserende datastruktur for å utføre nøyaktig og raskere søk, innsetting og sletting av prosedyrer på data
- Vi kan enkelt hente fullstendige eller delvise data fordi det å gå gjennom den koblede trestrukturen gjør det effektivt.
- B + trestrukturen vokser og krymper med en økning / reduksjon i antall lagrede poster.
- Lagring av data på bladnodene og etterfølgende forgrening av interne noder forkorter tydeligvis trehøyden, noe som reduserer diskinnmatings- og utgangsoperasjonene, og til slutt bruker mye mindre plass på lagringsenhetene.