B+ TREE: Søk, Sett inn og Slett Operasjoner Eksempel

Hva er et B+-tre?

A B+ tre brukes først og fremst for å implementere dynamisk indeksering på flere nivåer. Sammenlignet med B-treet lagrer B+-treet datapekerne kun ved bladnodene til treet, noe som gjør søkeprosessen mer nøyaktig og raskere.

Regler for B+ Tre

Her er viktige regler for B+ Tree.

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

Hvorfor bruke B+ Tree

Her er grunner til å bruke B+ Tree:

  • Nøkkel brukes først og fremst til å hjelpe søket ved å lede til riktig blad.
  • B+ Tree bruker en "fyllingsfaktor" for å håndtere økningen og reduksjonen 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 full skanning 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 og B Tree

B+ tre B tre
Søketaster kan gjentas. Søketøkler kan ikke være overflødige.
Data lagres kun 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 siden 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 sammen bladnoder.

Søk Operasjon

I B+ Tree er et søk en av de enkleste prosedyrene å utføre og få raske og nøyaktige resultater fra det.

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."

Produksjon:

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

innfelt Operasjonsalgoritme

1.	Even 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.  

Produksjon:

Algoritmen vil bestemme elementet og sette det inn i den nødvendige bladnoden.

innfelt Operasjon

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 serien med 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 for et tre, og gjenværende dataverdier justeres deretter ved å huske på gjeldende regler 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:

  • For det første må vi finne en bladinngang i treet som holder nøkkelen og pekeren. , slett bladoppføringen fra treet hvis bladet oppfyller de nøyaktige betingelsene for sletting av poster.
  • I tilfelle bladnoden bare oppfyller den tilfredsstillende faktoren for å være halvfull, er operasjonen fullført; Ellers har Leaf-noden minimumsoppføringer og kan ikke slettes.
  • De andre koblede nodene til høyre og venstre kan forlate alle 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 bladnoden med naboene til høyre eller venstre, slettes oppføringer av verdier i bladnoden eller koblet nabo som peker til toppnivånoden.

Delete Operasjon

Eksemplet ovenfor illustrerer prosedyren for å fjerne et element fra B+-treet i 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 indeksplassering. Derfor kan elementet slettes uten å påvirke slettingsreglene, som er verdien av minimumsnøkkelen.

Delete Operasjon

  • I eksemplet ovenfor må vi slette 31 fra treet.
  • Vi må finne forekomstene av 31 i Index og Leaf.
  • Vi kan se at 31 er tilgjengelig både på indeks- og bladnodenivå. Derfor sletter vi den fra begge forekomster.
  • Men, vi må fylle indeksen som peker til 42. Vi skal nå se på det rette barnet under 25 og ta minimumsverdien og plassere den som en indeks. Så, 42 er den eneste verdien til stede, vil det bli indeksen.

Delete Operasjonsalgoritme

1) Start at the root and go up to 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

Produksjon:

Nøkkelen "K" slettes, og nøkler lånes fra søsken for å justere verdiene i n og dens overordnede noder om nødvendig.

Oppsummering

  • B+ Tree er et selvbalanserende data struktur for å utføre nøyaktig og raskere søking, innsetting og sletting av data
  • Vi kan enkelt hente fullstendige data eller delvise data fordi å 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 påfølgende forgrening av interne noder forkorter åpenbart trehøyden, noe som reduserer diskinn- og utgangsoperasjonene, og til slutt bruker mye mindre plass på lagringsenhetene.