Belangrijk verschil: in computers zijn de binaire bomen boomgegevensstructuren die de gegevens opslaan en de gebruiker in staat stellen om op het algoritmische tijdstip de gegevens te openen, te doorzoeken, in te voegen en te verwijderen. Het verschil tussen een B- en B + -boom is dat in een B-tree de sleutels en gegevens kunnen worden opgeslagen in zowel de interne als de bladknooppunten, terwijl in een B + -boom de gegevens en sleutels alleen in de bladknooppunten kunnen worden opgeslagen .
De binaire bomen zijn uitgebalanceerde zoekbomen die zijn ontworpen om goed te werken op directe toegang tot secundaire opslagapparaten zoals magnetische schijven. Rudolf Bayer en Ed McCreight hebben het concept van een B-tree uitgevonden.
Een B-tree is een gegeneraliseerde binaire zoekboom, waarin elk knooppunt meer dan twee kinderen kan hebben. Elk intern knooppunt in een B-tree bevat een aantal sleutels. Deze sleutels scheiden de waarden en vormen verder de subbomen. De interne knooppunten in een B-structuur kunnen variabele aantallen onderliggende knooppunten hebben, die binnen een vooraf gedefinieerd bereik zijn gerangschikt. Op het moment dat gegevens worden ingevoegd of verwijderd van een willekeurig knooppunt, is er een verandering in het aantal onderliggende knooppunten. Om het vooraf gedefinieerde bereik te behouden, kunnen interne knooppunten worden gekoppeld of gesplitst. In een B-tree is een bereik van onderliggende nodes toegestaan, waardoor het vooraf gedefinieerde bereik moet worden behouden.
De B-bomen hoeven niet vaak opnieuw te worden gebalanceerd in tegenstelling tot andere zelfbalancerende zoekbomen. De knooppunten in deze bomen zijn niet altijd vol; vandaar dat de ruimtes onnodig worden geconsumeerd in deze bomen die leiden tot verspilling van ruimte. Alleen de onder- en bovengrenzen van het aantal onderliggende knooppunten worden doorgaans vastgesteld voor een bepaalde implementatie. Bijvoorbeeld, in een 2-3 B-tree (vaak eenvoudigweg een 2-3-boom genoemd), kan elk intern knooppunt slechts 2 of 3 onderliggende nodes hebben.
Bovendien is de B-tree geoptimaliseerd voor systemen die grote datablokken lezen en schrijven. Het wordt vaak gebruikt in databases en bestandssystemen. In de B-structuur worden alle knooppunten op dezelfde in evenwicht brengende diepten van de basisknooppunten gehouden. Deze diepten nemen langzaam toe naarmate het aantal elementen toeneemt; dit resulteert erin dat alle bladknooppunten nog een knoop verder van de wortel zijn. Verder zijn de B-trees voordeliger in vergelijking met andere implementaties wat betreft de tijd die nodig is om toegang te krijgen tot de data.
Een B + -boom is een n-array-structuur met een knooppunt, dat uit een groot aantal kinderen per knooppunt bestaat. De wortel kan een blad zijn of een knooppunt dat meer dan twee kinderen bevat. Een B + -boom bestaat uit een wortel, interne knopen en bladeren.
Een B + boom is hetzelfde als een B-boom; het enige verschil is dat er in de B + -boom aan de onderkant een extra niveau is toegevoegd met gekoppelde bladeren. In tegenstelling tot de B-structuur bevat elk knooppunt in een B + -boom alleen sleutels en geen sleutel / waarde-paren.
Bovendien meet de balansfactor of de volgorde van een B + -boom de capaciteit voor de interne knooppunten in een boom, dwz het aantal knooppunten dat ze kunnen hebben. Het werkelijke aantal kinderen voor een knooppunt is beperkt voor interne knooppunten. De root is echter een uitzondering omdat het toegestaan is om meer dan twee kinderen te hebben. Als de volgorde van een B + -boom bijvoorbeeld 7 is, kan elk intern knooppunt (behalve de hoofdmap) tussen 4 en 7 kinderen hebben; terwijl de root mogelijk tussen 2 en 7 heeft. De primaire waarde van de B + -structuur ligt in het opslaan van gegevens voor efficiënt ophalen in een blokgeoriënteerde opslagcontext en in het bijzonder bestandssystemen.
De primaire waarde van de B + -boom ligt in het opslaan en onderhouden van de gegevens, zodat de gegevens niet verloren gaan. Deze benadering wordt vooral toegepast in blokgeoriënteerde opslagcontext en in sommige specifieke bestandssystemen. De bladeren, die de onderste indexblokken zijn, van de B + -boom worden vaak aan elkaar gekoppeld in een gekoppelde lijst; vandaar dit maakt het bereik vragen of een geordende iteratie door de blokken eenvoudiger en efficiënter. Bovendien wordt de ruimtefactor niet verspild in B + bomen. De B + -boom biedt een efficiënt gegevensstructuurformat voor de behuizing, waardoor ze eenvoudig kunnen worden geopend en opgeslagen. De B + -bomen zijn met name handig als index van een databasesysteem, waarbij de gegevens zich meestal op een schijf bevinden.
Vergelijking tussen B Tree en B + Tree:
B Boom | B + Tree | |
Korte webbeschrijvingen | AB-structuur is een organisatiestructuur voor het opslaan en ophalen van informatie in de vorm van een boom waarin alle eindknopen zich op dezelfde afstand van de basis bevinden en alle niet-eindknopen tussen n en 2 n subbomen of aanwijzers hebben (waar n is een geheel getal). | B + tree is een n-array-structuur met een variabel maar vaak groot aantal kinderen per knooppunt. Een B + -boom bestaat uit een wortel, interne knopen en bladeren. De wortel kan een blad zijn of een knooppunt met twee of meer kinderen. |
Ook gekend als | Evenwichtige boom. | B plus boom. |
Ruimte | Op) | Op) |
Zoeken | O (log n) | O (log b n) |
invoegen | O (log n) | O (log b n) |
Verwijder | O (log n) | O (log b n) |
opslagruimte | In een B-boom, zoeksleutels en gegevens die zijn opgeslagen in interne of bladknooppunten. | In een B + -structuur worden gegevens alleen opgeslagen in leaf-nodes. |
Gegevens | De bladknooppunten van de drie opslagaanwijzers naar records in plaats van werkelijke records. | De bladknooppunten van de boom slaan de werkelijke record op in plaats van verwijzingen naar records. |
Ruimte | Deze bomen verspillen ruimte | Er bomen verspillen geen ruimte. |
Functie van bladknopen | In de B-structuur kan het knooppunt niet worden opgeslagen met behulp van de gekoppelde lijst. | In B + boom worden leaf-knooppuntgegevens geordend in een sequentieel gekoppelde lijst. |
Zoeken | Hier wordt het zoeken in B-tree moeilijk omdat gegevens niet in het leaf-knooppunt te vinden zijn. | Hier is het zoeken naar gegevens in een B + -boom erg eenvoudig omdat alle gegevens worden gevonden in leaf-nodes. |
Zoek toegankelijkheid | Hier in de B-tree is de zoekopdracht niet zo eenvoudig als in vergelijking met een B + -boom. | Hier in B + tree wordt het zoeken gemakkelijk. |
Redundante sleutel | Ze slaan geen overtollige zoeksleutel op. | Ze slaan een redundante zoeksleutel op. |
toepassingen | Ze zijn een oudere versie en zijn niet zo voordelig in vergelijking met de B + -bomen. | Veel implementeerders van databasesystemen geven de voorkeur aan de structurele eenvoud van een B + -boom. |