B-träd i datastruktur: Sök, infoga, ta bort

Vad är ett B-träd?

B Träd ä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. År 1972 introducerades denna metod först av McCreight och Bayer, som kallade den Height Balanced m-way Search Tree. Den hjälper dig att bevara data sorterade och möjliggör olika operationer som infogning, sökning och borttagning på kortare tid.

Regler för B-Tree

Här är viktiga regler för att skapa ett B-träd:

• Alla blad kommer att skapas på samma nivå.
• Ett B-träd bestäms av ett antal grader, vilket också kallas "ordning" (specificerat av en extern aktör, som en programmerare), kallat 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 nycklar som en rotnod, såväl som dess undernoder, kan innehålla beräknas med denna formel: m − 1. Till exempel:

  m = 4
  max keys: 4 − 1 = 3

• Varje nod, förutom rotnoden, måste innehålla ett minsta antal nycklar av [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 ett B-träd:

• Minskar antalet läsningar som görs på disken.
• B-träd kan enkelt optimeras för att justera deras 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. När dessa data överförs till huvudminnet (eller RAM) kallas de en datastruktur.
• När det gäller stora datamängder kräver sökning efter en enda post på disken att hela disken läses; 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å de block de finns i. Detta minskar tids- och minnesförbrukningen drastiskt.
• Eftersom vi har enorma data kan vi skapa indextabeller på flera nivåer.
• Ett flernivåindex kan utformas med hjälp av ett B-träd för keeping datan sorterad på ett självbalanserande sätt.

Sök Operation

Sökoperationen är den enklaste operationen på ett B-träd. Följande algoritm tillämpas:

• Låt nyckeln (värdet) som ska sökas vara "k".
• Börja söka från roten och gå rekursivt nedåt.
• Om k är mindre än rotvärdet, sök i det vänstra delträdet; om k är större än rotvärdet, sök i det högra delträdet.
• 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 ett B-träd är ett självbalanserande träd kan man 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.

I exemplet ovan:

• Sök efter nyckeln på lämplig position i noden.
• Sätt in nyckeln i målnoden och kontrollera reglerna.
• Har noden efter insättningen mer än eller lika med det minsta antalet nycklar, vilket är 1? I det här fallet, ja, det har den. Kontrollera nästa regel.
• Har noden efter insättningen fler än det maximala antalet nycklar, vilket är 3? I det här fallet nej, det har den inte. Det betyder att B-trädet inte bryter mot några regler och insättningen ä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 kommer den mellersta noden att väljas med vänsterbias eller högerbias.

I exemplet ovan:

• Noden har färre än maximum antal nycklar.
• 1 infogas bredvid 3, men regeln för stigande ordning bryts.
• För att åtgärda detta sorteras nycklarna.

På liknande sätt kan 13 och 2 enkelt infogas i noden eftersom de uppfyller regeln om "färre än maxantal 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 max antal nycklar.
• 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 infognings- och sökoperationerna. Följande algoritm gäller:

• Kör sökåtgärden och hitta målnyckeln i noderna.
• Tre villkor tillämpas baserat på målnyckelns placering, vilket förklaras i följande avsnitt.

Om målnyckeln finns i lövnoden

• Target finns i lövnoden, fler än min-nycklar. Att ta bort detta kommer inte att bryta mot egenskapen för B-trädet.
• Target finns i lövnoden och har min-nyckelnoder. Att ta bort detta kommer att bryta mot B-trädets egenskap.
• Målnoden kan låna en nyckel från den omedelbara vänstra noden eller den omedelbara högra noden (syskon).
• Syskonen kommer att säga ja om den har fler än det minsta antalet nycklar.
• Nyckeln lånas från föräldernoden, maxvärdet överförs till föräldernoden, maxvärdet från föräldernoden överförs till målnoden och målvärdet tas bort.
• Target finns i lövnoden, men inga syskon har mer än det minsta antalet nycklar: sök efter nyckeln, sammanfoga med syskon och det minsta antalet överordnade noder, det totala antalet nycklar kommer nu att vara mer än min, och målnyckeln kommer att ersättas med det minsta antalet föräldernoder.

Om målnyckeln finns i en intern nod

• Välj antingen en föregångare i ordnad ordning eller en efterföljare i ordnad ordning.
• Om det gäller en föregångare i rätt ordning kommer den maximala nyckeln från dess vänstra underträd att väljas.
• Om det gäller en efterföljare i rätt ordning kommer den lägsta nyckeln från dess högra underträd att väljas.
• Om målnyckelns föregångare i ordning har fler än min-nycklarna, kan den först då ersätta målnyckeln med maxvärdet för föregångaren i ordning.
• Om målnyckelns föregångare i ordning inte har fler än min-nycklar, leta efter den efterföljande ordningens minsta nyckel.
• 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 maximum-elementet i det föregående underträdet i ordning.
• Om målet, efter borttagning, har färre än min-nycklar, kommer målnoden att låna maxvärdet från sitt syskon via syskonets förälder.
• Förälderns maxvärde kommer att tas av målet, men med noderna med syskonets maxvärde.

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

Diagrammet ovan visar olika fall av borttagningsoperationen 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 en nod kan ha är 5. Medan det minsta och maximala antalet nycklar en nod kan ha är 2 respektive 4.

I exemplet ovan:

• Målnoden har målnyckeln som ska tas bort.
• Målnoden har fler nycklar än det minsta antalet nycklar.
• Ta bara bort nyckeln.

I exemplet ovan:

• Målnoden har nycklar som är lika med minimiantalet nycklar, så vi kan inte radera den direkt eftersom det kommer att bryta mot villkoren.

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

• Målnoden lånar en nyckel från ett omedelbart syskon, i det här fallet föregångaren 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 ordning 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 lånar en nyckel från ett omedelbart syskon, i det här fallet efterföljaren i ordning (höger syskon), eftersom dess föregångare i ordning (vänster syskon) har nycklar som är lika med minsta antal 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 ingen syskon som kan ge sin nyckel till målnoden. Därför krävs sammanslagning. Se proceduren för att ta bort en sådan nyckel:

• Sammanfoga målnoden med någon av dess omedelbara syskon tillsammans med den överordnade nyckeln.
• Nyckeln från den överordnade noden väljs som sitter mellan de två sammanslagna noderna.
• Ta bort målnyckeln från den sammanslagna noden.

Radera Operation Pseudo Code

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.

Vanliga frågor