B TREE i datastruktur: Søk, Sett inn, Slett Operasjonseksempel

Regler for B-tre

Her er viktige regler for å lage B_Tree

• Alle bladene vil bli opprettet på samme nivå.
• B-Tree bestemmes av et antall grader, som også kalles "ordre" (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.
• Maksimalt antall undernoder, en rotnod og dens undernoder kan inneholde, beregnes ved hjelp av denne formelen:

  m – 1

  For eksempel:

  m = 4
  max keys: 4 – 1 = 3
  

• Hver node, unntatt root, må inneholde minimumsnøkler på

  [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 B-Tree

• Reduserer antall avlesninger 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, disse dataene, når de bringes inn i hovedminnet (eller RAM), kalles datastruktur.
• I tilfelle store data krever søk i én post på disken å lese hele disken; dette øker tids- og hovedminneforbruket på grunn av høy disktilgangsfrekvens og datastørrelse.
• For å overvinne dette lages indekstabeller som lagrer postreferansen til postene basert på blokkene de ligger i. Dette reduserer tids- og minneforbruket drastisk.
• Siden vi har enorme data, kan vi lage indekstabeller på flere nivåer.
• Flernivåindeks kan utformes ved å bruke B Tree for å holde dataene sortert på en selvbalanserende måte.

Søk Operasjon

Søkeoperasjonen er den enkleste operasjonen på B Tree.

Følgende algoritme brukes:

• La nøkkelen (verdien) som skal søkes med "k".
• Begynn å søke fra roten og gå rekursivt nedover.
• Hvis k er mindre enn rotverdien, søk venstre undertre, hvis k er større enn rotverdien, søk i høyre undertre.
• 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 B Tree 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.

TIPS	Følgende er ikke sant om innsettingsalgoritmen: Siden noden er full, vil den derfor dele seg, og så vil en ny verdi settes inn

I eksemplet ovenfor:

• Søk på riktig posisjon i noden etter nøkkelen
• Sett inn nøkkelen i målnoden, og se etter regler
• Etter innsetting, har noden mer enn lik et minimum antall nøkler, som er 1? I dette tilfellet, ja, det gjør det. Sjekk neste regel.
• Etter innsetting, har noden mer enn et maksimalt antall nøkler, som er 3? I dette tilfellet, nei, det gjør det ikke. Dette betyr at B-treet ikke bryter noen regler, og innsettingen er fullført.

I eksemplet ovenfor:

• Noden har nådd maks antall nøkler
• Noden vil dele seg, og den midterste nøkkelen vil bli rotnoden til de to andre nodene.
• Ved like antall nøkler vil den midterste noden velges ved venstre forspenning eller høyre forspenning.

I eksemplet ovenfor:

• Noden har mindre enn maks nøkler
• 1 er satt inn ved siden av 3, men regelen for stigende rekkefølge er brutt
• For å fikse dette blir nøklene sortert

På samme måte kan 13 og 2 enkelt settes inn i noden da de oppfyller regelen for mindre enn maks nøkler for nodene.

I eksemplet ovenfor:

• Noden har nøkler lik maks nøkler.
• Nøkkelen settes inn i målnoden, men den bryter regelen om maksnø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

Slettingsoperasjonen har flere regler enn innsettings- og søkeoperasjoner.

Følgende algoritme gjelder:

• Kjør søkeoperasjonen og finn målnøkkelen i nodene
• Tre forhold ble brukt 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-taster.
• Sletting av dette vil ikke krenke eiendommen til B Tree
• Target er i bladnoden, den har min nøkkelnoder
• Sletting av dette vil krenke eiendommen til B Tree
• Target node kan låne nøkkel fra umiddelbar venstre node, eller umiddelbar høyre node (søsken)
• Søsken vil si ja hvis den har mer enn minimum antall nøkler
• Nøkkelen vil bli lånt fra overordnet node, maksverdien vil bli overført til en overordnet, maksverdien til overordnet node vil bli overført til målnoden, og fjern målverdien
• Target er i bladnoden, men ingen søsken har mer enn min antall nøkler
• Søk etter nøkkel
• Slå sammen med søsken og minimum av overordnede noder
• Totalt antall nøkler vil nå være mer enn min
• Målnøkkelen vil bli erstattet med minimum av en overordnet node

Hvis målnøkkelen er i en intern node

• Velg enten, bestill forgjenger eller i rekkefølge etterfølger
• I tilfelle forgjengeren i rekkefølge, vil den maksimale nøkkelen fra venstre undertre bli valgt
• I tilfelle etterfølger i rekkefølge, vil minimumsnøkkelen fra høyre undertre bli valgt
• Hvis målnøkkelens forgjenger i rekkefølge har flere enn min-tastene, kan den kun erstatte målnøkkelen med maks. for forgjengeren i rekkefølge
• Hvis målnøkkelens forgjenger i rekkefølge ikke har mer enn min-nøkler, se etter etterfølgerens minimumsnøkkel i rekkefølge.
• 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 maksimumselementet i forgjengerundertreet i rekkefølge
• Hvis målet etter sletting har mindre enn min-nøkler, vil målnoden låne maksverdi fra søsken via søskens forelder.
• Maksverdien til forelderen vil bli tatt av et mål, men med nodene til maksverdien til søsken.

La oss nå forstå sletteoperasjonen med et eksempel.

Diagrammet ovenfor viser forskjellige tilfeller av sletteoperasjoner i et B-tre. Dette B-treet er av størrelsesorden 5, som betyr at minimumsantallet barnenoder en node kan ha er 3, og det maksimale antallet barnenoder 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 minimumsnøkler
• Bare slett nøkkelen

I eksemplet ovenfor:

• Målnoden har nøkler som tilsvarer minimumsnøkler, så den kan ikke slettes direkte da den vil bryte vilkårene

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

• Målnoden vil låne en nøkkel fra umiddelbar søsken, i dette tilfellet forgjenger i rekkefølge (venstre søsken) fordi den ikke har noen etterfølger i rekkefølge (høyre søsken)
• Maksimumsverdien til inorder-forgjengeren vil bli overført til overordnet, og overordnet vil overføre maksimalverdien 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 umiddelbar søsken, i dette tilfellet, i rekkefølge etterfølger (høyre søsken) fordi dens forgjenger i rekkefølge (venstre søsken) har nøkler 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 til målnoden. Derfor er sammenslåing nødvendig.

Se prosedyren for å slette en slik nøkkel:

• Slå sammen målnoden med noen av dens umiddelbare søsken sammen med overordnet nøkkel
• Nøkkelen fra den overordnede noden velges som søsken mellom de to sammenslående nodene
• Slett målnøkkelen fra den sammenslåtte noden

Delete Operapseudokode

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

Produksjon:

Det største elementet slettes fra B-treet.

Sammendrag

• B Tree er en selvbalanserende datastruktur for bedre søk, innsetting og sletting av data fra disken.
• B Tre er regulert av graden angitt
• B Trenøkler og noder er ordnet i stigende rekkefølge.
• Søkeoperasjonen til B Tree er den enkleste, som alltid starter fra roten og begynner å sjekke om målnøkkelen er større eller mindre enn nodeverdien.
• Innsettingsoperasjonen til B Tree er ganske detaljert, som først finner en passende innsettingsposisjon for målnøkkelen, setter den inn, evaluerer gyldigheten av B Tree mot forskjellige tilfeller, og deretter omstrukturerer B Tree-nodene deretter.
• Slettingsoperasjonen til B Tree søker først etter målnøkkelen som skal slettes, sletter den, evaluerer gyldigheten basert på flere tilfeller som minimums- og maksimumsnøkler til målnoden, søsken og forelder.