B+ TRÆ: Søg, Indsæt og Slet Operations eksempel

Hvad er et B+-træ?

A B+ træ bruges primært til at implementere dynamisk indeksering på flere niveauer. Sammenlignet med B-træet gemmer B+-træet kun datapegerne ved træets bladknuder, hvilket gør søgning mere nøjagtig og hurtigere.

Regler for B+ Træ

Her er væsentlige regler for B+ Tree.

• Blade bruges til at gemme dataposter.
• Det er gemt i træets interne noder.
• Hvis en målnøgleværdi er mindre end den interne node, følges punktet lige til dens venstre side.
• Hvis en målnøgleværdi er større end eller lig med den interne node, følges punktet lige til højre for dens side.
• Roden har minimum to børn.

Hvorfor bruge B+ Tree

Her er grunde til at bruge B+ Tree:

• Nøgler bruges primært til at hjælpe søgningen ved at lede til det rigtige blad.
• B+ Tree bruger en "fyldningsfaktor" til at styre stigningen og faldet i et træ.
• I B+ træer kan adskillige nøgler nemt placeres på hukommelsessiden, fordi de ikke har de data, der er knyttet til de indre knudepunkter. Derfor vil den hurtigt få adgang til trædata, der er på bladknuden.
• En omfattende fuld scanning af alle elementerne er et træ, der kun behøver et lineært gennemløb, fordi alle bladknuderne i et B+ træ er forbundet med hinanden.

B+ træ vs. B træ

Her er de vigtigste forskelle mellem B+ Tree vs. B Tree

B+ træ	B Træ
Søgetaster kan gentages.	Søgenøgler kan ikke være overflødige.
Data gemmes kun på bladknuderne.	Både bladknuder og interne knudepunkter kan gemme data
Data gemt på bladknuden gør søgningen mere præcis og hurtigere.	Søgning er langsom på grund af data gemt på Leaf og interne noder.
Sletning er ikke vanskelig, da et element kun fjernes fra en bladknude.	Sletning af elementer er en kompliceret og tidskrævende proces.
Sammenkædede bladknuder gør søgningen effektiv og hurtig.	Du kan ikke sammenkæde bladknuder.

Søg Operation

I B+ Tree er en søgning en af ​​de nemmeste procedurer at udføre og få hurtige og præcise resultater fra den.

Følgende søgealgoritme er anvendelig:

• For at finde den nødvendige post, skal du udføre binær søgning på de tilgængelige poster i træet.
• I tilfælde af et nøjagtigt match med søgenøglen, returneres den tilsvarende post til brugeren.
• Hvis den nøjagtige nøgle ikke findes af søgningen i den overordnede, nuværende eller bladknude, så vises en "ikke fundet-meddelelse" til brugeren.
• Søgningsprocessen kan køres igen for bedre og mere præcise resultater.

Søg Operationsalgoritme

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

Produktion:

Den matchede rekord, der er sat i forhold til den nøjagtige nøgle, vises for brugeren; ellers vises et mislykket forsøg til brugeren.

indsatte Operation

Følgende algoritme er anvendelig for indsættelsesoperationen:

• 50 procent af elementerne i noderne flyttes til et nyt blad til opbevaring.
• Forælderen til det nye blad er knyttet nøjagtigt til den mindste nøgleværdi og en ny placering i træet.
• Opdel den overordnede node i flere placeringer, hvis den bliver fuldt udnyttet.
• Nu, for at opnå bedre resultater, er den midterste nøgle knyttet til noden på øverste niveau af det pågældende blad.
• Indtil noden på øverste niveau ikke er fundet, skal du fortsætte med at gentage processen, der er forklaret i ovenstående trin.

indsatte Operationsalgoritme

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.  

Produktion:

Algoritmen vil bestemme elementet og med succes indsætte det i den nødvendige bladknude.

Ovenstående eksempel på B+-træ er forklaret i nedenstående trin:

• For det første har vi 3 noder, og de første 3 elementer, som er 1, 4 og 6, tilføjes på passende steder i noderne.
• Den næste værdi i rækken af ​​data er 12, der skal gøres til en del af træet.
• For at opnå dette skal du opdele noden, tilføje 6 som et markørelement.
• Nu oprettes et højre-hierarki af et træ, og de resterende dataværdier justeres i overensstemmelse hermed ved at huske på de gældende regler, der er lig med eller større end værdier mod nøgleværdiknuderne til højre.

Slette Operation

Kompleksiteten af ​​sletteproceduren i B+ træet overgår indsættelses- og søgefunktionaliteten.

Følgende algoritme er anvendelig, mens du sletter et element fra B+-træet:

• For det første skal vi finde en bladindgang i træet, der holder nøglen og markøren. , slet bladindgangen fra træet, hvis bladet opfylder de nøjagtige betingelser for sletning af post.
• I tilfælde af at bladknuden kun opfylder den tilfredsstillende faktor at være halvfuld, så er operationen afsluttet; Ellers har Leaf-noden minimumsindgange og kan ikke slettes.
• De andre forbundne noder til højre og venstre kan forlade alle indgange og derefter flytte dem til bladet. Hvis disse kriterier ikke er opfyldt, skal de kombinere bladknuden og dens sammenkædede knude i træhierarkiet.
• Ved sammenlægning af bladknudepunktet med dets naboer til højre eller venstre, slettes indtastninger af værdier i bladknudepunktet eller den linkede nabo, der peger på noden på øverste niveau.

Eksemplet ovenfor illustrerer proceduren til at fjerne et element fra B+ træet i en bestemt rækkefølge.

• For det første identificeres de nøjagtige placeringer af det element, der skal slettes, i træet.
• Her kan det element, der skal slettes, kun identificeres nøjagtigt på bladniveau og ikke ved indeksplacering. Derfor kan elementet slettes uden at påvirke sletningsreglerne, som er værdien af ​​den absolutte minimumsnøgle.

• I ovenstående eksempel skal vi slette 31 fra træet.
• Vi er nødt til at finde forekomsterne af 31 i Index og Leaf.
• Vi kan se, at 31 er tilgængelig i både Index og Leaf node niveau. Derfor sletter vi det fra begge instanser.
• Men vi skal udfylde indekset, der peger på 42. Vi vil nu se på det rigtige barn under 25 og tage minimumsværdien og placere det som et indeks. Så da 42 er den eneste tilstedeværende værdi, bliver det indekset.

Slette Operationsalgoritme

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

Produktion:

Nøglen "K" slettes, og nøgler lånes fra søskende til justering af værdier i n og dens overordnede noder, hvis det er nødvendigt.

Resumé

• B+ Tree er en selvbalancerende datastruktur til at udføre præcise og hurtigere søgnings-, indsættelses- og sletningsprocedurer på data
• Vi kan nemt hente komplette data eller delvise data, fordi at gå gennem den sammenkædede træstruktur gør det effektivt.
• B+ træstrukturen vokser og krymper med en stigning/reduktion i antallet af lagrede poster.
• Lagring af data på bladknuderne og efterfølgende forgrening af interne noder forkorter åbenbart træhøjden, hvilket reducerer diskens input og output operationer, hvilket i sidste ende forbruger meget mindre plads på lagerenhederne.