B TRÄD i datastruktur: Sök, infoga, ta bort operationsexempel

Vad är ett B-träd?

B Tree är en självbalanserande datastruktur baserad på en specifik uppsättning regler för att söka, infoga och ta bort data på ett snabbare och minneseffektivt sätt. För att uppnå detta följs följande regler för att skapa ett B-träd.

Ett B-träd är en speciell typ av träd i en datastruktur. 1972 introducerades denna metod först av McCreight och Bayer kallade den Height Balanced m-way Search Tree. Det hjälper dig att bevara sorterad data och tillåta olika operationer som insättning, sökning och radering på kortare tid.

I denna B-Tree-handledning lär du dig:

Vad är ett B-träd?
Varför använda B-Tree
Historia av B Tree
Sökoperation
Sätt i drift
Radera operation

Regler för B-Tree

Här är viktiga regler för att skapa B_Tree

Alla löv skapas på samma nivå.
B-Tree bestäms av ett antal grader, som också kallas "ordning" (specificerad av en extern aktör, som en programmerare), kallad
```
m
```
framåt. Värdet av
```
m
```
beror på blockstorleken på skivan där data primärt finns.
Det vänstra underträdet i noden har lägre värden än underträdets högra sida. Detta innebär att noderna också sorteras i stigande ordning från vänster till höger.
Det maximala antalet underordnade noder, en rotnod och dess undernoder kan innehålla beräknas enligt följande formel:
```
m - 1
```
Till exempel:
```
m = 4max keys: 4 - 1 = 3
```

Varje nod, utom rot, måste innehålla minsta nycklar på
```
[m/2]-1
```
Till exempel:
```
m = 4min keys: 4/2-1 = 1
```
Det maximala antalet underordnade noder som en nod kan ha är lika med dess grad, vilket är
```
m
```
Minsta barn en nod kan ha är hälften av ordningen, vilket är m / 2 (takvärdet tas).
Alla nycklar i en nod sorteras i ökande ordning.

Varför använda B-Tree

Här är skäl att använda B-Tree

Minskar antalet läsningar som gjorts på disken
B Träd kan enkelt optimeras för att justera dess storlek (det vill säga antalet barnnoder) enligt diskstorleken
Det är en specialdesignad teknik för att hantera en skrymmande mängd data.
Det är en användbar algoritm för databaser och filsystem.
Ett bra val att välja när det gäller att läsa och skriva stora datablock

Historia av B Tree

Data lagras på disken i block, dessa data, när de tas in i huvudminnet (eller RAM) kallas datastruktur.
Vid enorma data krävs det att du läser hela disken för att söka efter en post på disken. detta ökar tid och minnesförbrukning på grund av hög diskåtkomstfrekvens och datastorlek.
För att övervinna detta skapas indextabeller som sparar postreferensen för posterna baserat på blocken de finns i. Detta minskar tid och minnesförbrukning drastiskt.
Eftersom vi har enorma data kan vi skapa flertalet indextabeller.
Flernivåindex kan designas med hjälp av B Tree för att hålla data sorterade på ett självbalanserande sätt.

Sökoperation

Sökningen är den enklaste åtgärden på B Tree.

Följande algoritm tillämpas:

Låt nyckeln (värdet) sökas med "k".
Börja söka från roten och korsa rekursivt neråt.
Om k är mindre än rotvärdet, sök i vänster underträd, om k är större än rotvärdet, sök i rätt underträd.
Om noden har hittat k, returnerar du bara noden.
Om k inte finns i noden, gå ner till barnet med en större nyckel.
Om k inte finns i trädet returnerar vi NULL.

Sätt i drift

Eftersom B Tree är ett självbalanserande träd kan du inte tvinga in en nyckel i en valfri nod.

Följande algoritm gäller:

Kör sökningen och hitta rätt plats för infogning.
Sätt in den nya nyckeln på rätt plats, men om noden redan har ett maximalt antal nycklar:
Noden, tillsammans med en nyinsatt nyckel, kommer att delas från mittelementet.
Mittelementet blir förälder för de andra två barnnoderna.
Noderna måste ordna nycklarna i stigande ordning.

DRICKS

Följande gäller inte införingsalgoritmen:

Eftersom noden är full delas den därför upp och sedan kommer ett nytt värde att införas

I exemplet ovan:

Sök efter lämplig position i noden efter nyckeln
Sätt in nyckeln i målnoden och leta efter regler
Har noden efter införandet mer än lika med ett minsta antal nycklar, vilket är 1? I det här fallet, ja, det gör det. Kontrollera nästa regel.
Har noden efter insättning mer än ett maximalt antal nycklar, vilket är 3? I det här fallet, nej, det gör det inte. Detta innebär att B-trädet inte bryter mot några regler och att infogningen är klar.

I exemplet ovan:

Noden har nått det maximala antalet nycklar
Noden kommer att delas och den mellersta nyckeln blir rotnoden för resten av de två noderna.
Vid ett jämnt antal nycklar väljs den mittersta noden med vänster bias eller höger bias.

I exemplet ovan:

Noden har mindre än max nycklar
1 infogas bredvid 3, men regeln för stigande ordning bryts
För att åtgärda detta sorteras nycklarna

På samma sätt kan 13 och 2 enkelt infogas i noden eftersom de uppfyller regeln för mindre än maxnycklar för noderna.

I exemplet ovan:

Noden har nycklar lika med maxnycklar.
Nyckeln infogas i målnoden, men den bryter mot regeln för maxnycklar.
Målnoden är uppdelad, och den mellersta nyckeln med vänster bias är nu överordnade till de nya barnnoderna.
De nya noderna är ordnade i stigande ordning.

På samma sätt, baserat på ovanstående regler och fall, kan resten av värdena enkelt införas i B-trädet.

Radera operation

Raderingsåtgärden har fler regler än insättnings- och sökoperationer.

Följande algoritm gäller:

Kör sökoperationen och hitta målnyckeln i noderna
Tre villkor tillämpade baserat på placeringen av målnyckeln, vilket förklaras i följande avsnitt

Om målnyckeln finns i bladnoden

Målet är i bladnoden, mer än min nycklar.
- Om du tar bort detta bryter inte B Tree's egendom
Målet är i bladnoden, det har min nyckelnoder
- Om du tar bort detta bryter du B Tree
- Målnoden kan låna nyckel från omedelbar vänster nod eller omedelbar höger nod (syskon)
- Syskonet kommer att säga ja om det har fler än minsta antal nycklar
- Nyckeln kommer att lånas från modernoden, maxvärdet överförs till en förälder, maxvärdet för modernoden överförs till målnoden och tar bort målvärdet
Målet är i bladnoden, men inga syskon har mer än min antal nycklar
- Sök efter nyckel
- Slå ihop med syskon och minimalt med föräldernoder
- Totalt antal nycklar blir nu mer än min
- Målnyckeln kommer att ersättas med ett minimum av en föräldernod

Om målnyckeln finns i en intern nod

Antingen välj, beställare eller efterträdare
Om föregångaren är i ordning väljs den maximala tangenten från dess vänstra underträd
Vid efterföljare i ordning väljs minsta tangent från dess högra underträd
Om målnyckelens beställda föregångare har mer än min-tangenterna, kan den bara ersätta målnyckeln med max för föregångaren i ordning
Om målnyckelens beställare inte har mer än minknappar, leta efter efterföljarens minsta nyckel.
Om målnyckelns beställda föregångare och efterträdare båda har mindre än min nycklar, slå sedan ihop föregångaren och efterträdaren.

Om målnyckeln finns i en rotnod

Ersätt med det maximala elementet i föregångaren i ordning
Om målet efter borttagning har mindre än min-tangenter, kommer målnoden att låna maxvärde från sitt syskon via syskonets förälder.
Förälderns maxvärde tas av ett mål, men med noderna för syskonets maxvärde.

Låt oss nu förstå borttagningen med ett exempel.

Ovanstående diagram visar olika fall av radering i ett B-träd. Detta B-träd är av ordning 5, vilket betyder att det minsta antalet barnnoder vilken nod som helst kan ha är 3, och det maximala antalet barnnoder vilken nod som helst kan ha är 5. Medan det lägsta och högsta antalet nycklar vilken nod som helst kan ha är 2 respektive 4.

I exemplet ovan:

Målnoden har den målnyckel som ska tas bort
Målnoden har nycklar mer än minsta nycklar
Ta bara bort nyckeln

I exemplet ovan:

Målnoden har nycklar som är lika med miniminivåerna, så kan inte ta bort den direkt eftersom den bryter mot villkoren

Nu förklarar följande diagram hur du tar bort den här nyckeln:

Målnoden kommer att låna en nyckel från omedelbar syskon, i det här fallet i ordning föregångare (vänster syskon) eftersom den inte har någon efterföljare i ordning (höger syskon)
Det maximala värdet för inordnarens föregångare överförs till föräldern och föräldern överför det maximala värdet till målnoden (se diagrammet nedan)

Följande exempel illustrerar hur man tar bort en nyckel som behöver ett värde från sin efterföljare.

Målnoden kommer att låna en nyckel från omedelbar syskon, i det här fallet efterföljare i ordning (höger syskon) eftersom dess föregångare (vänster syskon) har nycklar som är lika med minsta nycklar.
Minimivärdet för efterföljaren i order kommer att överföras till föräldern och föräldern överför det maximala värdet till målnoden.

I exemplet nedan har målnoden inget syskon som kan ge sin nyckel till målnoden. Därför krävs sammanslagning.

Se proceduren för att radera en sådan nyckel:

Slå samman målnoden med någon av dess omedelbara syskon tillsammans med föräldernyckeln
- Nyckeln från föräldernoden väljs som syskon mellan de två sammanslagna noderna
Ta bort målnyckeln från den sammanslagna noden

Ta bort operation Pseudokod

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Utgång :

Det största elementet raderas från B-trädet.

Sammanfattning:

B Tree är en självbalanserande datastruktur för bättre sökning, insättning och radering av data från disken.
B Trädet regleras av den angivna graden
B Trädnycklar och noder är ordnade i stigande ordning.
Sökningen av B Tree är den enklaste, som alltid börjar från roten och börjar kontrollera om målnyckeln är större eller mindre än nodvärdet.
Insättningen av B Tree är ganska detaljerad, som först hittar en lämplig position för insättning för målnyckeln, infogar den, utvärderar B-trädets giltighet mot olika fall och sedan omstrukturerar B Tree-noderna därefter.
Radering av B Tree söker först efter målnyckeln som ska raderas, tar bort den, utvärderar giltigheten baserat på flera fall som minimi- och maximaltangenter för målnoden, syskonen och föräldern.