B TRÆ i datastruktur: Søg, indsæt, slet driftseksempel

Hvad er et B-træ?

B Tree er en selvbalancerende datastruktur baseret på et specifikt sæt regler til søgning, indsættelse og sletning af dataene på en hurtigere og hukommelseseffektiv måde. For at opnå dette følges følgende regler for at oprette et B-træ.

Et B-Tree er en særlig slags træ i en datastruktur. I 1972 blev denne metode først introduceret af McCreight, og Bayer kaldte den Height Balanced m-way Search Tree. Det hjælper dig med at bevare data sorteret og tilladt forskellige operationer som indsættelse, søgning og sletning på kortere tid.

I denne B-Tree tutorial lærer du:

• Hvad er et B-træ?
• Hvorfor bruge B-Tree
• Historie af B Tree
• Søgning
• Indsæt operation
• Slet handling

Regler for B-Tree

Her er vigtige regler for oprettelse af B_Tree

• Alle blade oprettes på samme niveau.
• B-Tree bestemmes af et antal grader, der også kaldes "rækkefølge" (specificeret af en ekstern aktør, som en programmør), kaldet

  m

  fremad. Værdien af

  m

  afhænger af blokstørrelsen på den disk, hvor data primært er placeret.
• Venstre undertræ i noden vil have mindre værdier end undertræets højre side. Dette betyder, at noderne også er sorteret i stigende rækkefølge fra venstre til højre.
• Det maksimale antal underordnede noder, en rodnode såvel som dens underordnede noder kan indeholde beregnes ved hjælp af denne formel:

  m - 1

  For eksempel:

  m = 4max keys: 4 - 1 = 3

• Hver knude undtagen rod skal indeholde mindst nøgler på

  [m/2]-1

  For eksempel:

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

• Det maksimale antal underordnede noder, som en node kan have, er lig med dens grad, hvilket er

  m

• Det mindste børn, som en node kan have, er halvdelen af ​​ordren, hvilket er m / 2 (loftværdien tages).
• Alle nøgler i en node sorteres i stigende rækkefølge.

Hvorfor bruge B-Tree

Her er grunde til at bruge B-Tree

• Reducerer antallet af læsninger, der er foretaget på disken
• B Træer kan let optimeres for at justere dens størrelse (det vil sige antallet af underordnede noder) i henhold til diskstørrelsen
• Det er en specielt designet teknik til håndtering af en stor mængde data.
• Det er en nyttig algoritme til databaser og filsystemer.
• Et godt valg at vælge, når det kommer til læsning og skrivning af store datablokke

Historie af B Tree

• Data gemmes på disken i blokke, når disse data bringes i hovedhukommelsen (eller RAM) kaldes datastruktur.
• I tilfælde af enorme data kræver søgning efter en post på disken læsning af hele disken; dette øger tid og hovedhukommelsesforbrug på grund af høj diskadgangsfrekvens og datastørrelse.
• For at overvinde dette oprettes der indekstabeller, der gemmer postreferencen for posterne baseret på de blokke, de ligger i. Dette reducerer tid og hukommelsesforbrug drastisk.
• Da vi har enorme data, kan vi oprette indekstabeller på flere niveauer.
• Multi-level index kan designes ved hjælp af B Tree til at holde dataene sorteret på en selvbalancerende måde.

Søgning

Søgeoperationen er den enkleste operation på B Tree.

Følgende algoritme anvendes:

• Lad nøglen (værdien) søges efter "k".
• Begynd at søge fra roden og kryds rekursivt ned.
• Hvis k er mindre end rodværdien, skal du søge i venstre undertræ. Hvis k er større end rodværdien, skal du søge i det højre undertræ.
• Hvis noden har fundet k, skal du blot returnere noden.
• Hvis k ikke findes i noden, skal du krydse ned til barnet med en større nøgle.
• Hvis k ikke findes i træet, returnerer vi NULL.

Indsæt operation

Da B Tree er et selvbalancerende træ, kan du ikke tvinge indsættelse af en nøgle i en hvilken som helst node.

Følgende algoritme gælder:

• Kør søgningen og find det rette sted for indsættelse.
• Indsæt den nye nøgle på det rette sted, men hvis noden allerede har et maksimalt antal nøgler:
• Noden sammen med en nyindsat nøgle deles fra det midterste element.
• Det midterste element bliver forælder til de to andre underordnede noder.
• Knudepunkterne skal omarrangere nøgler i stigende rækkefølge.

TIP	Følgende gælder ikke for indsættelsesalgoritmen: Da noden er fuld, vil den blive delt, og derefter indsættes en ny værdi

I ovenstående eksempel:

• Søg efter den rette position i noden efter nøglen
• Indsæt nøglen i målnoden, og kontroller for regler
• Efter indsættelse har noden mere end lig med et minimum antal nøgler, hvilket er 1? I dette tilfælde, ja, det gør det. Tjek den næste regel.
• Efter indsættelse har noden mere end et maksimalt antal nøgler, hvilket er 3? I dette tilfælde nej, det gør det ikke. Dette betyder, at B-træet ikke overtræder nogen regler, og indsættelsen er fuldført.

I ovenstående eksempel:

• Noden har nået det maksimale antal nøgler
• Noden opdeles, og den midterste nøgle bliver rodnoden for de øvrige to noder.
• I tilfælde af et lige antal nøgler vælges den midterste knude ved venstre bias eller højre bias.

I ovenstående eksempel:

• Noden har mindre end max nøgler
• 1 indsættes ud for 3, men reglen om stigende rækkefølge er overtrådt
• For at løse dette sorteres tasterne

Tilsvarende kan 13 og 2 let indsættes i noden, da de opfylder mindre end max nøglereglen for noderne.

I ovenstående eksempel:

• Noden har nøgler svarende til max nøgler.
• Nøglen indsættes i målnoden, men den overtræder reglen om maks. Nøgler.
• Målknudepunktet er delt, og den midterste nøgle ved venstre bias er nu overordnet til de nye underknudepunkter.
• De nye noder er arrangeret i stigende rækkefølge.

Baseret på ovenstående regler og tilfælde kan resten af ​​værdierne ligeledes nemt indsættes i B-træet.

Slet handling

Sletningen har flere regler end indsætnings- og søgefunktioner.

Følgende algoritme gælder:

• Kør søgningen og find målnøglen i noderne
• Tre anvendte betingelser baseret på placeringen af ​​målnøglen som forklaret i de følgende afsnit

Hvis målnøglen er i bladnoden

• Målet er i bladknudepunktet, mere end min. Nøgler.
  • Sletning af dette vil ikke krænke B Tree's ejendom
• Målet er i bladknude, det har min nøglenoder
  • Sletning af dette vil krænke B Tree's ejendom
  • Målknudepunkt kan låne nøgle fra umiddelbar venstre knude eller umiddelbar højre knude (søskende)
  • Søskende vil sige ja, hvis det har mere end minimum antal nøgler
  • Nøglen lånes fra den overordnede node, den maksimale værdi overføres til en forælder, den maksimale værdi af den overordnede node overføres til målnoden, og fjern målværdien
• Målet er i bladknudepunktet, men ingen søskende har mere end min antal nøgler
  • Søg efter nøgle
  • Flet med søskende og minimum af forældrenoder
  • De samlede nøgler vil nu være mere end min
  • Målnøglen erstattes med minimumet af en overordnet node

Hvis målnøglen er i en intern node

• Enten vælg, rækkefølge forgænger eller ordre efterfølger
• Hvis forgængeren er i orden, vælges den maksimale nøgle fra det venstre undertræ
• I tilfælde af efterfølger efter ordre vælges minimumsnøglen fra dens højre undertræ
• Hvis målnøglens bestilte forgænger har mere end min-tasterne, kan den kun erstatte målnøglen med maksimum for forgængeren i rækkefølge
• Hvis målnøglens bestilte forgænger ikke har mere end min-nøgler, skal du kigge efter efterfølgerens minimumnøgle i rækkefølge.
• Hvis målnøglens ordregivende forgænger og efterfølger begge har mindre end min-nøgler, skal du flette forgængeren og efterfølgeren.

Hvis målnøglen er i en rodnode

• Udskift med det maksimale element i underordnet i forudgående rækkefølge
• Hvis målet efter sletning har mindre end min-nøgler, låner målnoden maksimumsværdien fra sin søskende via søskens forælder.
• Forældrenes maksimale værdi tages af et mål, men med noder for søskendets maksimale værdi.

Lad os nu forstå sletteoperationen med et eksempel.

Ovenstående diagram viser forskellige tilfælde af sletning i et B-Tree. Dette B-træ er af rækkefølge 5, hvilket betyder, at det mindste antal underordnede noder, som enhver node kan have, er 3, og det maksimale antal underordnede noder, som enhver node kan have, er 5. Mens minimum og et maksimalt antal nøgler, hvilken som helst node kan have henholdsvis 2 og 4.

I ovenstående eksempel:

• Målnoden har den målnøgle, der skal slettes
• Målknudepunktet har nøgler mere end minimumnøgler
• Slet blot nøglen

I ovenstående eksempel:

• Målknudepunktet har nøgler svarende til minimumnøgler, så det kan ikke slettes direkte, da det overtræder betingelserne

Nu forklarer følgende diagram, hvordan du sletter denne nøgle:

• Målknudepunktet låner en nøgle fra det øjeblikkelige søskende, i dette tilfælde ordregivende forgænger (venstre søskende), fordi den ikke har nogen efterfølger i rækkefølge (højre søskende)
• Den maksimale værdi af inorder-forgængeren overføres til forælderen, og forælderen overfører den maksimale værdi til målnoden (se diagrammet nedenfor)

Følgende eksempel illustrerer, hvordan du sletter en nøgle, der har brug for en værdi fra sin efterfølger i rækkefølge.

• Målknudepunktet låner en nøgle fra det umiddelbare søskende, i dette tilfælde efterfølger i rækkefølge (højre søskende), fordi det er i rækkefølge, at forgængeren (venstre søskende) har nøgler svarende til minimumstaster.
• Minimumsværdien af ​​efterfølgeren i ordren overføres til forælderen, og forælderen overfører den maksimale værdi til målnoden.

I eksemplet nedenfor har målnoden ingen søskende, der kan give sin nøgle til målnoden. Derfor er fletning påkrævet.

Se proceduren for sletning af en sådan nøgle:

• Flet målknudepunktet med nogen af ​​dets umiddelbare søskende sammen med forældrenøglen
  • Nøglen fra den overordnede knudepunkt er valgt, at søskende mellem de to fusionerende noder
• Slet målnøglen fra den flettede node

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

Output :

Det største element slettes fra B-Tree.

Resumé:

• B Tree er en selvbalancerende datastruktur til bedre søgning, indsættelse og sletning af data fra disken.
• B Træet reguleres af den angivne grad
• B Trænøgler og noder er arrangeret i stigende rækkefølge.
• Søgningen af ​​B Tree er den enkleste, som altid starter fra roden og begynder at kontrollere, om målnøglen er større eller mindre end nodeværdien.
• Indsætningsoperationen af ​​B Tree er ret detaljeret, som først finder en passende indsættelsesposition for målnøglen, indsætter den, evaluerer gyldigheden af ​​B Tree mod forskellige tilfælde og derefter omstrukturerer B Tree-noderne i overensstemmelse hermed.
• Sletningsoperationen af ​​B Tree søger først efter den målnøgle, der skal slettes, sletter den, evaluerer gyldigheden baseret på flere tilfælde som minimum og maksimum nøgler til målnoden, søskende og forælder.