B TREE i datastruktur: Sök, Infoga, Ta bort Operaexempel

Regler för B-Tree

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

• Alla blad kommer att skapas på samma nivå.
• B-Tree bestäms av ett antal grader, som också kallas "ordning" (specificeras av en extern aktör, som en programmerare), kallad

  m

  framåt. Värdet av

  m

  beror på blockstorleken på disken där data primärt finns.

• Det vänstra underträdet av noden kommer att ha lägre värden än den högra sidan av underträdet. Det betyder att noderna också sorteras i stigande ordning från vänster till höger.
• Det maximala antalet undernoder, en rotnod och dess undernoder kan innehålla beräknas med denna formel:

  m – 1

  Till exempel:

  m = 4
  max keys: 4 – 1 = 3
  

• Varje nod, utom root, måste innehålla minsta nycklar på

  [m/2]-1

  Till exempel:

  m = 4
  min keys: 4/2-1 = 1
  

• Det maximala antalet underordnade noder en nod kan ha är lika med dess grad, vilket är

  m

• Minsta barn som en nod kan ha är hälften av beställningen, 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 anledningar till att använda B-Tree

• Minskar antalet läsningar som görs på disken
• B-träd kan enkelt optimeras för att justera dess storlek (det vill säga antalet underordnade noder) 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

Historien om B Tree

• Data lagras på disken i block, dessa data, när de förs in i huvudminnet (eller RAM) kallas datastruktur.
• Om det rör sig om enorma data kräver sökning av en post på disken att hela disken läses; detta ökar tids- och minnesförbrukningen 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 drastiskt tids- och minnesförbrukningen.
• Eftersom vi har enorma data kan vi skapa indextabeller på flera nivåer.
• Multi-level index kan designas genom att använda B Tree för att hålla data sorterad på ett självbalanserande sätt.

Sök Operation

Sökoperationen är den enklaste operationen på B Tree.

Följande algoritm används:

• Låt nyckeln (värdet) som ska sökas med "k".
• Börja söka från roten och gå rekursivt nedåt.
• Om k är mindre än rotvärdet, sök vänster underträd, om k är större än rotvärdet, sök i höger underträd.
• Om noden har hittat k, returnera helt enkelt noden.
• Om k inte hittas i noden, gå ner till barnet med en större nyckel.
• Om k inte hittas i trädet returnerar vi NULL.

Insert Operation

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

Följande algoritm gäller:

• Kör sökoperationen och hitta lämplig plats för insättning.
• Sätt in den nya nyckeln på rätt plats, men om noden redan har ett maximalt antal nycklar:
• Noden, tillsammans med en nyinfogad nyckel, delas från mittelementet.
• Det mellersta elementet blir förälder för de andra två underordnade noderna.
• Noderna måste omarrangera nycklar i stigande ordning.

TIPS	Följande är inte sant om infogningsalgoritmen: Eftersom noden är full, kommer den att delas, och sedan kommer ett nytt värde att infogas

I exemplet ovan:

• Sök på lämplig position i noden efter nyckeln
• Sätt in nyckeln i målnoden och leta efter regler
• Efter infogning, har noden 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.
• Efter infogning, har noden mer än ett maximalt antal nycklar, vilket är 3? I det här fallet, nej, det gör det inte. Detta betyder att B-trädet inte bryter mot några regler, och insättningen är klar.

I exemplet ovan:

• Noden har nått max antal nycklar
• Noden kommer att delas och den mellersta nyckeln blir rotnoden för de andra två noderna.
• Vid ett jämnt antal nycklar kommer den mittersta noden att väljas med vänster- eller högerbias.

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 max nycklar för noderna.

I exemplet ovan:

• Noden har nycklar lika med max nycklar.
• Nyckeln infogas i målnoden, men den bryter mot regeln om maxnycklar.
• Målnoden är delad och mitttangenten genom vänsterförspänning är nu föräldern till de nya undernoderna.
• 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 infogas i B-trädet.

Radera Operation

Raderingsoperationen har fler regler än infogning och sökoperationer.

Följande algoritm gäller:

• Kör sökoperationen och hitta målnyckeln i noderna
• Tre villkor tillämpas baserat på platsen för målnyckeln, som förklaras i följande avsnitt

Om målnyckeln finns i lövnoden

• Target är i lövnoden, mer än min nycklar.
• Att ta bort detta kommer inte att kränka B Trees egendom
• Target är i bladnod, den har min nyckelnoder
• Att ta bort detta kommer att kränka B Trees egendom
• Target nod kan låna nyckel från omedelbar vänster nod, eller omedelbar höger nod (syskon)
• Syskonen kommer att säga ja om den har fler än minsta antal nycklar
• Nyckeln kommer att lånas från föräldernoden, maxvärdet kommer att överföras till en förälder, maxvärdet för föräldernoden kommer att överföras till målnoden, och tar bort målvärdet
• Target är i lövnoden, men inga syskon har mer än min antal nycklar
• Sök efter nyckel
• Slå samman med syskon och ett minimum av överordnade noder
• Totalt antal nycklar kommer nu att vara mer än min
• Målnyckeln kommer att ersättas med minimum av en överordnad nod

Om målnyckeln finns i en intern nod

• Välj antingen, beställ föregångare eller i ordning efterföljare
• I fallet med föregångaren i ordning, kommer den maximala nyckeln från dess vänstra underträd att väljas
• I händelse av efterföljare i ordning, kommer miniminyckeln från dess högra underträd att väljas
• Om målnyckelns föregångare i sin ordning har fler än min-tangenterna, kan den endast ersätta målnyckeln med max för föregångaren i sin ordning
• Om målnyckelns föregångare i ordning inte har fler än min-tangenter, leta efter efterföljarens miniminyckel i ordningen.
• Om målnyckelns föregångare och efterföljare båda har mindre än min-tangenter, slå ihop föregångaren och efterföljaren.

Om målnyckeln finns i en rotnod

• Ersätt med det maximala elementet i föregående underträd i ordning
• Om målet, efter radering, har mindre än min-nycklar, kommer målnoden att låna maxvärde från sitt syskon via syskons förälder.
• Maxvärdet för föräldern kommer att tas av ett mål, men med noderna för maxvärdet för syskonen.

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

Diagrammet ovan visar olika fall av raderingsoperationer i ett B-träd. Detta B-träd är av ordning 5, vilket innebär att det minsta antalet underordnade noder en nod kan ha är 3, och det maximala antalet underordnade noder som en nod kan ha är 5. Medan det minsta och högsta antalet nycklar en nod kan ha är 2. kan ha är 4 respektive XNUMX.

I exemplet ovan:

• Målnoden har målnyckeln att radera
• Målnoden har fler nycklar än minimumnycklar
• Ta bara bort nyckeln

I exemplet ovan:

• Målnoden har nycklar som är lika med minimumnycklar, så den kan inte raderas direkt eftersom den bryter mot villkoren

Nu förklarar följande diagram hur man tar bort denna nyckel:

• Målnoden kommer att låna en nyckel från närmaste syskon, i det här fallet, föregångare i ordning (vänster syskon) eftersom den inte har någon efterföljare i ordning (höger syskon)
• Det maximala värdet för föregångaren i ordningsföljd kommer att överföras till föräldern, och föräldern kommer att överföra 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 i sin ordning.

• 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 i ordning (vänster syskon) har nycklar lika med minsta nycklar.
• Minsta värdet för efterföljaren i ordning kommer att överföras till föräldern, och föräldern kommer att överföra det maximala värdet till målnoden.

I exemplet nedan har målnoden inte något 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 överordnad nyckel
• Nyckeln från den överordnade noden väljs som syskon mellan de två sammanslagna noderna
• Ta bort målnyckeln från den sammanslagna noden

Radera Operapseudokoden

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

Produktion:

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

Sammanfattning

• B Tree är en självbalanserande datastruktur för bättre sökning, infogning och radering av data från disken.
• B Träd regleras av den angivna graden
• B Trädnycklar och noder är ordnade i stigande ordning.
• Sökoperationen för B Tree är den enklaste, som alltid startar från roten och börjar kontrollera om målnyckeln är större eller mindre än nodvärdet.
• Infogningsoperationen för B Tree är ganska detaljerad, som först hittar en lämplig position för insättning av målnyckeln, infogar den, utvärderar giltigheten av B Tree mot olika fall och sedan omstrukturerar B Tree-noderna därefter.
• Borttagningsoperationen av B Tree söker först efter målnyckeln som ska raderas, tar bort den, utvärderar giltigheten baserat på flera fall som minimum- och maximumnycklar för målnoden, syskon och förälder.