Vad är ett B + träd?
Ett B + -träd används främst för att implementera dynamisk indexering på flera nivåer. Jämfört med B-Tree lagrar B + Tree datapekarna bara i trädets bladnoder, vilket gör sökningen mer process mer exakt och snabbare.
I denna B + Tree-handledning lär du dig:
- Vad är ett B + träd?
- Regler för B + Tree
- Varför använda B + Tree
- B + Tree vs. B Tree
- Sökoperation
- Sätt i drift
- Radera operation
Regler för B + Tree
Här är viktiga regler för B + Tree.
- Bladen används för att lagra dataposter.
- Den lagras i trädets interna noder.
- Om ett målnyckelvärde är mindre än den interna noden följs punkten precis till vänster.
- Om ett målnyckelvärde är större än eller lika med den interna noden följs punkten precis till höger sida.
- Roten har minst två barn.
Varför använda B + Tree
Här finns skäl till att använda B + Tree:
- Nycklar 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 associerade med de inre noderna. Därför kommer den snabbt att komma åt träddata som finns på bladnoden.
- En omfattande fullständig genomsökning av alla element är ett träd som behöver bara ett linjärt pass eftersom alla bladnoder i ett B + -träd är kopplade till varandra.
B + Tree vs. B Tree
Här är de viktigaste skillnaderna mellan B + Tree vs. B Tree
| B + träd | B träd |
| Sökningsknappar kan upprepas. | Sökningsknappar kan inte vara överflödiga. |
| Data sparas bara på bladnoderna. | Både bladnoder och interna noder kan lagra data |
| Data lagrad på bladnoden gör sökningen mer exakt och snabbare. | Sökningen är långsam på grund av data som lagras på Leaf och interna noder. |
| Radering är inte svårt eftersom ett element bara tas bort från en bladnod. | Radering av element är en komplicerad och tidskrävande process. |
| Länkade bladnoder gör sökningen effektiv och snabb. | Du kan inte länka bladnoder. |
Sökoperation
I B + Tree är en sökning en av de enklaste procedurerna för att utföra och få snabba och exakta resultat från den.
Följande sökalgoritm är tillämplig:
- För att hitta den post som krävs måste du utföra den binära sökningen på tillgängliga poster i trädet.
- Om en exakt matchning med söktangenten returneras motsvarande post till användaren.
- Om den exakta nyckeln inte lokaliseras genom sökningen i föräldra-, nuvarande- eller bladnoden, visas ett "inte hittat meddelande" för användaren.
- Sökprocessen kan köras om för bättre och mer exakta resultat.
Sök operation algoritm
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Utgång :
Den matchade posten som ställts in mot den exakta tangenten visas för användaren; annars visas ett misslyckat försök för användaren.
Sätt i drift
Följande algoritm är tillämplig för insättningsoperationen:
- 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 föräldernoden på fler platser om den blir fullt utnyttjad.
- Nu, för bättre resultat, är mittnyckeln associerad med toppnivån i det bladet.
- Tills toppnivån inte hittas, fortsätt med att itera processen som förklaras i ovanstående steg.
Infoga operationsalgoritm
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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.
Utgång :
Algoritmen kommer att bestämma elementet och infoga det framgångsrikt i den önskade bladnoden.
Ovanstående exempel på B + Tree 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 dataserien ä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 pekarelement.
- Nu skapas en högerhierarki för ett träd och återstående datavärden justeras därefter genom att tänka på tillämpliga regler som är lika med eller större än värden mot nyckelvärdesnoderna till höger.
Radera operation
Komplexiteten för borttagningsproceduren i B + -trädet överträffar infognings- och sökfunktionaliteten.
Följande algoritm är tillämplig när du raderar ett element från B + -trädet:
- För det första måste vi hitta en bladpost i trädet som håller tangenten och pekaren. , ta bort bladposten från trädet om bladet uppfyller de exakta villkoren för postradering.
- Om bladnoden bara uppfyller den tillfredsställande faktorn att vara halvfull, är operationen slutförd; annars har Leaf-noden minimiposter och kan inte raderas.
- De andra länkade noder till höger och vänster kan lämna alla poster och sedan flytta dem till bladet. Om dessa kriterier inte uppfylls ska de kombinera bladnoden och dess länkade nod i trädhierarkin.
- Vid sammanslagning av bladnod med sina grannar till höger eller vänster raderas poster av värden i bladnoden eller den länkade grannen som pekar på toppnivånoden.
Exemplet ovan illustrerar proceduren för att ta bort ett element från B + -trädet i 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 raderas utan att det påverkar reglerna för borttagning, vilket är värdet på den minsta nyckeln.
- I exemplet ovan måste vi ta bort 31 från trädet.
- Vi måste hitta förekomsten av 31 i Index och Leaf.
- Vi kan se att 31 är tillgängligt på både index- och bladnodnivå. Därför tar vi bort det från båda instanser.
- Men vi måste fylla i indexet som pekar på 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 nuvarande värdet blir det index.
Ta bort operation algoritm
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Utgång :
Nyckeln "K" raderas och nycklarna 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 exakt och snabbare sökning, infoga och ta bort procedurer på data
- Vi kan enkelt hämta fullständig eller partiell data eftersom det går effektivt genom att gå igenom den länkade trädstrukturen.
- B + trädstrukturen växer och krymper med en ökning / minskning av antalet lagrade poster.
- Lagring av data på bladnoderna och efterföljande förgrening av interna noder förkortar uppenbarligen trädhöjden, vilket minskar skivinmatnings- och utmatningsoperationerna, vilket slutligen tar mycket mindre utrymme på lagringsenheterna.