B TRE i datastruktur: Søk, sett inn, slett driftseksempel

Innholdsfortegnelse:

Anonim

Hva er et B-tre?

B Tree er en selvbalanserende datastruktur basert på et bestemt sett med regler for å søke, sette inn og slette dataene 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 kalte den Height Balanced m-way Search Tree. Det hjelper deg med å bevare data sortert og tillatt forskjellige operasjoner som innsetting, søk og sletting på kortere tid.

I denne B-Tree-opplæringen lærer du:

  • Hva er et B-tre?
  • Hvorfor bruke B-Tree
  • Historie av B Tree
  • Søkeoperasjon
  • Sett inn operasjon
  • Slett operasjon

Regler for B-Tree

Her er viktige regler for å lage B_Tree

  • Alle blader blir opprettet på samme nivå.
  • B-Tree bestemmes av et antall grader, som også kalles "orden" (spesifisert av en ekstern aktør, som en programmerer), referert til som 
    m
    og videre. Verdien av 
    m
    avhenger av blokkstørrelsen på disken som data primært ligger på.
  • Det venstre undertreet til noden vil ha mindre verdier enn høyre side av undertreet. Dette betyr at nodene også er sortert i stigende rekkefølge fra venstre til høyre.
  • Maksimalt antall underordnede noder, en rotnode og underordnede noder kan inneholde, beregnes med denne formelen: 
    m - 1
    For eksempel: 
    m = 4max keys: 4 - 1 = 3

  • Hver node, unntatt rot, må inneholde minimum nøkler på 
    [m/2]-1
    For eksempel: 
    m = 4min keys: 4/2-1 = 1
  • Maksimalt antall underordnede noder en node kan ha er lik graden, altså 
    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 som er gjort på disken
  • B Trær kan enkelt optimaliseres for å justere størrelsen (det vil si antall barn noder) i henhold til diskstørrelsen
  • Det er en spesialdesignet teknikk for håndtering av 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

Historie av B Tree

  • Data lagres på disken i blokker. Disse dataene, når de føres inn i hovedminnet (eller RAM), kalles datastruktur.
  • Ved enorme data, må du lese hele disken for å søke etter en post på disken; dette øker tid og hovedminneforbruk på grunn av høy diskfrekvens og datastørrelse.
  • For å overvinne dette lages det indekstabeller som lagrer postreferansen til postene basert på blokkene de ligger i. Dette reduserer tid og minneforbruk drastisk.
  • Siden vi har enorme data, kan vi lage indeks tabeller på flere nivåer.
  • Flernivåindeks kan utformes ved å bruke B Tree for å holde dataene sortert på en selvbalanserende måte.

Søkeoperasjon

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

Følgende algoritme brukes:

  • La nøkkelen (verdien) søkes etter "k".
  • Begynn å søke fra roten og kryss rekursivt nedover.
  • Hvis k er mindre enn rotverdien, søk i venstre undertre, hvis k er større enn rotverdien, søk i høyre undertreet.
  • Hvis noden har funnet k, returnerer du bare noden.
  • Hvis k ikke finnes i noden, krysser du ned til barnet med en større nøkkel.
  • Hvis k ikke finnes i treet, returnerer vi NULL.

Sett inn 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 innsatt nøkkel, vil dele seg fra midtelementet.
  • Midterelementet blir foreldre for de to andre barnenodene.
  • Nodene må ordne nøklene på nytt i stigende rekkefølge.

TIPS

Følgende stemmer ikke med innsettingsalgoritmen:

Siden noden er full, vil den derfor deles, og deretter settes en ny verdi inn

I eksemplet ovenfor:

  • Søk i riktig posisjon i noden etter nøkkelen
  • Sett nøkkelen i målnoden, og se etter regler
  • Etter innføring har noden mer enn lik et minimum antall nøkler, som er 1? I dette tilfellet, ja, det gjør det. Sjekk neste regel.
  • Har noden etter innsetting 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 maksimalt antall nøkler
  • Noden vil splitte, og den midterste nøkkelen blir rotnoden til resten av de to nodene.
  • I tilfelle jevnt antall nøkler vil den midterste noden bli valgt med venstre skjevhet eller høyre skjevhet.

I eksemplet ovenfor:

  • Noden har mindre enn maks nøkler
  • 1 settes inn ved siden av 3, men regelen for stigende orden er brutt
  • For å fikse dette sorteres nøklene

Tilsvarende kan 13 og 2 enkelt settes inn i noden ettersom de oppfyller mindre enn maks nøkkelregelen for nodene.

I eksemplet ovenfor:

  • Noden har nøkler lik maks. Nøkler.
  • Nøkkelen settes inn i målnoden, men den bryter med regelen om maksimale nøkler.
  • Målnoden er delt, og den midterste tasten ved venstre skjevhet er nå overordnet til de nye underordnede nodene.
  • De nye nodene er ordnet i stigende rekkefølge.

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

Slett operasjon

Sletteoperasjonen 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 som ble brukt basert på plasseringen av målnøkkelen, som forklart i de følgende avsnittene

Hvis målnøkkelen er i bladnoden

  • Målet er i bladnoden, mer enn min nøkler.
    • Slette dette vil ikke bryte eiendommen til B Tree
  • Målet er i bladnoden, den har min nøkkelnoder
    • Slette dette vil bryte eiendommen til B Tree
    • Målnode kan låne nøkkel fra umiddelbar venstre node, eller umiddelbar høyre node (søsken)
    • Søsken vil si ja hvis det har mer enn minimum antall nøkler
    • Nøkkelen blir lånt fra foreldrenoden, den maksimale verdien vil bli overført til en overordnet, den maksimale verdien til den overordnede noden vil bli overført til målnoden, og fjern målverdien
  • Målet 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 foreldrenoder
    • Totale nøkler vil nå være mer enn min
    • Målnøkkelen vil bli erstattet med minimum et foreldrenode

Hvis målnøkkelen er i en intern node

  • Enten velg, bestill forgjenger eller ordre etterfølger
  • I tilfelle av forgjengeren i bestilling, velges den maksimale tasten fra venstre undertrær
  • I tilfelle etterfølger i bestilling, velges minimumsnøkkelen fra det høyre undertreet
  • Hvis målnøkkelens forgjengere i rekkefølge har mer enn min-tastene, kan den bare erstatte målnøkkelen med maksimum for forgjengeren i rekkefølge
  • Hvis forløperen for målnøkkelen ikke har mer enn min-nøklene, kan du se etter etterfølgerens minimumsnøkkel.
  • Hvis målnøkkelens forløper og etterfølger i rekkefølge begge har mindre enn min-nøkler, slår du sammen forgjengeren og etterfølgeren.

Hvis målnøkkelen er i en rotnode

  • Bytt ut med det maksimale elementet i forordnet undertreet
  • Hvis målet etter sletting har mindre enn min-nøkler, vil målnoden låne maksimal verdi fra søsken via søskenens foreldre.
  • Maksimumsverdien til foreldrene vil bli tatt av et mål, men med nodene til søskenens maksimale verdi.

La oss nå forstå sletteoperasjonen med et eksempel.

Ovenstående diagram viser forskjellige tilfeller av sletteoperasjoner i et B-tre. Dette B-treet er av rekkefølge 5, noe som betyr at det minste antallet barn noder en node kan ha er 3, og det maksimale antall barn noder en hvilken som helst node kan ha er 5. Mens minimum og et maksimalt antall nøkler en hvilken som helst node kan ha er henholdsvis 2 og 4.

I eksemplet ovenfor:

  • Målnoden har målnøkkelen som skal slettes
  • Målnoden har nøkler mer enn minimumstaster
  • Bare slett nøkkelen

I eksemplet ovenfor:

  • Målnoden har nøkler lik minimumnøkler, så kan ikke slette den direkte, da den bryter med vilkårene

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

  • Målnoden vil låne en nøkkel fra øyeblikkelig søsken, i dette tilfellet forgjengeren i orden (venstre søsken) fordi den ikke har noen etterfølger i ordren (høyre søsken)
  • Maksimumsverdien til bestillingsforgjengeren overføres til foreldrene, og foreldrene 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 etterfølgeren i bestillingen.

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

I eksemplet nedenfor har ikke målnoden noe søsken som kan gi nøkkelen til målnoden. Derfor kreves sammenslåing.

Se fremgangsmåten for å slette en slik nøkkel:

  • Slå sammen målnoden med noen av dens nærmeste søsken sammen med foreldrenøkkelen
    • Nøkkelen fra foreldrenoden er valgt som søsken mellom de to sammenslåtte nodene
  • Slett målnøkkelen fra den sammenslåtte noden

Slett operasjon Pseudo-kode

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

Utgang :

Det største elementet er slettet fra B-treet.

Sammendrag:

  • B Tree er en selvbalanserende datastruktur for bedre søk, innsetting og sletting av data fra disken.
  • B Treet reguleres av den angitte graden
  • B Tre nø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.
  • Sletteoperasjonen til B Tree søker først etter målnøkkelen som skal slettes, sletter den, evaluerer gyldigheten basert på flere tilfeller som minimum og maksimum nøkler til målnoden, søsken og foreldre.