B+ TRE: Søk, sett inn og slett Operasjoner

Hva er et B+-tre?

A B+ tre brukes primært til å implementere dynamisk indeksering på flere nivåer. Sammenlignet med et B-tre lagrer B+-treet datapekerne bare på bladnodene i treet, noe som gjør søkeprosessen mer nøyaktig og raskere.

Regler for B+ Tre

Her er viktige regler for et B+ tre.

• Blader brukes til å lagre dataposter.
• Poster lagres i de interne nodene i treet.
• Hvis en målnøkkelverdi er mindre enn den interne noden, følges pekeren like til venstre for den.
• Hvis en målnøkkelverdi er større enn eller lik den interne noden, følges pekeren like til høyre for den.
• Roten har minimum to barn.

Hvorfor bruke B+ Tree

Her er grunner til å bruke et B+-tre:

• Taster brukes primært til å hjelpe søket ved å peke til riktig blad.
• Et B+-tre bruker en «fyllingsfaktor» for å håndtere økning og reduksjon i et tre.
• I B+-trær kan mange nøkler enkelt plasseres på minnesiden fordi de ikke har data knyttet til de indre nodene. Derfor vil den raskt få tilgang til tredata som er på bladnoden.
• En omfattende fullskanning av alle elementene trenger bare én lineær passering fordi alle bladnodene i et B+ tre er koblet til hverandre.

B+ Tree vs. B Tree

Her er de viktigste forskjellene mellom et B+ tre og et B-tre.

Søk Operasjon

I et B+-tre er et søk en av de enkleste prosedyrene å utføre, og det gir raske og nøyaktige resultater.

Følgende søkealgoritme kan brukes:

• For å finne den nødvendige posten, må du utføre binært søk på de tilgjengelige postene i treet.
• Ved eksakt samsvar med søkenøkkelen, returneres den tilsvarende posten til brukeren.
• I tilfelle den eksakte nøkkelen ikke er lokalisert av søket i den overordnede, gjeldende eller bladnoden, vises en "ikke funnet-melding" til brukeren.
• Søkeprosessen kan kjøres på nytt for bedre og mer nøyaktige resultater.

Søk Operasjonsalgoritme

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
       The accurate result is returned and displayed to the user
   Else, if the node being searched is the current and the exact key is not found by the algorithm
       Display the statement "Recordset cannot be found."

Utgang: Den matchede posten satt mot den eksakte nøkkelen vises for brukeren; ellers vises et mislykket forsøk til brukeren.

innfelt 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 koblet til minimumsnøkkelverdien og en ny plassering i treet.
• Del den overordnede noden i flere steder i tilfelle den blir fullt utnyttet.
• For bedre resultater er nå den midterste nøkkelen knyttet til den øverste noden på det bladet.
• Inntil toppnivånoden ikke blir funnet, fortsett å gjenta prosessen som er forklart i trinnene ovenfor.

innfelt Operasjonsalgoritme

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. 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 tree.
   b. 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.

Eksempeleksemplet ovenfor 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, legges til på passende steder i nodene.
• Den neste verdien i dataserien er 12, som må gjøres til en del av treet.
• For å oppnå dette, divider noden og legg til 6 som et pekerelement.
• Nå opprettes et høyrehierarki av et tre, og de gjenværende dataverdiene justeres deretter av kee.ping husk de gjeldende reglene for lik eller større enn-verdier mot nøkkelverdi-nodene til høyre.

Delete Operasjon

Kompleksiteten til sletteprosedyren i B+-treet overgår den til innsettings- og søkefunksjonaliteten.

Følgende algoritme kan brukes når du sletter et element fra B+-treet:

• Først må vi finne en bladoppføring i treet som inneholder nøkkelen og pekeren, og deretter slette bladoppføringen fra treet hvis bladet oppfyller de nøyaktige betingelsene for sletting av poster.
• Dersom bladnoden bare oppfyller den tilfredsstillende faktoren om å være halvfull, er operasjonen fullført. Ellers har bladnoden et minimum av oppføringer og kan ikke slettes.
• De andre koblede nodene til høyre og venstre kan forlate eventuelle oppføringer og deretter flytte dem til bladet. Hvis disse kriteriene ikke er oppfylt, bør de kombinere bladnoden og dens koblede node i trehierarkiet.
• Ved sammenslåing av en bladnode med naboene til høyre eller venstre, slettes verdioppføringer i bladnoden eller den koblede naboen som peker til noden på toppnivå.

Eksemplet ovenfor illustrerer prosedyren for å fjerne et element fra et B+-tre av en bestemt rekkefølge.

• For det første identifiseres de nøyaktige plasseringene til elementet som skal slettes i treet.
• Her kan elementet som skal slettes bare identifiseres nøyaktig på bladnivå og ikke ved indeksplasseringen. Elementet kan derfor slettes uten å påvirke slettingsreglene, som er verdien til den absolutte minimumsnøkkelen.

• I eksemplet ovenfor må vi slette 31 fra treet.
• Vi må finne forekomstene av 31 i indeksen og bladet.
• Vi kan se at 31 er tilgjengelig på både indeks- og bladnodenivå. Derfor sletter vi den fra begge instansene.
• Men vi må fylle indeksen som peker mot 42. Vi skal nå se på det riktige barnet under 25 år og ta minimumsverdien og plassere den som en indeks. Så siden 42 er den eneste verdien som er tilstede, blir den indeksen.

Delete Operasjonsalgoritme

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  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 node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

Utgang: Nøkkelen «K» slettes, og nøkler lånes fra søsken for å justere verdier i n og dens overordnede noder om nødvendig.

Spørsmål og svar