I följande handledning kommer vi att lära oss om B Tree-datastrukturen och överväga att visualisera den.
Så, låt oss börja.
Vad är ett B-träd?
De B Träd är en speciell typ av flervägssökträd , allmänt känd som M-väg träd, som balanserar sig själv. På grund av sin balanserade struktur används dessa träd ofta för att driva och hantera enorma databaser och förenkla sökningar. I ett B-träd kan varje nod ha högst n underordnade noder. B Tree är ett exempel på Multilevel Indexing i ett Database Management System (DBMS). Blad- och interna noder kommer båda att ha postreferenser. B-träd är känt som Balanced Stored Tree eftersom alla lövnoder är på samma nivå.
Följande diagram är ett exempel på ett B-träd:
Figur 1. A B-träd med ordning 3
Förstå reglerna för B-trädet
Följande är de viktiga egenskaperna hos ett B-träd:
- Alla bladnoder är på samma nivå.
- B-trädets datastruktur definieras av termen minimigrad 'd'. Värdet på 'd' beror på storleken på diskblocket.
- Varje nod, exklusive roten, måste bestå av minst d-1-nycklar. Rotnoden kan bestå av minst 1 nyckel.
- Alla noder (inklusive rotnoden) får bestå av högst (2d-1) nycklar.
- Antalet barn i en nod är lika med tillägg av antalet nycklar som finns i den och .
- Alla nycklar i en nod sorteras i stigande ordning. Barnet mellan två nycklar, k1 och k2, består av alla nycklar som sträcker sig mellan k1 respektive k2.
- Till skillnad från det binära sökträdet, växer B-trädets datastruktur och krymper från roten. Medan det binära sökträdet växer nedåt och krymper nedåt.
- I likhet med andra självbalanserade binära sökträd är tidskomplexiteten för B-trädets datastruktur för operationer som sökning, infogning och radering O(log?n) .
- Införandet av en nod i B-trädet sker endast vid lövnoden.
Låt oss betrakta följande exempel på ett B-träd med minsta ordning 5.
Figur 2. A B Ordningsträd 5
Notera: Värdet på den minsta beställningen är mycket mer än 5 i en praktisk B-träd.
I diagrammet ovan kan vi observera att alla lövnoder är på samma nivå, och alla icke-lövnoder har inget tomt underträd och består av nycklar en mindre än antalet barn.
Den fastställda formuleringen av B-trädets regler:
Varje B-träd beror på ett positivt konstant heltal känt som MINIMUM , som används för att bestämma antalet dataelement som kan hållas i en enda nod.
hur många veckor på en månad
Regel 1: Roten kan ha så få som bara ett dataelement (eller till och med inga dataelement om det inte heller är några barn); varannan nod har minst MINIMUM dataelement.
Regel 2: Det maximala antalet dataelement som lagras i en nod är två gånger värdet av MINIMUM .
Regel 3: Dataelementen för varje nod i B-trädet lagras i en delvis fylld array, sorterad från det minsta dataelementet (vid index 0 ) till det största dataelementet (vid den slutliga använda positionen för arrayen).
Regel 4: Det totala antalet underträd under en icke-bladsnod är alltid en mer än antalet dataelement i den noden.
- underträd 0, underträd 1,...
Regel 5: Med avseende på alla icke-bladsnoder:
- Ett dataelement vid index är större än alla dataelement i underträdets nummer i av noden, och
- Ett dataelement vid index är mindre än alla dataelement i underträdets nummer i+1 av noden.
Regel 6: Varje löv i ett B-träd har samma djup. Således säkerställer det att ett B-träd förhindrar problemet med ett obalanserat träd.
Operationer på en B Tree-datastruktur
För att säkerställa att ingen av egenskaperna för en B Tree-datastruktur kränks under operationen, kan B-trädet delas eller sammanfogas. Följande är några operationer som vi kan utföra på ett B-träd:
- Söka efter ett dataelement i B Tree
- Infogning av ett dataelement i B Tree
- Radering av ett dataelement i B Tree
Sökoperation på ett B-träd
Att söka efter ett element i ett B-träd liknar det i ett binärt sökträd. Men istället för att fatta ett tvåvägsbeslut (vänster eller höger) som ett binärt sökträd, fattar ett B-träd ett m-vägsbeslut vid varje nod där m är antalet barn i noden.
Steg för att söka efter ett dataelement i ett B-träd:
Steg 1: Sökningen börjar från rotnoden. Jämför sökelementet k med roten.
Steg 1.1: Om rotnoden består av elementet k kommer sökningen att slutföras.
Steg 1.2: Om elementet k är mindre än det första värdet i roten kommer vi att flytta till barnet längst till vänster och söka efter barnet rekursivt.
Steg 1.3.1: Om roten bara har två barn kommer vi att flytta till barnet längst till höger och rekursivt söka efter barnnoderna.
Steg 1.3.2: Om roten har fler än två nycklar kommer vi att söka efter resten.
Steg 2: Om elementet k inte hittas efter att ha korsat hela trädet, så finns inte sökelementet i B-trädet.
Låt oss visualisera stegen ovan med hjälp av ett exempel. Antag att vi ville söka efter en nyckel k=34 i följande B-träd:
Figur 3.1. Ett givet B-träd
- Först kommer vi att kontrollera om nyckeln k = 34 är vid rotnoden. Eftersom nyckeln inte är vid roten kommer vi att gå vidare till dess underordnade noder. Vi kan också observera att rotnoden har två barn; därför kommer vi att jämföra det erforderliga värdet mellan de två nycklarna.
Figur 3.2. Nyckeln k finns inte i roten - Nu när vi kan lägga märke till att nyckeln k är större än rotnoden, d.v.s. 30, kommer vi att fortsätta med rotens högra underordnade.
Figur 3.3. Nyckeln k > 30, flytta till höger barn - Vi kommer nu att jämföra nyckeln k med värdena som finns på noden, dvs 40 respektive 50. Eftersom nyckeln k är mindre än den vänstra tangenten, dvs 40, kommer vi att flytta till nodens vänstra underordnade.
Figur 3.4. Nyckeln k<40, move to left child< li> - Eftersom värdet i det vänstra barnet på 40 är 34, vilket är det obligatoriska värdet, kan vi dra slutsatsen att nyckeln hittas och sökoperationen är klar.
Figur 3.4. Nyckeln k = 34, det vänstra barnet på 40
Vi jämförde nyckeln med fyra olika värden i exemplet ovan tills vi hittade den. Sålunda är tidskomplexiteten som krävs för sökoperationen i ett B-träd O(log?n) .
Infoga operation på ett B-träd
När vi infogar ett dataelement i ett B-träd måste vi först kontrollera om det elementet redan finns i trädet eller inte. Om dataelementet hittas i B-trädet, sker inte infogningsoperationen. Men om så inte är fallet kommer vi att gå vidare med infogningen. Det finns två scenarier som måste tas om hand när ett element infogas i bladnoden:
Steg för att infoga ett dataelement i ett B-träd:
Steg 1: Vi börjar med att beräkna det maximala antalet nycklar i noden på basis av B-trädets ordning.
Steg 2: Om trädet är tomt tilldelas en rotnod, och vi kommer att infoga nyckeln som fungerar som rotnod.
Steg 3: Vi kommer nu att söka i den tillämpliga noden för infogning.
Steg 4: Om noden är full:
Steg 4.1: Vi kommer att infoga dataelementen i stigande ordning.
Steg 4.2: Om dataelementen är större än det maximala antalet nycklar kommer vi att dela upp hela noden vid medianen.
Steg 4.3: Vi kommer att trycka mediantangenten uppåt och dela upp vänster och höger tangenter som vänster och höger barn.
Steg 5: Om noden inte är full kommer vi att infoga noden i stigande ordning.
Låt oss visualisera stegen ovan med hjälp av ett exempel. Antag att vi måste skapa ett B-träd av ordning 4. Dataelementen som måste infogas i B-trädet är 5,3,21,11,1,16,8,13,4 och 9 .
- Eftersom m är lika med 3, är det maximala antalet nycklar för en nod = m-1 = 3-1 = 2 .
- Vi börjar med att infoga 5 i det tomma trädet.
Figur 4.1. Lägger in 5 - Vi kommer nu att infoga 3 i trädet. Eftersom 3 är mindre än 5 kommer vi att infoga 3 till vänster om 5 i samma nod.
Figur 4.2. Lägger in 3 - Vi kommer nu att infoga 21 i trädet, och eftersom 21 är större än 5, kommer det att infogas till höger om 5 i samma nod. Men eftersom vi vet att det maximala antalet nycklar i noden är 2, kommer en av dessa nycklar att flyttas till en nod ovanför för att dela upp den. Således kommer 5, det mellersta dataelementet, att flytta uppåt, och 3 och 21 kommer att bli dess vänstra respektive högra noder.
Figur 4.3. Lägger in 21 - Nu är det dags att infoga nästa dataelement, dvs 11, som är större än 5 men mindre än 21. Därför kommer 11 att infogas som en nyckel till vänster om noden som består av 21 som en nyckel.
Figur 4.4. Lägger in 11 - På liknande sätt kommer vi att infoga nästa dataelement 1 i trädet, och som vi kan observera är 1 mindre än 3; därför kommer den att infogas som en nyckel till vänster om noden som består av 3 som en nyckel.
Figur 4.5. Lägger in 1 - Nu kommer vi att infoga dataelement 16 i trädet, vilket är större än 11 men mindre än 21. Antalet nycklar i den noden överstiger dock det maximala antalet nycklar. Därför kommer noden att delas och flytta mitttangenten till roten. Följaktligen kommer 16 att infogas till höger om 5:an och dela 11 och 21 i två separata noder.
Figur 4.6. Lägger in 16 - Dataelementet 8 kommer att infogas som en nyckel till vänster om 11.
Figur 4.7. Lägger in 8 - Vi kommer att infoga 13 i trädet, vilket är mindre än 16 och större än 11. Därför bör dataelement 13 infogas till höger om noden som består av 8 och 11. Men eftersom det maximala antalet nycklar i trädet kan endast vara 2 kommer en uppdelning att ske, vilket flyttar det mellersta dataelementet 11 till ovanstående nod och 8 och 13 till två separata noder. Nu kommer ovanstående nod att bestå av 5, 11 och 16, vilket återigen överskrider det maximala nyckelantalet. Därför kommer det att ske ytterligare en uppdelning, vilket gör dataelementet 11 till rotnoden med 5 och 16 som underordnade.
Figur 4.8. Lägger in 13 - Eftersom dataelementet 4 är mindre än 5 men större än 3, kommer det att infogas till höger om noden som består av 1 och 3, vilket kommer att överskrida det maximala antalet nycklar i en nod igen. Därför kommer ett spill att inträffa igen och flyttar 3:an till den övre noden bredvid 5.
Figur 4.9. Lägger in 4 - Till sist kommer dataelementet 9, som är större än 8 men mindre än 11, att infogas till höger om noden som består av 8 som en nyckel.
Figur 4.10. Lägger in 9
I exemplet ovan har vi gjort olika jämförelser. Det första värdet infogades direkt i trädet; efter det måste varje värde jämföras med de tillgängliga noderna i det trädet. Tidskomplexiteten för infogningsoperationen i ett B-träd beror på antalet noder och .
Ta bort operation på ett B-träd
Att ta bort ett dataelement på ett B-träd innehåller tre primära händelser:
- Genom att söka på noden där nyckeln som ska raderas finns,
- Ta bort nyckeln och
- Balansera trädet vid behov.
När ett element tas bort från trädet kan ett tillstånd som kallas underflöde uppstå. Underflöde uppstår när en nod består av färre än det minsta antalet nycklar; det borde hålla.
Följande är några termer som måste förstås innan du visualiserar borttagnings-/borttagningsåtgärden:
Följande är tre framträdande fall av raderingsoperationen i ett B-träd:
Fall 1: Borttagning/borttagning av nyckeln ligger i Leaf-noden - Detta ärende är vidare uppdelat i två olika fall:
1. Raderingen/borttagningen av nyckeln bryter inte mot egenskapen för det minsta antal nycklar som en nod ska ha.
Låt oss visualisera detta fall med hjälp av ett exempel där vi tar bort nyckel 32 från följande B-träd.
Figur 4.1: Ta bort en lövnodnyckel (32) från B-trädet
Som vi kan observera strider inte mot ovanstående egenskap att ta bort 32 från detta träd.
2. Raderingen/borttagningen av nyckeln bryter mot egenskapen för det minsta antal nycklar som en nod ska ha. I det här fallet måste vi låna en nyckel från dess närmaste syskonnod i ordningen från vänster till höger.
Först ska vi besöka det närmaste Vänstersyskonet. Om den vänstra syskonnoden har mer än ett minsta antal nycklar, kommer den att låna en nyckel från denna nod.
Annars kommer vi att kontrollera för att låna från den närmaste högra syskonnoden.
Låt oss nu visualisera detta fall med hjälp av ett exempel där vi tar bort 31 från ovanstående B-träd. Vi kommer att låna en nyckel från vänster syskonnod i detta fall.
Figur 4.2: Ta bort en lövnodnyckel (31) från B-trädet
Om båda de närliggande syskonnoderna redan består av ett minsta antal nycklar, kommer vi att slå samman noden med antingen den vänstra syskonnoden eller den högra. Denna sammanslagningsprocess görs genom föräldernoden.
Låt oss visualisera igen genom att ta bort nyckeln 30 från ovanstående B-träd.
Figur 4.3: Ta bort en lövnodnyckel (30) från B-trädet
Fall 2: Borttagning/borttagning av nyckeln ligger i non-Leaf-noden - Detta fall är ytterligare uppdelat i olika fall:
1. Noden som inte är löv/intern, som tas bort, ersätts av en föregångare i ordning om den vänstra underordnade noden har fler än det minsta antalet nycklar.
hög och hög sort
Låt oss visualisera detta fall med hjälp av ett exempel där vi tar bort nyckeln 33 från B-trädet.
Figur 4.4: Ta bort en lövnodnyckel (33) från B-trädet
2. Noden som inte är löv/intern, som tas bort, ersätts av en efterföljare i ordning om den högra underordnade noden har fler än det minsta antalet nycklar.
Om något av barnen har ett minsta antal nycklar, kommer vi att slå samman Vänster och Höger underordnade noder.
Låt oss visualisera detta fall genom att ta bort nyckeln 30 från B-trädet.
Figur 4.5: Ta bort en lövnodnyckel (30) från B-trädet
Efter sammanslagning, om föräldernoden har mindre än det minsta antalet nycklar, kan man leta efter syskonen, som i Fall 1 .
Fall 3: I följande fall krymper trädets höjd. Om målnyckeln ligger i en intern nod, och borttagningen av nyckeln leder till färre nycklar i noden (vilket är mindre än det minsta nödvändiga), leta sedan efter föregångaren i ordning och efterföljare i ordning. Om båda barnen har ett minsta antal nycklar kan lån inte ske. Det här leder till Fall 2(3) d.v.s. sammanslagning av barnnoderna.
Vi ska återigen leta efter syskon för att låna nyckel. Men om syskonen också består av ett minsta antal nycklar, kommer vi att slå ihop noden med syskonen tillsammans med föräldernoden och ordna de underordnade noderna enligt kraven (stigande ordning).
Låt oss visualisera detta fall med hjälp av ett exempel där vi tar bort dataelementet 10 från det givna B-trädet.
Figur 4.6: Ta bort en lövnodnyckel (10) från B-trädet
Tidskomplexiteten i exemplen ovan varierar beroende på varifrån nyckeln behöver raderas. Sålunda är tidskomplexiteten för raderingsoperationen i ett B-träd O(log?n) .
Slutsatsen
I den här handledningen har vi lärt oss om B-trädet och visualiserat dess olika funktioner med olika exempel. Vi har också förstått några grundläggande egenskaper och regler för B-trädet.