Hovedforskjell: I datamaskiner er de binære trærne datastrukturer som lagrer dataene, og tillater brukeren å få tilgang til, søke, sette inn og slette dataene i algoritmisk tid. Forskjellen mellom et B og B + -treet er at i et B-tre kan nøklene og dataene lagres i både interne og bladnoder, mens i et B + tre kan dataene og nøklene kun lagres i bladknutene .
De binære trærne er balansert søketrær som er designet for å fungere godt på sekundære lagringsenheter med direkte tilgang, for eksempel magnetiske disker. Rudolf Bayer og Ed McCreight oppfant konseptet med et B-tre.
Et B-tre er et generalisert binært søketre, der en node kan ha mer enn to barn. Hver internnode i et B-tre inneholder et antall nøkler. Disse nøklene adskiller verdiene, og danner videre undertrærne. De interne nodene i et B-tre kan ha varierende antall barnnoder, som er ordnet innenfor et forhåndsdefinert område. På det tidspunktet når data blir satt inn eller fjernet fra en hvilken som helst knutepunkt, er det en endring i antall barnnoder. For å opprettholde det forhåndsdefinerte området kan interne noder knyttes sammen eller splittes. I et B-tre er det tillatt å velge en rekke barnnoter, som det forutbestemte området må opprettholdes for.
B-trærne trenger ikke å balanseres ofte i motsetning til andre selvbalanserende søketrær. Nodene i disse trærne er ikke alltid fulle; Derfor blir romene forbruket unødvendig i disse trærne som fører til sløsing med rom. Bare de nedre og øvre grensene på antall barnnoder er typisk fastsatt for en bestemt implementering. For eksempel, i et 2-3 B-tre (ofte ganske enkelt referert til som 2-3 tre), kan hver intern knute bare ha 2 eller 3 barnnoder.
I tillegg er B-treet optimalisert for systemer som leser og skriver store datablokker. Det brukes vanligvis i databaser og filsystemer. I B-treet holdes alle noder på samme balanse dyp fra rotknutene. Disse dypene øker sakte etter hvert som antall elementer øker; Dette resulterer i at alle bladnoder er en ekstra knute lenger unna roten. Videre er B-trærne mer fordelaktige sammenlignet med andre implementeringer i forhold til tiden som tar for å få tilgang til dataene.
Et B + -treet er et n-array-tre med en node, som består av et stort antall barn per knutepunkt. Roten kan være et blad eller en knute som inneholder mer enn to barn. Et B + tre består av en rot, indre noder og blader.
Et B + tre er det samme som et B-tre; Den eneste forskjellen er at i B + -træret er det lagt et ekstra nivå i bunnen med lenkede blad. I motsetning til B-treet inneholder hver knute i et B + tre også bare nøkler og ikke nøkkelverdier.
I tillegg måler balanseringsfaktoren eller rekkefølgen til et B + -tråd kapasiteten til de interne noder i et tre, det vil si antall noder de kan ha. Det faktiske antall barn for en node er begrenset for interne noder. Roten er imidlertid et unntak da det er tillatt å ha mer enn to antall barn. For eksempel, hvis rekkefølgen på et B + tre er 7, kan hver intern knute (unntatt rot) ha mellom 4 og 7 barn; mens roten kan ha mellom 2 og 7. Den primære verdien av B + -træret er å lagre data for effektiv gjenfinning i en blokkorientert lagringskontekst og spesielt filsystemer.
Den primære verdien av B + -træret er å lagre og vedlikeholde dataene, slik at dataene ikke går tapt. Denne tilnærmingen brukes spesielt i blokkorientert lagringskontekst og i enkelte filsystemer. Bladene, som er de nederste mest indeksblokkene, til B + -treet, er ofte knyttet til hverandre i en koblet liste; Derfor gjør dette utvalgsspørsmål eller en bestilt iterasjon gjennom blokkene enklere og mer effektiv. Videre er romfaktoren ikke bortkastet i B + trær. B + -træret gir et effektivt boligdataformatformat, noe som gjør dem enkle å få tilgang til og lagre. B + -trærne er spesielt nyttige som en databasesystemindeks, hvor dataene vanligvis ligger på en disk.
Sammenligning mellom B Tree og B + Tree:
B Tree | B + Tree | |
Korte webbeskrivelser | AB-tre er en organisasjonsstruktur for informasjonslagring og gjenfinning i form av et tre der alle terminale noder er i samme avstand fra basen, og alle ikke-terminale noder har mellom n og 2 n undertrær eller pekere (hvor n er et heltall). | B + tre er et n-array-tre med en variabel men ofte stort antall barn per knutepunkt. Et B + tre består av en rot, indre noder og blader. Roten kan være enten et blad eller en knute med to eller flere barn. |
Også kjent som | Balansert tre. | B pluss tre. |
Rom | På) | På) |
Søke | O (log n) | O (log b n) |
Sett inn | O (log n) | O (log b n) |
Slett | O (log n) | O (log b n) |
Oppbevaring | I et B-tre, søk nøkler og data lagret i interne eller blad noder. | I et B + tre, data lagret bare i blad noder. |
Data | Bladknutene til de tre butikkindikatorene til poster i stedet for faktiske poster. | Bladets knutepunkter lagrer den faktiske posten i stedet for pekere til poster. |
Rom | Disse trærne ødelegger plass | Der trær ikke kaster bort plass. |
Funksjon av bladnoder | I B-tre kan ikke bladknuten lagres ved hjelp av koblet liste. | I B + -treet blir bladnodedata bestilt i en sekvensiell lenket liste. |
Søker | Her blir søket vanskelig i B-treet, da data ikke finnes i bladknutepunktet. | Her er det lett å søke på data i et B + -treet fordi alle data er funnet i bladknutepunkter. |
Søk tilgjengelighet | Her i B tre er søket ikke så lett i forhold til et B + tre. | Her i B + tre blir søket lett. |
Redundant nøkkel | De lagrer ikke redundant søke nøkkel. | De lagrer redundant søke nøkkel. |
applikasjoner | De er en eldre versjon og er ikke så fordelaktig i forhold til B + trærne. | Mange databasesystemimplementorer foretrekker den enkle struktur av et B + tre. |