Huvudskillnad: I datorer är binära träd träddatastrukturer som lagrar data och tillåter användaren att komma åt, söka, infoga och radera data vid algoritmisk tid. Skillnaden mellan ett B och B + träd är att i ett B-träd kan nycklarna och data lagras i både interna och lövnoder, medan i ett B + träd kan data och nycklar endast lagras i bladnodarna .
De binära träden är balanserade sökträd som är utformade för att fungera bra på sekundära lagringsenheter med direkt åtkomst som magnetdiskar. Rudolf Bayer och Ed McCreight uppfann konceptet om ett B-träd.
Ett B-träd är ett generaliserat binärt sökträd, där någon nod kan ha mer än två barn. Varje intern nod i ett B-träd innehåller ett antal nycklar. Dessa nycklar skiljer värdena, och vidare bildar delstromen. De interna noderna i ett B-träd kan ha ett varierande antal barnnoder som är ordnade inom ett fördefinierat område. Vid den tidpunkt då data infogas eller tas bort från någon nod, ändras antalet barnnodar. För att upprätthålla det fördefinierade området kan interna noder förenas eller delas. I ett B-träd är ett antal barnnoder tillåtna, varför det fördefinierade området måste bibehållas.
B-träd behöver inte ombalanseras ofta, till skillnad från andra självbalanserade sökträd. Noderna i dessa träd är inte alltid fulla; Därför förbrukas utrymmena onödiga i dessa träd som leder till slöseri med rymden. Endast de undre och övre gränserna på antalet barnnoter är vanligtvis fixade för en viss implementering. Till exempel, i ett 2-3 B-träd (ofta helt enkelt betecknat som 2-3 träd) kan varje intern nod ha endast 2 eller 3 barn nod.
Dessutom optimeras B-trädet för system som läser och skriver stora datablock. Det används vanligtvis i databaser och filsystem. I B-trädet hålls alla noder på samma balanseringsdjup från rotnoderna. Dessa djup ökar långsamt, eftersom antalet element ökar; detta resulterar i att alla lövnoter är en ytterligare nod längre bort från roten. Vidare är B-träden mer fördelaktiga jämfört med andra implementeringar i förhållande till tiden som tar sig för att komma åt data.
Ett B + träd är ett n-array-träd med en nod, som består av ett stort antal barn per nod. Roten kan vara ett blad eller en nod som innehåller mer än två barn. Ett B + träd består av en rot, inre noder och löv.
Ett B + träd är detsamma som ett B-träd; Den enda skillnaden är att i B + trädet finns en extra nivå som läggs längst ner med länkade blad. Också i motsats till B-trädet innehåller varje nod i ett B + -tråd bara nycklar och inte nyckelvärdespar.
Dessutom mäter balanseringsfaktorn eller ordningen för ett B + -tråd kapaciteten för de interna noderna i ett träd, det vill säga antalet noder de kan ha. Det faktiska antalet barn för en nod är begränsat för interna noder. Roten är dock ett undantag eftersom det är tillåtet att ha fler än två antal barn. Om exempelvis en B + träds ordning är 7, kan varje intern nod (förutom roten) ha mellan 4 och 7 barn; medan roten kan ha mellan 2 och 7. Det primära värdet för B + -trädet är att lagra data för effektiv återhämtning i ett blockorienterat lagringsförhållande och i synnerhet filsystem.
Det primära värdet på B + -trädet är att lagra och behålla data så att data inte går förlorade. Detta tillvägagångssätt tillämpas särskilt i blockorienterat lagringskontext och i vissa specifika filsystem. Bladen, som är de längsta indexblocken, av B + -trädet är ofta länkade till varandra i en länkad lista; Därigenom gör det en radfrågor eller en beställd iteration genom blocken enklare och effektivare. Dessutom är rymdfaktorn inte bortkastad i B + träd. B + -treet ger ett effektivt format för bostadsdata struktur, vilket gör dem enkla att komma åt och lagra. B + -trena är särskilt användbara som databas-systemindex, där data vanligtvis ligger på en disk.
Jämförelse mellan B Tree och B + Tree:
B Tree | B + träd | |
Korta webbbeskrivningar | AB-träd är en organisationsstruktur för informationslagring och -hämtning i form av ett träd där alla terminala noder ligger i samma avstånd från basen, och alla icke-terminala noder har mellan n och 2 n deltrar eller pekare (var n är ett heltal). | B + träd är ett n-array-träd med en variabel men ofta stort antal barn per nod. Ett B + träd består av en rot, inre noder och löv. Roten kan vara antingen ett blad eller en nod med två eller flera barn. |
Också känd som | Balanserat träd. | B plus träd. |
Rymden | På) | På) |
Sök | O (log n) | O (log bn ) |
Föra in | O (log n) | O (log bn ) |
Radera | O (log n) | O (log bn ) |
Lagring | I ett B-träd, söknycklar och data lagrade i interna eller lövnoder. | I ett B + träd, data som endast lagras i lövnoter. |
Data | Bladnodarna i de tre butikspekarna ska registreras i stället för faktiska poster. | Trädets lönodder lagrar själva posten istället för pekar på poster. |
Rymden | Dessa träd slösar utrymme | Där slösar inte träd på plats. |
Funktion av bladnoder | I B-träd kan lösnoden inte lagras med hjälp av länkad lista. | I B + träd beställs bladnoddata i en sekventiell länkad lista. |
Sökande | Här blir det svårt att söka i B-träd, eftersom data inte finns i bladnodet. | Här är det lätt att söka efter data i ett B + -träd eftersom alla data finns i bladnodder. |
Sök tillgänglighet | Här i B-trädet är sökningen inte så lätt jämfört med ett B + -träd. | Här i B + träd blir sökningen lätt. |
Redundant nyckel | De lagrar inte redundanta söknycklar. | De lagrar redundanta söknycklar. |
tillämpningar | De är en äldre version och är inte så fördelaktiga jämfört med B + träden. | Många databas system implementatorer föredrar strukturell enkelhet av ett B + träd. |
