Innan man förstår B träd och B+ träd skillnader bör vi känna till B-trädet och B+-trädet separat.

Vad är B-trädet?

B träd är ett självbalanserande träd, och det är ett m-vägsträd där m definierar trädets ordning. Btree är en generalisering av Binärt sökträd där en nod kan ha mer än en nyckel och fler än två barn beroende på värdet av m . I B-trädet specificeras data i en sorterad ordning med lägre värden i det vänstra underträdet och högre värden i det högra underträdet.

hur man returnerar array i java

Egenskaper för B-träd

Följande är egenskaperna för B-trädet:

• I B-trädet måste alla lövnoderna vara på samma nivå, medan, i fallet med ett binärt träd, lövnoderna kan vara på olika nivåer.

Låt oss förstå denna egenskap genom ett exempel.

I ovanstående träd är alla bladnoder inte på samma nivå, men de har de yttersta två barnen. Därför kan vi säga att ovanstående träd är en binärt träd men inte ett B-träd.

• Om Bträdet har en ordning på m, kan varje nod ha maximalt m När det gäller minsta barn har lövnoderna noll barn, rotnoden har två barn och de interna noderna har ett tak på m/2.
• Varje nod kan ha maximala (m-1) nycklar. Till exempel, om värdet på m är 5 är det maximala värdet för nycklar 4.
• Rotnoden har minst en nyckel, medan alla andra noder utom rotnoden har (tak på m/2 minus - 1) minimumnycklar.
• Om vi ​​utför infogning i B-trädet, så infogas noden alltid i bladnoden.

Anta att vi vill skapa ett B-träd av ordning 3 genom att infoga värden från 1 till 10.

Steg 1: Först skapar vi en nod med 1 värde som visas nedan:

Steg 2: Nästa element är 2, som kommer efter 1 som visas nedan:

Steg 3: Nästa element är 3, och det infogas efter 2 som visas nedan:

Eftersom vi vet att varje nod kan ha max 2 nycklar, så kommer vi att dela denna nod genom mittelementet. Mittelementet är 2, så det flyttar till sin förälder. Noden 2 har ingen förälder, så den blir rotnoden enligt nedan:

Steg 4: Nästa element är 4. Eftersom 4 är större än 2 och 3, så läggs det till efter 3:an som visas nedan:

Steg 5: Nästa element är 5. Eftersom 5 är större än 2, 3 och 4 så kommer det att läggas till efter 4 som visas nedan:

Eftersom vi vet att varje nod kan ha max 2 nycklar, så kommer vi att dela denna nod genom mittelementet. Mittelementet är 4, så det flyttar till sin förälder. Föräldern är nod 2; därför kommer 4 att läggas till efter 2 som visas nedan:

Steg 6: Nästa element är 6. Eftersom 6 är större än 2, 4 och 5, så kommer 6 efter 5 som visas nedan:

Steg 7: Nästa element är 7. Eftersom 7 är större än 2, 4, 5 och 6, så kommer 7 efter 6 som visas nedan:

Eftersom vi vet att varje nod kan ha max 2 nycklar, så kommer vi att dela denna nod genom mittelementet. Det mellersta elementet är 6, så det flyttas till sin förälder som visas nedan:

Men 6 kan inte läggas till efter 4 eftersom noden kan ha max 2 nycklar, så vi delar upp denna nod genom mittelementet. Mittelementet är 4, så det flyttar till sin förälder. Eftersom nod 4 inte har någon förälder kommer nod 4 att bli en rotnod enligt nedan:

Vad är ett B+-träd?

De B+ träd är också känt som ett avancerat självbalanserat träd eftersom varje väg från trädets rot till trädets blad har samma längd. Här betyder samma längd att alla bladnoder uppträder på samma nivå. Det kommer inte att hända att några av lövnoderna förekommer på tredje nivån och några av dem på andra nivån.

Ett B+-trädindex anses vara ett index på flera nivåer, men B+-trädstrukturen liknar inte de sekventiella indexfilerna på flera nivåer.

Varför används B+-trädet?

Ett B+-träd används för att lagra posterna mycket effektivt genom att lagra posterna på ett indexerat sätt med hjälp av den B+-trädindexerade strukturen. Tack vare indexeringen på flera nivåer blir dataåtkomsten snabbare och enklare.

B+ träd Nodstruktur

Nodstrukturen för B+-trädet innehåller pekare och nyckelvärden som visas i bilden nedan:

Som vi kan observera i ovanstående B+-trädnodstruktur att den innehåller n-1 nyckelvärden (k₁till k_n-1) och n pekare (s₁topp_n).

Söknyckelvärdena som placeras i noden hålls i sorterad ordning. Alltså, om jagij.

Begränsning av olika typer av noder

Låt 'b' vara ordningen för B+-trädet.

Non som inte är löv

Låt 'm' representera antalet barn i en nod, då kan relationen mellan trädets ordning och antalet barn representeras som:

Låt k representera söknyckelvärdena. Relationen mellan trädets ordning och söknyckeln kan representeras som:

Eftersom vi vet att antalet pekare är lika med söknyckelvärdena plus 1, så matematiskt kan det skrivas som:

Antal pekare (eller barn) = Antal söktangenter + 1

Därför skulle det maximala antalet pekare vara 'b', och det minsta antalet pekare skulle vara takfunktionen för b/2.

Bladnod

En lövnod är en nod som uppträder på den sista nivån av B+-trädet, och varje lövnod använder endast en pekare för att ansluta med varandra för att ge den sekventiella åtkomsten på lövnivån.

I lövnod är det maximala antalet barn:

Det maximala antalet söknycklar är:

Rotnod

Det maximala antalet barn i fallet med rotnoden är: b

Minsta antal barn är: 2

exempel på binärt sökträd

Specialfall i B+-träd

Fall 1: Om rotnoden är den enda noden i trädet. I det här fallet blir rotnoden lövnoden.

I det här fallet är det maximala antalet barn 1, det vill säga själva rotnoden, medan det minsta antalet barn är b-1, vilket är samma som för en lövnod.

Representation av en lövnod i B+-träd

I figuren ovan, '.' representerar pekaren, medan 10, 20 och 30 är nyckelvärdena. Pekaren innehåller adressen där nyckelvärdet är lagrat, som visas i figuren ovan.

Exempel på B+-träd

I figuren ovan innehåller noden tre nyckelvärden, dvs. 9, 16 och 25. Pekaren som visas före 9, innehåller nyckelvärdena mindre än 9 representerade av k_i. Pekaren som visas före 16, innehåller nyckelvärden större än eller lika med 9 men mindre än 16 representerade av kj. Pekaren som visas före 25, innehåller nyckelvärden som är större än eller lika med 16 men mindre än 25 representerade av k_n.

Skillnader mellan B-träd och B+-träd

Följande är skillnaderna mellan B-trädet och B+-trädet: