B+ TRÄD: Sök, infoga och radera Operations Exempel

Vad är ett B+-träd?

A B+ träd används främst för att implementera dynamisk indexering på flera nivåer. Jämfört med B-träd lagrar B+-trädet datapekarna endast vid trädets lövnoder, vilket gör sökningen mer exakt och snabbare.

Regler för B+ Tree

Här är viktiga regler för B+ Tree.

  • Blad används för att lagra dataposter.
  • Det lagras i trädets interna noder.
  • Om ett målnyckelvärde är mindre än den interna noden, följs punkten precis till dess vänstra sida.
  • Om ett målnyckelvärde är större än eller lika med den interna noden, följs punkten precis till dess högra sida.
  • Roten har minst två barn.

Varför använda B+ Tree

Här är skälen till att använda B+ Tree:

  • Nyckeln används främst för att underlätta sökningen genom att dirigera till rätt blad.
  • B+ Tree använder en "fyllningsfaktor" för att hantera ökningen och minskningen i ett träd.
  • I B+-träd kan många nycklar enkelt placeras på minnessidan eftersom de inte har data som är associerade med de inre noderna. Därför kommer den snabbt åt träddata som finns på lövnoden.
  • En omfattande fullständig genomsökning av alla element är ett träd som bara behöver en linjär pass eftersom alla bladnoder i ett B+-träd är länkade med varandra.

B+-träd vs. B-träd

Här är de viktigaste skillnaderna mellan B+ Tree och B Tree

B+ träd B Träd
Söktangenterna kan upprepas. Söknycklar kan inte vara överflödiga.
Data sparas endast på lövnoderna. Både bladnoder och interna noder kan lagra data
Data som lagras på lövnoden gör sökningen mer exakt och snabbare. Sökningen går långsamt på grund av data lagrad på Leaf och interna noder.
Radering är inte svårt eftersom ett element bara tas bort från en lövnod. Radering av element är en komplicerad och tidskrävande process.
Länkade lövnoder gör sökningen effektiv och snabb. Du kan inte länka lövnoder.

Sök Operation

I B+ Tree är en sökning en av de enklaste procedurerna att utföra och få snabba och exakta resultat från den.

Följande sökalgoritm är tillämplig:

  • För att hitta den nödvändiga posten måste du köra binär sökning på tillgängliga poster i trädet.
  • Vid en exakt matchning med söknyckeln returneras motsvarande post till användaren.
  • Om den exakta nyckeln inte hittas av sökningen i den överordnade, nuvarande eller lövnoden, visas ett "ej hittat meddelande" för användaren.
  • Sökprocessen kan köras om för bättre och mer exakta resultat.

Sök Operationsalgoritm

 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 matchade posten mot den exakta nyckeln visas för användaren; annars visas ett misslyckat försök för användaren.

Insert Operation

Följande algoritm är tillämplig för infogningsoperationen:

  • 50 procent av elementen i noderna flyttas till ett nytt blad för lagring.
  • Föräldern till det nya bladet är exakt länkat till det minsta nyckelvärdet och en ny plats i trädet.
  • Dela upp den överordnade noden i fler platser ifall den utnyttjas fullt ut.
  • Nu, för bättre resultat, är mittnyckeln associerad med toppnivånoden för det bladet.
  • Tills toppnivånoden inte hittas, fortsätt att iterera processen som förklaras i stegen ovan.

Insert Operationsalgoritm

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 kommer att bestämma elementet och framgångsrikt infoga det i den nödvändiga lövnoden.

Insert Operation

Ovanstående exempel på B+-träd förklaras i stegen nedan:

  • För det första har vi 3 noder, och de första 3 elementen, som är 1, 4 och 6, läggs till på lämpliga platser i noderna.
  • Nästa värde i serien av data är 12 som måste göras till en del av trädet.
  • För att uppnå detta, dela noden, lägg till 6 som ett pekelement.
  • Nu skapas en högerhierarki för ett träd, och återstående datavärden justeras i enlighet med detta genom att hålla i åtanke de tillämpliga reglerna för lika med eller större än värden mot nyckel-värde-noderna till höger.

Radera Operation

Komplexiteten i raderingsproceduren i B+-trädet överträffar den för infogning och sökfunktioner.

Följande algoritm är tillämplig när ett element tas bort från B+-trädet:

  • För det första måste vi hitta en bladpost i trädet som håller nyckeln och pekaren. , radera bladposten från trädet om bladet uppfyller de exakta villkoren för radering av post.
  • Om lövnoden endast uppfyller den tillfredsställande faktorn att vara halvfull, är operationen avslutad; annars har Leaf-noden minimiposter och kan inte tas bort.
  • De andra länkade noderna till höger och vänster kan lämna alla poster och sedan flytta dem till bladet. Om dessa kriterier inte är uppfyllda, bör de kombinera lövnoden och dess länkade nod i trädhierarkin.
  • Vid sammanslagning av lövnoden med dess grannar till höger eller vänster raderas värden i lövnoden eller länkad granne som pekar mot toppnivånoden.

Radera Operation

Exemplet ovan illustrerar proceduren för att ta bort ett element från B+-trädet av en specifik ordning.

  • För det första identifieras de exakta platserna för elementet som ska raderas i trädet.
  • Här kan elementet som ska raderas endast identifieras exakt på bladnivå och inte vid indexplacering. Därför kan elementet tas bort utan att det påverkar reglerna för borttagning, vilket är värdet på den absoluta miniminyckeln.

Radera Operation

  • I exemplet ovan måste vi ta bort 31 från trädet.
  • Vi måste hitta förekomsterna av 31 i Index och Leaf.
  • Vi kan se att 31 är tillgänglig på både Index- och Leaf-nodnivå. Därför tar vi bort det från båda instanserna.
  • Men vi måste fylla i indexet som pekar på 42. Vi ska nu titta på rätt barn under 25 och ta minimivärdet och placera det som ett index. Så, eftersom 42 är det enda värdet som finns, kommer det att bli index.

Radera Operationsalgoritm

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:

Nyckeln "K" raderas och nycklar lånas från syskon för att justera värden i n och dess överordnade noder om det behövs.

Sammanfattning

  • B+ Tree är en självbalanserande datastruktur för att utföra exakta och snabbare sökningar, infogning och radering av data
  • Vi kan enkelt hämta kompletta data eller partiella data eftersom att gå igenom den länkade trädstrukturen gör det effektivt.
  • B+-trädstrukturen växer och krymper med en ökning/minskning av antalet lagrade poster.
  • Lagring av data på lövnoderna och efterföljande förgrening av interna noder förkortar uppenbarligen trädhöjden, vilket minskar diskinmatnings- och utmatningsoperationerna, vilket slutligen förbrukar mycket mindre utrymme på lagringsenheterna.