B-tre i datastruktur: Søk, sett inn, slett

Hva er et B-tre?

B tre er en selvbalanserende datastruktur basert på et spesifikt sett med regler for å søke, sette inn og slette data på en raskere og minneeffektiv måte. For å oppnå dette følges følgende regler for å lage et B-tre.

Et B-tre er en spesiell type tre i en datastruktur. I 1972 ble denne metoden først introdusert av McCreight og Bayer, som kalte den Height Balanced m-way Search Tree. Den hjelper deg med å bevare data sortert og tillater ulike operasjoner som innsetting, søking og sletting på kortere tid.

Regler for B-tre

Her er viktige regler for å lage et B-tre:

• Alle bladene vil bli opprettet på samme nivå.
• Et B-tre bestemmes av et antall grader, som også kalles «orden» (spesifisert av en ekstern aktør, som en programmerer), referert til som m videre. Verdien av m avhenger av blokkstørrelsen på disken som data primært er plassert på.
• Det venstre undertreet til noden vil ha lavere verdier enn høyre side av undertreet. Dette betyr at nodene også er sortert i stigende rekkefølge fra venstre mot høyre.
• Det maksimale antallet nøkler en rotnode, samt dens undernoder, kan inneholde, beregnes med denne formelen: m − 1. For eksempel:

  m = 4
  max keys: 4 − 1 = 3

• Hver node, unntatt roten, må inneholde et minimum antall nøkler av [m/2] − 1. For eksempel:

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

• Maksimalt antall underordnede noder en node kan ha er lik graden, som er m.
• Minste barn en node kan ha er halvparten av ordren, som er m/2 (takverdien er tatt).
• Alle nøklene i en node er sortert i økende rekkefølge.

Hvorfor bruke B-Tree

Her er grunner til å bruke et B-tre:

• Reduserer antall lesninger som gjøres på disken.
• B-trær kan enkelt optimaliseres for å justere størrelsen (det vil si antall underordnede noder) i henhold til diskstørrelsen.
• Det er en spesialdesignet teknikk for å håndtere store mengder data.
• Det er en nyttig algoritme for databaser og filsystemer.
• Et godt valg å velge når det gjelder å lese og skrive store datablokker.

Historien til B Tree

• Data lagres på disken i blokker. Når disse dataene bringes inn i hovedminnet (eller RAM), kalles de en datastruktur.
• Når det gjelder enorme datamengder, krever det å søke etter én post på disken at hele disken leses. Dette øker tid og forbruk av hovedminne på grunn av høy disktilgangsfrekvens og datastørrelse.
• For å overkomme dette opprettes indekstabeller som lagrer postreferansen til postene basert på blokkene de befinner seg i. Dette reduserer tids- og minneforbruket drastisk.
• Siden vi har enorme data, kan vi lage indekstabeller på flere nivåer.
• En flernivåindeks kan utformes ved å bruke et B-tre for keeping dataene sorteres på en selvbalanserende måte.

Søk Operasjon

Søkeoperasjonen er den enkleste operasjonen på et B-tre. Følgende algoritme brukes:

• La nøkkelen (verdien) som skal søkes inn være «k».
• Begynn å søke fra roten og gå rekursivt nedover.
• Hvis k er mindre enn rotverdien, søk i det venstre undertreet; hvis k er større enn rotverdien, søk i det høyre undertreet.
• Hvis noden har funnet k, returnerer du bare noden.
• Hvis k ikke finnes i noden, gå ned til barnet med en større nøkkel.
• Hvis k ikke finnes i treet, returnerer vi NULL.

innfelt Operasjon

Siden et B-tre er et selvbalanserende tre, kan du ikke tvinge inn en nøkkel i hvilken som helst node. Følgende algoritme gjelder:

• Kjør søkeoperasjonen og finn riktig sted for innsetting.
• Sett inn den nye nøkkelen på riktig sted, men hvis noden allerede har et maksimalt antall nøkler:
• Noden, sammen med en nylig satt inn nøkkel, vil dele seg fra midtelementet.
• Det midterste elementet blir overordnet for de to andre underordnede nodene.
• Nodene må omorganisere nøkler i stigende rekkefølge.

I eksemplet ovenfor:

• Søk etter riktig posisjon i noden for nøkkelen.
• Sett inn nøkkelen i målnoden, og sjekk for regler.
• Har noden mer enn eller lik minimumsantallet nøkler, som er 1, etter innsetting? I dette tilfellet ja, det har den. Sjekk neste regel.
• Har noden mer enn det maksimale antallet nøkler, som er 3, etter innsetting? I dette tilfellet, nei, det har den ikke. Dette betyr at B-treet ikke bryter noen regler, og innsettingen er fullført.

I eksemplet ovenfor:

• Noden har nådd maksimalt antall nøkler.
• Noden vil dele seg, og den midterste nøkkelen blir rotnoden til resten av de to nodene.
• Ved et partall nøkler vil den midterste noden bli valgt med venstre- eller høyreforspenning.

I eksemplet ovenfor:

• Noden har færre enn maksimalt antall nøkler.
• 1 er satt inn ved siden av 3, men regelen for stigende rekkefølge brytes.
• For å fikse dette er nøklene sortert.

På samme måte kan 13 og 2 enkelt settes inn i noden, ettersom de oppfyller regelen om «mindre enn maksimalt antall nøkler» for nodene.

I eksemplet ovenfor:

• Noden har nøkler lik maks nøkler.
• Nøkkelen er satt inn i målnoden, men den bryter regelen om maksimalt antall nøkler.
• Målnoden er delt, og den midterste nøkkelen ved venstre forspenning er nå overordnet til de nye undernodene.
• De nye nodene er ordnet i stigende rekkefølge.

På samme måte, basert på reglene og tilfellene ovenfor, kan resten av verdiene enkelt settes inn i B-treet.

Delete Operasjon

Sletteoperasjonen har flere regler enn innsettings- og søkeoperasjonene. Følgende algoritme gjelder:

• Kjør søkeoperasjonen og finn målnøkkelen i nodene.
• Tre betingelser gjelder basert på plasseringen av målnøkkelen, som forklart i de følgende avsnittene.

Hvis målnøkkelen er i bladnoden

• Target er i bladnoden, mer enn min-nøkler. Sletting av dette vil ikke krenke egenskapen til B-treet.
• Target er i bladnoden, og den har min-nøkkelnoder. Sletting av dette vil krenke egenskapen til B-treet.
• Målnoden kan låne en nøkkel fra den umiddelbare venstre noden eller den umiddelbare høyre noden (søsken).
• Søsken vil si ja hvis den har mer enn minimumsantallet nøkler.
• Nøkkelen lånes fra foreldrenoden, maksverdien overføres til foreldrenoden, maksverdien fra foreldrenoden overføres til målnoden, og målverdien fjernes.
• Target er i bladnoden, men ingen søsken har mer enn minimumsantallet nøkler: søk etter nøkkelen, slå sammen med søsken og minimumsantallet foreldrenoder, totalt antall nøkler vil nå være mer enn minimumsantallet, og målnøkkelen vil bli erstattet med minimumsantallet til en foreldrenode.

Hvis målnøkkelen er i en intern node

• Velg enten en forgjenger i riktig rekkefølge eller en etterfølger i riktig rekkefølge.
• Når det gjelder en forgjenger i riktig rekkefølge, vil den maksimale nøkkelen fra det venstre undertreet bli valgt.
• Ved en etterfølger i riktig rekkefølge vil minimumsnøkkelen fra det høyre undertreet bli valgt.
• Hvis målnøkkelens forgjenger i rekkefølge har flere enn min-tastene, er det først da som den kan erstatte målnøkkelen med maks-tallet for forgjengeren i rekkefølge.
• Hvis målnøkkelens forgjenger i rekkefølge ikke har mer enn min-nøkler, se etter den rekkefølgefølgende etterfølgerens minimumsnøkkel.
• Hvis målnøkkelens forgjenger og etterfølger i rekkefølge begge har mindre enn min-nøkler, slå sammen forgjengeren og etterfølgeren.

Hvis målnøkkelen er i en rotnode

• Erstatt med det maksimale elementet i det foregående undertreet i riktig rekkefølge.
• Hvis målet har færre enn minimumsnøkler etter sletting, vil målnoden låne maksverdien fra søskenet sitt via søskenets overordnede.
• Maksimumsverdien til foreldrene vil bli tatt av målet, men med nodene med maksimalverdien til søskenet.

La oss nå forstå sletteoperasjonen med et eksempel.

Diagrammet ovenfor viser forskjellige tilfeller av sletteoperasjonen i et B-tre. Dette B-treet er av orden 5, som betyr at minimum antall barnnoder en node kan ha er 3, og maksimum antall barnnoder en node kan ha er 5. Mens minimum og maksimum antall nøkler en node kan ha er henholdsvis 2 og 4.

I eksemplet ovenfor:

• Målnoden har målnøkkelen som skal slettes.
• Målnoden har flere nøkler enn minimumsantall nøkler.
• Bare slett nøkkelen.

I eksemplet ovenfor:

• Målnoden har nøkler som tilsvarer minimumsnøkler, så vi kan ikke slette den direkte, da det vil bryte betingelsene.

Nå forklarer følgende diagram hvordan du sletter denne nøkkelen:

• Målnoden vil låne en nøkkel fra en umiddelbar søsken, i dette tilfellet forgjengeren i riktig rekkefølge (venstre søsken), fordi den ikke har noen etterfølger i riktig rekkefølge (høyre søsken).
• Maksimumsverdien til forgjengeren i rekkefølge vil bli overført til forelderen, og forelderen vil overføre maksimumsverdien til målnoden (se diagrammet nedenfor).

Følgende eksempel illustrerer hvordan du sletter en nøkkel som trenger en verdi fra sin etterfølger i rekkefølge.

• Målnoden vil låne en nøkkel fra en umiddelbar søsken, i dette tilfellet etterfølgeren i rekkefølge (høyre søsken), fordi forgjengeren i rekkefølge (venstre søsken) har nøkler som er lik minimumsnøkler.
• Minimumsverdien til etterfølgeren i rekkefølge vil bli overført til overordnet, og overordnet vil overføre maksimumsverdien til målnoden.

I eksemplet nedenfor har ikke målnoden noen søsken som kan gi nøkkelen sin til målnoden. Derfor er sammenslåing nødvendig. Se prosedyren for å slette en slik nøkkel:

• Slå sammen målnoden med hvilken som helst av dens umiddelbare søsken sammen med den overordnede nøkkelen.
• Nøkkelen fra den overordnede noden velges, og den ligger mellom de to sammenslående nodene.
• Slett målnøkkelen fra den sammenslåtte noden.

Delete Operasjon 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
    }
}

Utgang: Det største elementet slettes fra B-treet.

Spørsmål og svar