In de volgende tutorial leren we over de B Tree-gegevensstructuur en overwegen we deze te visualiseren.
Dus laten we beginnen.
Wat is een B-boom?
De B Boom is een speciaal type meerwegzoekboom , algemeen bekend als de M-weg boom, die zichzelf in evenwicht brengt. Vanwege hun evenwichtige structuur worden deze bomen vaak gebruikt om enorme databases te beheren en te beheren en zoekopdrachten te vereenvoudigen. In een B-boom kan elk knooppunt maximaal n onderliggende knooppunten hebben. B Tree is een voorbeeld van indexering op meerdere niveaus in een databasebeheersysteem (DBMS). Leaf- en interne knooppunten hebben beide recordreferenties. B Tree staat bekend als Balanced Stored Tree omdat alle bladknooppunten zich op hetzelfde niveau bevinden.
Het volgende diagram is een voorbeeld van een B-boom:
Figuur 1. A B Boom met bestelling 3
De regels van de B-boom begrijpen
Hieronder volgen de belangrijke eigenschappen van een B-boom:
- Alle bladknooppunten bevinden zich op hetzelfde niveau.
- De gegevensstructuur van de B-boom wordt gedefinieerd door de term minimumgraad 'd'. De waarde van 'd' hangt af van de grootte van het schijfblok.
- Elk knooppunt, met uitzondering van de wortel, moet uit minimaal d-1-sleutels bestaan. Het rootknooppunt mag uit minimaal 1 sleutel bestaan.
- Alle knooppunten (inclusief het hoofdknooppunt) mogen uit maximaal bestaan (2d-1) sleutels.
- Het aantal kinderen van een knooppunt is gelijk aan de toevoeging van het aantal daarin aanwezige sleutels en .
- Alle sleutels van een knooppunt worden in oplopende volgorde gesorteerd. Het kind tussen twee sleutels, k1 en k2, bestaat uit alle sleutels die respectievelijk tussen k1 en k2 liggen.
- In tegenstelling tot de binaire zoekboom groeit en krimpt de gegevensstructuur van de B-boom vanaf de wortel. Terwijl de binaire zoekboom naar beneden groeit en naar beneden krimpt.
- Net als bij andere zelfgebalanceerde binaire zoekbomen, is de tijdcomplexiteit van de B-boomgegevensstructuur voor bewerkingen zoals zoeken, invoegen en verwijderen O(log?n) .
- Het inbrengen van een knooppunt in de B-boom gebeurt alleen bij het bladknooppunt.
Laten we het volgende voorbeeld bekijken van een B-boom met minimale bestelling 5.
Figuur 2. A B Boom van orde 5
Let op: De waarde van de minimale bestelling is veel meer dan 5 in een praktische B Trees.
In het bovenstaande diagram kunnen we zien dat alle bladknooppunten zich op hetzelfde niveau bevinden, en dat alle niet-bladknooppunten geen lege subboom hebben en uit sleutels bestaan die één minder zijn dan het aantal van hun kinderen.
De vaste formulering van de B Tree-regels:
Elke B-boom is afhankelijk van een positief constant geheel getal, bekend als MINIMUM , die wordt gebruikt om het aantal gegevenselementen te bepalen dat in een enkel knooppunt kan worden bewaard.
Regel 1: De root kan slechts één data-element bevatten (of zelfs geen data-elementen als het ook geen onderliggende elementen zijn); elk ander knooppunt heeft dat tenminste MINIMUM gegevenselementen.
Regel 2: Het maximale aantal gegevenselementen dat in een knooppunt wordt opgeslagen, is tweemaal de waarde van MINIMUM .
Regel 3: De data-elementen van elk knooppunt van de B-boom worden opgeslagen in een gedeeltelijk gevulde array, gesorteerd vanaf het kleinste data-element (bij index 0 ) naar het grootste data-element (op de uiteindelijk gebruikte positie van de array).
Regel 4: Het totale aantal subbomen onder een niet-bladknooppunt is altijd één meer dan het aantal gegevenselementen in dat knooppunt.
- subboom 0,subboom 1,...
Regel 5: Met betrekking tot elk niet-bladknooppunt:
- Een data-element in de index is groter dan alle data-elementen in het subboomnummer i van het knooppunt, en
- Een data-element in de index is kleiner dan alle data-elementen in het subboomnummer ik+1 van het knooppunt.
Regel 6: Elk blad in een B-boom heeft dezelfde diepte. Het zorgt er dus voor dat een B-boom het probleem van een onevenwichtige boom voorkomt.
Bewerkingen op een B Tree-datastructuur
Om ervoor te zorgen dat geen van de eigenschappen van een B Tree-datastructuur tijdens de bewerkingen wordt geschonden, kan de B Tree worden gesplitst of samengevoegd. Hieronder volgen enkele bewerkingen die we op een B-boom kunnen uitvoeren:
- Zoeken naar een data-element in B Tree
- Invoeging van een data-element in B Tree
- Verwijdering van een data-element in B Tree
Zoekbewerking op een B-boom
Het zoeken naar een element in een B-boom is vergelijkbaar met dat in een binaire zoekboom. Maar in plaats van een tweerichtingsbeslissing te nemen (links of rechts) zoals een binaire zoekboom, neemt een B-boom een m-wegbeslissing bij elk knooppunt, waarbij m het aantal kinderen van het knooppunt is.
Stappen om een data-element in een B-boom te zoeken:
Stap 1: Het zoeken begint vanaf het hoofdknooppunt. Vergelijk het zoekelement k met de wortel.
Stap 1.1: Als het hoofdknooppunt uit het element k bestaat, is de zoekopdracht voltooid.
Stap 1.2: Als het element k kleiner is dan de eerste waarde in de wortel, gaan we naar het meest linkse kind en doorzoeken het kind recursief.
Stap 1.3.1: Als de wortel slechts twee kinderen heeft, gaan we naar het meest rechtse kind en doorzoeken we recursief de onderliggende knooppunten.
Stap 1.3.2: Als de root meer dan twee sleutels heeft, doorzoeken we de rest.
Stap 2: Als het element k niet wordt gevonden nadat de hele boom is doorlopen, dan is het zoekelement niet aanwezig in de B-boom.
Laten we de bovenstaande stappen visualiseren met behulp van een voorbeeld. Stel dat we willen zoeken naar een sleutel k=34 in de volgende B-boom:
converteer tekenreeks naar int java
Figuur 3.1. Een gegeven B-boom
- Eerst zullen we controleren of de sleutel k = 34 bevindt zich in het hoofdknooppunt. Omdat de sleutel zich niet in de root bevindt, gaan we verder met de onderliggende knooppunten. We kunnen ook waarnemen dat het wortelknooppunt twee kinderen heeft; daarom zullen we de vereiste waarde tussen de twee sleutels vergelijken.
Figuur 3.2. De sleutel k is niet aanwezig in de root - Nu we kunnen opmerken dat de sleutel k groter is dan het wortelknooppunt, dat wil zeggen 30, gaan we verder met het rechterkind van de wortel.
Figuur 3.3. De sleutel k > 30, ga naar het rechterkind - We zullen nu de sleutel k vergelijken met de waarden die aanwezig zijn op het knooppunt, dat wil zeggen respectievelijk 40 en 50. Omdat de sleutel k kleiner is dan de linkersleutel, dat wil zeggen 40, gaan we naar het linkerkind van het knooppunt.
Figuur 3.4. De sleutel K<40, move to left child< li> - Omdat de waarde in het linkerkind van 40 34 is, wat de vereiste waarde is, kunnen we concluderen dat de sleutel is gevonden en dat de zoekbewerking is voltooid.
Figuur 3.4. De sleutel k = 34, het linkerkind van 40
We vergeleken de sleutel met vier verschillende waarden in het bovenstaande voorbeeld totdat we hem vonden. De tijdscomplexiteit die nodig is voor de zoekbewerking in een B-boom is dus gelijk O(log?n) .
Bewerking op een B-boom invoegen
Bij het invoegen van een data-element in een B-boom moeten we eerst controleren of dat element al in de boom aanwezig is of niet. Als het data-element binnen de B-boom wordt gevonden, vindt de invoegbewerking niet plaats. Als dat echter niet het geval is, gaan we verder met het invoegen. Er zijn twee scenario's waarmee rekening moet worden gehouden bij het invoegen van een element in het bladknooppunt:
Stappen om een data-element in een B-boom in te voegen:
Stap 1: We beginnen met het berekenen van het maximale aantal sleutels in het knooppunt op basis van de volgorde van de B-boom.
Stap 2: Als de boom leeg is, wordt er een rootknooppunt toegewezen en voegen we de sleutel in die als rootknooppunt fungeert.
Stap 3: We zullen nu het toepasselijke knooppunt voor invoeging zoeken.
Stap 4: Als het knooppunt vol is:
Stap 4.1: We zullen de gegevenselementen in oplopende volgorde invoegen.
Stap 4.2: Als de gegevenselementen groter zijn dan het maximale aantal sleutels, splitsen we het volledige knooppunt op de mediaan.
Stap 4.3: We duwen de middentoets naar boven en splitsen de linker- en rechtertoets als linker- en rechterkind.
Stap 5: Als het knooppunt niet vol is, voegen we het knooppunt in oplopende volgorde in.
Laten we de bovenstaande stappen visualiseren met behulp van een voorbeeld. Stel dat we een B-boom van orde 4 moeten maken. De gegevenselementen die in de B-boom moeten worden ingevoegd, zijn 5,3,21,11,1,16,8,13,4 en 9 .
stl
- Omdat m gelijk is aan 3, het maximale aantal sleutels voor een knooppunt = m-1 = 3-1 = 2 .
- We beginnen met het invoegen 5 in de lege boom.
Figuur 4.1. Invoegen 5 - We zullen er nu 3 in de boom invoegen. Omdat 3 kleiner is dan 5, voegen we 3 links van 5 in hetzelfde knooppunt in.
Figuur 4.2. Invoegen 3 - We zullen nu 21 in de boom invoegen, en aangezien 21 groter is dan 5, zal het rechts van 5 in hetzelfde knooppunt worden ingevoegd. Omdat we echter weten dat het maximale aantal sleutels in het knooppunt twee is, wordt een van deze sleutels verplaatst naar een knooppunt erboven om deze te splitsen. Dus 5, het middelste data-element, zal omhoog bewegen, en 3 en 21 zullen respectievelijk de linker- en rechterknooppunten worden.
Figuur 4.3. Invoegen 21 - Nu is het tijd om het volgende data-element in te voegen, d.w.z. 11, dat groter is dan 5 maar kleiner dan 21. Daarom zal 11 worden ingevoegd als een sleutel aan de linkerkant van het knooppunt dat bestaat uit 21 als sleutel.
Figuur 4.4. Invoegen 11 - Op dezelfde manier zullen we het volgende gegevenselement 1 in de boom invoegen, en zoals we kunnen zien, is 1 kleiner dan 3; daarom wordt het als een sleutel aan de linkerkant van het knooppunt bestaande uit 3 als sleutel ingevoegd.
Figuur 4.5. Invoegen 1 - Nu zullen we data-element 16 in de boom invoegen, dat groter is dan 11 maar kleiner dan 21. Het aantal sleutels in dat knooppunt overschrijdt echter het maximale aantal sleutels. Daarom zal het knooppunt splitsen, waardoor de middelste sleutel naar de wortel wordt verplaatst. Daarom wordt 16 rechts van de 5 ingevoegd, waardoor 11 en 21 in twee afzonderlijke knooppunten worden gesplitst.
Figuur 4.6. Invoegen 16 - Het data-element 8 wordt als sleutel links van 11 ingevoegd.
Figuur 4.7. Invoegen 8 - We zullen 13 in de boom invoegen, wat kleiner is dan 16 en groter dan 11. Daarom moet data-element 13 rechts van het knooppunt bestaande uit 8 en 11 worden ingevoegd. Omdat het maximale aantal sleutels in de boom echter kan slechts 2 is, zal er een splitsing plaatsvinden, waarbij het middelste data-element 11 naar het bovenstaande knooppunt wordt verplaatst en 8 en 13 naar twee afzonderlijke knooppunten. Nu zal het bovenstaande knooppunt bestaan uit 5, 11 en 16, wat opnieuw het maximale aantal sleutels overschrijdt. Daarom zal er nog een splitsing plaatsvinden, waardoor het data-element 11 het hoofdknooppunt wordt, met 5 en 16 als onderliggende knooppunten.
Figuur 4.8. Invoegen 13 - Omdat het data-element 4 kleiner is dan 5 maar groter dan 3, wordt het rechts van het knooppunt bestaande uit 1 en 3 ingevoegd, waardoor het maximale aantal sleutels in een knooppunt opnieuw wordt overschreden. Daarom zal er opnieuw een lekkage optreden, waardoor de 3 naar het bovenste knooppunt naast 5 wordt verplaatst.
Figuur 4.9. Invoegen 4 - Tenslotte zal het data-element 9, dat groter is dan 8 maar kleiner dan 11, rechts van het knooppunt bestaande uit 8 als sleutel worden ingevoegd.
Figuur 4.10. Invoegen 9
In het bovenstaande voorbeeld hebben we verschillende vergelijkingen uitgevoerd. De eerste waarde werd rechtstreeks in de boom ingevoegd; daarna moest elke waarde worden vergeleken met de beschikbare knooppunten in die boom. De tijdscomplexiteit voor de invoegbewerking in een B-boom hangt af van het aantal knooppunten en .
Bewerking op een B-boom verwijderen
Het verwijderen van een gegevenselement in een B-boom bevat drie primaire gebeurtenissen:
- Zoeken naar het knooppunt waar de te verwijderen sleutel bestaat,
- De sleutel verwijderen, en
- Indien nodig de boom balanceren.
Terwijl u een element uit de boom verwijdert, kan er een toestand optreden die bekend staat als Underflow. Onderstroom treedt op wanneer een knooppunt uit minder dan het minimumaantal sleutels bestaat; het zou moeten vasthouden.
Hieronder volgen enkele termen die u moet begrijpen voordat u de verwijderingsbewerking visualiseert:
Hieronder volgen drie prominente gevallen van de verwijderingsbewerking in een B-boom:
Geval 1: Het verwijderen/verwijderen van de sleutel ligt in het Leaf-knooppunt - Deze zaak is verder onderverdeeld in twee verschillende gevallen:
1. Het verwijderen/verwijderen van de sleutel is niet in strijd met de eigenschap van het minimumaantal sleutels dat een knooppunt moet bevatten.
Laten we dit geval visualiseren met behulp van een voorbeeld waarin we sleutel 32 uit de volgende B-boom zullen verwijderen.
Figuur 4.1: Een bladknooppuntsleutel (32) verwijderen uit de B-boom
Zoals we kunnen zien, schendt het verwijderen van 32 uit deze stamboom de bovenstaande eigenschap niet.
2. Het verwijderen/verwijderen van de sleutel is in strijd met de eigenschap van het minimumaantal sleutels dat een knooppunt moet bevatten. In dit geval moeten we een sleutel lenen van het nabijgelegen zusterknooppunt in de volgorde van links naar rechts.
Ten eerste zullen we de naaste linkse broer of zus bezoeken. Als het linker zusterknooppunt meer dan een minimumaantal sleutels heeft, zal het een sleutel van dit knooppunt lenen.
Anders zullen we controleren of we kunnen lenen van het nabijgelegen rechterbroer-zusknooppunt.
Laten we dit geval nu visualiseren met behulp van een voorbeeld waarin we 31 uit de bovenstaande B-boom zullen verwijderen. In dit geval lenen we een sleutel van het linker zusterknooppunt.
Figuur 4.2: Een bladknooppuntsleutel (31) verwijderen uit de B-boom
Als beide nabijgelegen zusterknooppunten al uit een minimum aantal sleutels bestaan, zullen we het knooppunt samenvoegen met het linker zusterknooppunt of met het rechterknooppunt. Dit samenvoegproces wordt uitgevoerd via het bovenliggende knooppunt.
Laten we het opnieuw visualiseren door sleutel 30 uit de bovenstaande B-boom te verwijderen.
Figuur 4.3: Een bladknooppuntsleutel (30) verwijderen uit de B-boom
Geval 2: Het verwijderen/verwijderen van de sleutel ligt in het niet-Leaf-knooppunt - Deze zaak is verder onderverdeeld in verschillende gevallen:
1. Het niet-bladige/interne knooppunt, dat wordt verwijderd, wordt vervangen door een voorganger in de juiste volgorde als het linkerkindknooppunt meer dan het minimumaantal sleutels heeft.
Laten we dit geval visualiseren met behulp van een voorbeeld waarin we sleutel 33 uit de B-boom zullen verwijderen.
Figuur 4.4: Een bladknooppuntsleutel (33) verwijderen uit de B-boom
2. Het niet-Leaf/Interne knooppunt, dat wordt verwijderd, wordt vervangen door een opvolger in de juiste volgorde als het rechterkindknooppunt meer dan het minimumaantal sleutels heeft.
Als een van beide kinderen een minimumaantal sleutels heeft, zullen we de linker- en rechterkindknooppunten samenvoegen.
Laten we dit geval visualiseren door sleutel 30 uit de B-boom te verwijderen.
Figuur 4.5: Een bladknooppuntsleutel (30) verwijderen uit de B-boom
Als het ouderknooppunt na het samenvoegen minder dan het minimumaantal sleutels heeft, kan men naar de broers en zussen zoeken, zoals in Zaak 1 .
Geval 3: In het volgende geval krimpt de hoogte van de boom. Als de doelsleutel zich in een intern knooppunt bevindt, en het verwijderen van de sleutel leidt tot minder sleutels in het knooppunt (wat minder is dan het minimaal noodzakelijke), zoek dan naar de voorganger in de juiste volgorde en de opvolger in de juiste volgorde. Als beide kinderen een minimum aantal sleutels hebben, kan er niet geleend worden. Dit leidt tot Geval 2(3) , dat wil zeggen het samenvoegen van de onderliggende knooppunten.
We gaan opnieuw op zoek naar de broer of zus om een sleutel te lenen. Als het broertje of zusje echter ook uit een minimumaantal sleutels bestaat, zullen we het knooppunt met het broertje of zusje samenvoegen met het bovenliggende knooppunt en de onderliggende knooppunten rangschikken volgens de vereisten (oplopende volgorde).
Laten we dit geval visualiseren met behulp van een voorbeeld waarin we het data-element 10 uit de gegeven B-boom zullen verwijderen.
Figuur 4.6: Een bladknooppuntsleutel (10) verwijderen uit de B-boom
De tijdscomplexiteit in de bovenstaande voorbeelden varieert afhankelijk van de locatie waar de sleutel moet worden verwijderd. De tijdscomplexiteit voor de verwijderingsbewerking in een B-boom is dus gelijk O(log?n) .
De conclusie
In deze tutorial hebben we de B Tree leren kennen en de verschillende werkingen ervan gevisualiseerd met verschillende voorbeelden. We hebben ook enkele fundamentele eigenschappen en regels van de B-boom begrepen.