B+ TRÄD: Sök, infoga och ta bort Operationer

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 ett B-träd lagrar B+-trädet endast datapekarna vid trädets lövnoder, vilket gör sökprocessen mer exakt och snabbare.

Regler för B+ Tree

Här är viktiga regler för ett B+ träd.

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

Varför använda B+ Tree

Här är anledningar till att använda ett B+-träd:

• Nycklar används främst för att underlätta sökningen genom att leda till rätt blad.
• Ett B+-träd använder en "fyllnadsfaktor" 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 skanning av alla element kräver bara ett linjärt steg eftersom alla lövnoder i ett B+ träd är länkade till varandra.

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

Här är de viktigaste skillnaderna mellan ett B+ träd och ett B-träd.

Sök Operation

I ett B+ träd är en sökning en av de enklaste procedurerna att utföra och ger snabba och exakta resultat.

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 lövet länkas korrekt med det lägsta nyckelvärdet och en ny plats i trädet.
• Dela upp den överordnade noden i fler platser ifall den utnyttjas fullt ut.
• För bättre resultat är nu den mittersta nyckeln associerad med den översta noden på det lövet.
• Tills toppnivånoden inte hittas, fortsätt att iterera processen som förklaras i stegen ovan.

Insert Operationsalgoritm

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.

Produktion: Algoritmen kommer att bestämma elementet och framgångsrikt infoga det i den nödvändiga lövnoden.

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

• Först 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 dataserien är 12, vilket måste göras till en del av trädet.
• För att uppnå detta, dividera noden och lägg till 6 som ett pekarelement.
• Nu skapas en högerhierarki av ett träd, och de återstående datavärdena justeras därefter av kee.ping med tanke på de tillämpliga reglerna för värden som är lika med eller större än 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örst måste vi hitta en lövpost i trädet som innehåller nyckeln och pekaren, och sedan radera lövposten från trädet om lövet uppfyller de exakta villkoren för borttagning av poster.
• Om lövnoden bara uppfyller den tillfredsställande faktorn att vara halvfull, är operationen slutförd; annars har lövnoden ett minimum av poster och kan inte raderas.
• De andra länkade noderna till höger och vänster kan tömma alla poster och sedan flytta dem till lövbladet. Om dessa kriterier inte är uppfyllda bör de kombinera lövnoden och dess länkade nod i trädhierarkin.
• Vid sammanslagning av en lövnod med dess grannar till höger eller vänster raderas värdeposter i lövnoden eller den länkade grannen som pekar på noden på toppnivå.

Exemplet ovan illustrerar proceduren för att ta bort ett element från ett B+-träd 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 korrekt på lövnivå och inte vid indexplaceringen. Därför kan elementet raderas utan att det påverkar raderingsreglerna, vilket är värdet för den absoluta minimumnyckeln.

• I exemplet ovan måste vi ta bort 31 från trädet.
• Vi behöver lokalisera 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 den från båda instanserna.
• Men vi måste fylla indexet så att det pekar mot 42. Vi ska nu titta på rätt barn under 25 år och ta minimivärdet och placera det som ett index. Så eftersom 42 är det enda värdet som finns, blir det indexet.

Radera Operationsalgoritm

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

Produktion: Nyckeln "K" tas bort, och nycklar lånas från syskon för att justera värden i n och dess överordnade noder vid behov.

Vanliga frågor