B-boom in datastructuren: zoeken, invoegen, verwijderen

Wat is een B-boom?

B Boom Een B-boom is een zelfbalancerende datastructuur gebaseerd op een specifieke set regels voor het zoeken, invoegen en verwijderen van gegevens op een snellere en geheugenefficiëntere manier. Om dit te bereiken, worden de volgende regels gevolgd bij het creëren van een B-boom.

Een B-boom is een speciaal type boom in een datastructuur. Deze methode werd in 1972 voor het eerst geïntroduceerd door McCreight en Bayer, die het een hoogtegebalanceerde m-weg zoekboom noemden. Het helpt je om gegevens gesorteerd te houden en maakt diverse bewerkingen zoals invoegen, zoeken en verwijderen in minder tijd mogelijk.

Regels voor B-Tree

Hieronder volgen belangrijke regels voor het maken van een B-boom:

• Alle bladeren worden op hetzelfde niveau gemaakt.
• Een B-boom wordt bepaald door een aantal graden, ook wel "orde" genoemd (gespecificeerd door een externe partij, zoals een programmeur), aangeduid als m verder. De waarde van m hangt af van de blokgrootte op de schijf waarop de gegevens zich primair bevinden.
• De linker subboom van het knooppunt heeft lagere waarden dan de rechterkant van de subboom. Dit betekent dat de knooppunten ook oplopend van links naar rechts worden gesorteerd.
• Het maximale aantal sleutels dat een rootknooppunt, evenals de bijbehorende kindknooppunten, kan bevatten, wordt berekend met de volgende formule: m − 1. Bijvoorbeeld:

  m = 4
  max keys: 4 − 1 = 3

• Elk knooppunt, met uitzondering van de root, moet een minimum aantal sleutels bevatten van [m/2] − 1. Bijvoorbeeld:

  m = 4
  min keys: 4/2 − 1 = 1

• Het maximale aantal onderliggende knooppunten dat een knooppunt kan hebben, is gelijk aan de graad ervan m.
• Het minimale aantal kinderen dat een knooppunt kan hebben is de helft van de orde, namelijk m/2 (de plafondwaarde wordt genomen).
• Alle sleutels in een knooppunt worden in oplopende volgorde gesorteerd.

Waarom B-Tree gebruiken?

Hieronder volgen redenen om een ​​B-boom te gebruiken:

• Vermindert het aantal leesbewerkingen op de schijf.
• B-bomen kunnen eenvoudig worden geoptimaliseerd om hun grootte (dat wil zeggen, het aantal kindknooppunten) aan te passen aan de beschikbare schijfruimte.
• Het is een speciaal ontworpen techniek voor het verwerken van een grote hoeveelheid gegevens.
• Het is een handig algoritme voor databases en bestandssystemen.
• Een goede keuze voor het lezen en schrijven van grote hoeveelheden data.

Geschiedenis van B-boom

• Gegevens worden in blokken op de schijf opgeslagen. Deze gegevens worden, wanneer ze in het hoofdgeheugen (of RAM) worden geladen, een datastructuur genoemd.
• Bij grote hoeveelheden data vereist het zoeken naar één record op de schijf het uitlezen van de hele schijf; dit verhoogt de benodigde tijd en het geheugenverbruik als gevolg van de hoge frequentie van schijftoegang en de omvang van de data.
• Om dit te verhelpen, worden indextabellen aangemaakt die de recordreferentie opslaan op basis van de blokken waarin de records zich bevinden. Dit reduceert de benodigde tijd en het geheugenverbruik aanzienlijk.
• Omdat we over enorme gegevens beschikken, kunnen we indextabellen met meerdere niveaus maken.
• Een index op meerdere niveaus kan worden ontworpen door een B-boom te gebruiken voor het bijhouden van gegevens.ping De gegevens worden op een zelfbalancerende manier gesorteerd.

Zoeken Operatie

De zoekoperatie is de eenvoudigste bewerking op een B-boom. Het volgende algoritme wordt toegepast:

• Laten we de te zoeken sleutel (de waarde) aanduiden met "k".
• Begin met zoeken vanaf de wortel en zoek recursief naar beneden.
• Als k kleiner is dan de wortelwaarde, doorzoek dan de linker subboom; als k groter is dan de wortelwaarde, doorzoek dan de rechter subboom.
• Als het knooppunt de gevonden k heeft, retourneert u eenvoudigweg het knooppunt.
• Als de k niet in het knooppunt wordt gevonden, ga dan naar het kind met een grotere sleutel.
• Als k niet in de boom wordt gevonden, retourneren we NULL.

Invoegen Operatie

Omdat een B-boom een ​​zelfbalancerende boom is, kun je niet zomaar een sleutel in een willekeurige knoop invoegen. Het volgende algoritme is van toepassing:

• Voer de zoekopdracht uit en vind de juiste invoegplaats.
• Plaats de nieuwe sleutel op de juiste locatie, maar als het knooppunt al een maximaal aantal sleutels heeft:
• Het knooppunt zal, samen met een nieuw ingevoegde sleutel, zich splitsen van het middelste element.
• Het middelste element wordt het bovenliggende element voor de andere twee onderliggende knooppunten.
• De knooppunten moeten de sleutels in oplopende volgorde herschikken.

In het bovenstaande voorbeeld:

• Zoek de sleutel op de juiste positie in het knooppunt.
• Voeg de sleutel in het doelknooppunt in en controleer op regels.
• Heeft het knooppunt na invoeging meer dan of gelijk aan het minimum aantal sleutels, namelijk 1? In dit geval is het antwoord ja. Controleer de volgende regel.
• Heeft het knooppunt na de invoeging meer sleutels dan het maximale aantal van 3? In dit geval niet. Dit betekent dat de B-boom geen regels overtreedt en dat de invoeging is voltooid.

In het bovenstaande voorbeeld:

• Het knooppunt heeft het maximale aantal sleutels bereikt.
• Het knooppunt zal zich splitsen en de middelste sleutel zal het wortelknooppunt worden van de overige twee knooppunten.
• Bij een even aantal sleutels wordt het middelste knooppunt geselecteerd op basis van een voorkeur voor links of rechts.

In het bovenstaande voorbeeld:

• Het knooppunt heeft minder dan het maximale aantal sleutels.
• Het getal 1 wordt naast het getal 3 geplaatst, maar de regel van oplopende volgorde wordt geschonden.
• Om dit op te lossen, worden de sleutels gesorteerd.

Op dezelfde manier kunnen 13 en 2 gemakkelijk in het knooppunt worden ingevoegd, omdat ze voldoen aan de regel "minder dan het maximale aantal sleutels" voor de knooppunten.

In het bovenstaande voorbeeld:

• Het knooppunt heeft sleutels die gelijk zijn aan het maximale aantal sleutels.
• De sleutel wordt in het doelknooppunt ingevoegd, maar dit is in strijd met de regel van het maximale aantal sleutels.
• Het doelknooppunt wordt gesplitst en de middelste sleutel is nu, door links te vertekenen, de ouder van de nieuwe onderliggende knooppunten.
• De nieuwe knooppunten zijn in oplopende volgorde gerangschikt.

Op dezelfde manier kunnen, op basis van de bovenstaande regels en gevallen, de rest van de waarden eenvoudig in de B-boom worden ingevoegd.

Verwijdering Operatie

De verwijderingsbewerking kent meer regels dan de invoeg- en zoekbewerkingen. Het volgende algoritme is van toepassing:

• Voer de zoekopdracht uit en vind de doelsleutel in de knooppunten.
• Er worden drie voorwaarden toegepast op basis van de locatie van de doelsleutel, zoals in de volgende paragrafen wordt uitgelegd.

Als de doelsleutel zich in het bladknooppunt bevindt

• Target bevindt zich in het bladknooppunt, meer dan min sleutels. Het verwijderen hiervan zal de eigenschap van de B-boom niet schenden.
• Target bevindt zich in het bladknooppunt en heeft min sleutelknooppunten. Het verwijderen hiervan zou een eigenschap van de B-boom schenden.
• Het doelknooppunt kan een sleutel lenen van het direct linkse knooppunt of het direct rechtse knooppunt (broer of zus).
• De broer of zus zal het zeggen ja als het meer dan het minimum aantal sleutels heeft.
• De sleutel wordt geleend van het bovenliggende knooppunt, de maximale waarde wordt overgedragen naar het bovenliggende knooppunt, de maximale waarde van het bovenliggende knooppunt wordt overgedragen naar het doelknooppunt en de doelwaarde wordt verwijderd.
• Target Als de sleutel zich in het bladknooppunt bevindt, maar geen van de broers of zussen meer dan het minimum aantal sleutels heeft, zoek dan naar de sleutel, voeg deze samen met de broers of zussen en het minimum aantal bovenliggende knooppunten. Het totale aantal sleutels zal nu groter zijn dan het minimum, en de doelsleutel wordt vervangen door het minimum aantal sleutels van een bovenliggend knooppunt.

Als de doelsleutel zich in een intern knooppunt bevindt

• Kies een voorganger of opvolger in de juiste volgorde.
• In het geval van een in-order voorganger wordt de maximale sleutel uit de linker subboom geselecteerd.
• In het geval van een opvolger in de juiste volgorde, wordt de kleinste sleutel uit de rechter subboom geselecteerd.
• Als de in-order voorganger van de doelsleutel meer sleutels bevat dan het minimum, dan kan deze de doelsleutel alleen vervangen door de sleutel met het maximum aantal sleutels uit de in-order voorganger.
• Als de in-order voorganger van de doelsleutel niet meer dan min sleutels heeft, zoek dan naar de minimale sleutel van de in-order opvolger.
• Als de voorganger en de opvolger van de doelsleutel beide minder dan min-sleutels hebben, voeg dan de voorganger en de opvolger samen.

Als de doelsleutel zich in een hoofdknooppunt bevindt

• Vervang dit door het maximale element van de in-order voorganger-subboom.
• Als het doelknooppunt na verwijdering minder dan het minimum aantal sleutels bevat, zal het doelknooppunt de maximale waarde lenen van zijn broer of zus via de ouder van die broer of zus.
• De maximale waarde van het ouderknooppunt wordt door het doelknooppunt overgenomen, maar met de knooppunten die de maximale waarde van het broer- of zusknooppunt vertegenwoordigen.

Laten we nu de verwijderbewerking aan de hand van een voorbeeld toelichten.

Het bovenstaande diagram toont verschillende gevallen van de verwijderingsbewerking in een B-boom. Deze B-boom is van orde 5, wat betekent dat een knooppunt minimaal 3 en maximaal 5 kindknooppunten kan hebben. Het minimum en maximum aantal sleutels dat een knooppunt kan hebben, zijn respectievelijk 2 en 4.

In het bovenstaande voorbeeld:

• Het doelknooppunt bevat de te verwijderen doelsleutel.
• Het doelknooppunt heeft meer sleutels dan het minimum aantal sleutels.
• Verwijder de sleutel.

In het bovenstaande voorbeeld:

• Het doelknooppunt heeft sleutels die gelijk zijn aan het minimum aantal sleutels, dus we kunnen het niet direct verwijderen omdat dat de voorwaarden zou schenden.

Het volgende diagram legt uit hoe u deze sleutel kunt verwijderen:

• Het doelknooppunt leent een sleutel van een direct broer- of zusknooppunt, in dit geval de in de juiste volgorde georiënteerde voorganger (linker broer of zus), omdat het geen in de juiste volgorde georiënteerde opvolger (rechter broer of zus) heeft.
• De maximale waarde van de voorganger in de juiste volgorde wordt overgedragen aan het bovenliggende knooppunt, en het bovenliggende knooppunt draagt ​​de maximale waarde vervolgens over aan het doelknooppunt (zie onderstaand diagram).

Het volgende voorbeeld illustreert hoe u een sleutel verwijdert die een waarde nodig heeft van zijn opvolger.

• Het doelknooppunt leent een sleutel van een direct broer- of zusknooppunt, in dit geval de opvolger in de juiste volgorde (rechter broer of zus), omdat de voorganger in de juiste volgorde (linker broer of zus) sleutels heeft die gelijk zijn aan het minimum aantal sleutels.
• De minimumwaarde van de opvolger in de juiste volgorde wordt overgedragen naar de ouder, en de ouder zal de maximale waarde overdragen aan het doelknooppunt.

In het onderstaande voorbeeld heeft het doelknooppunt geen broer of zus die zijn sleutel aan het doelknooppunt kan doorgeven. Daarom is samenvoegen noodzakelijk. Zie de procedure voor het verwijderen van een dergelijke sleutel:

• Voeg het doelknooppunt samen met al zijn directe broers en zussen, inclusief de oudersleutel.
• De sleutel van het bovenliggende knooppunt dat zich tussen de twee samenvoegende knooppunten bevindt, wordt geselecteerd.
• Verwijder de doelsleutel uit het samengevoegde knooppunt.

Verwijdering Operatie Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Output: Het grootste element wordt uit de B-Tree verwijderd.

Veelgestelde vragen