B TRÆ i datastruktur: Søg, Indsæt, Slet Operation eksempel

Regler for B-Tree

Her er vigtige regler for at skabe B_Tree

• Alle blade vil blive oprettet på samme niveau.
• B-Tree er bestemt af et antal grader, som også kaldes "orden" (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.

• Det venstre undertræ af noden vil have mindre værdier end den højre side af undertræet. Det betyder, at noderne også er sorteret i stigende rækkefølge fra venstre mod højre.
• Det maksimale antal underknuder, en rodknude såvel som dens underknudepunkter kan indeholde, beregnes ved hjælp af denne formel:

  m – 1

  For eksempel:

  m = 4
  max keys: 4 – 1 = 3
  

• Hver node, undtagen root, skal indeholde minimum nøgler på

  [m/2]-1

  For eksempel:

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

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

  m

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

Hvorfor bruge B-Tree

Her er grunde til at bruge B-Tree

• Reducerer antallet af aflæsninger foretaget på disken
• B-træer kan nemt optimeres til at justere størrelsen (det vil sige antallet af børneknuder) i henhold til diskstørrelsen
• Det er en specialdesignet teknik til at håndtere 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 at læse og skrive store datablokke

Historien om B Tree

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

Søg Operation

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

Følgende algoritme anvendes:

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

indsatte 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øgeoperationen og find det passende indsættelsessted.
• Indsæt den nye nøgle på det rigtige sted, men hvis noden allerede har et maksimalt antal nøgler:
• Noden vil sammen med en nyligt indsat nøgle opdeles fra det midterste element.
• Det midterste element bliver overordnet for de to andre underordnede noder.
• Noderne skal omarrangere nøgler i stigende rækkefølge.

TIP	Følgende er ikke sandt om indsættelsesalgoritmen: Da noden er fuld, vil den derfor opdeles, og så vil en ny værdi blive indsat

I ovenstående eksempel:

• Søg på den relevante position i noden efter nøglen
• Indsæt nøglen i målknuden, og tjek for regler
• Efter indsættelse, har noden mere end lig med et minimum antal nøgler, som 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. Det betyder, at B-træet ikke overtræder nogen regler, og indsættelsen er gennemført.

I ovenstående eksempel:

• Noden har nået det maksimale antal nøgler
• Noden vil opdeles, og den midterste nøgle bliver rodknuden for de to andre noder.
• I tilfælde af lige antal nøgler, vil den midterste node blive valgt ved venstre bias eller højre bias.

I ovenstående eksempel:

• Noden har mindre end max nøgler
• 1 er indsat ved siden af ​​3, men reglen om stigende orden er overtrådt
• For at rette op på dette, sorteres nøglerne

På samme måde kan 13 og 2 nemt indsættes i noden, da de opfylder mindre end max nøgler for noderne.

I ovenstående eksempel:

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

På samme måde, baseret på ovenstående regler og tilfælde, kan resten af ​​værdierne nemt indsættes i B-træet.

Slette Operation

Sletningsoperationen har flere regler end indsættelses- og søgeoperationer.

Følgende algoritme gælder:

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

Hvis målnøglen er i bladknuden

• Target er i bladknuden, mere end min-taster.
• Sletning af dette vil ikke krænke B Trees ejendom
• Target er i bladknude, den har min nøglenoder
• Sletning af dette vil krænke B Trees ejendom
• Target node kan låne nøgle fra umiddelbar venstre node eller umiddelbar højre node (søskende)
• Søskende vil sige Ja hvis den har mere end minimum antal nøgler
• Nøglen vil blive lånt fra den overordnede node, den maksimale værdi vil blive overført til en forælderen, den maksimale værdi af den overordnede node vil blive overført til den ønskede node, og fjern målværdien
• Target er i bladknuden, men ingen søskende har mere end min antal nøgler
• Søg efter nøgle
• Flet sammen med søskende og minimum af overordnede noder
• Det samlede antal nøgler vil nu være mere end min
• Målnøglen vil blive erstattet med minimum af en overordnet node

Hvis målnøglen er i en intern node

• Vælg enten, bestil forgænger eller i rækkefølge efterfølger
• I tilfælde af en forgænger i rækkefølge, vil den maksimale nøgle fra dets venstre undertræ blive valgt
• I tilfælde af efterfølger i rækkefølge, vil minimumsnøglen fra dets højre undertræ blive valgt
• Hvis målnøglens forgænger i rækkefølge har mere end min-tasterne, kan den kun erstatte målnøglen med maks. for forgængeren i rækkefølge
• Hvis målnøglens forgænger i rækkefølge ikke har mere end min nøgler, skal du kigge efter efterfølgerens minimumnøgle i rækkefølge.
• Hvis målnøglens forgænger og efterfølger i rækkefølge begge har mindre end min-nøgler, så flet forgængeren og efterfølgeren.

Hvis målnøglen er i en rodnode

• Erstat med det maksimale element i det forgængers undertræ i rækkefølge
• Hvis målet efter sletning har mindre end min nøgler, så vil målknuden låne max værdi fra sin søskende via søskendes forælder.
• Den maksimale værdi af forælderen vil blive taget af et mål, men med noderne af maks. værdien for søskende.

Lad os nu forstå sletningsoperationen med et eksempel.

Ovenstående diagram viser forskellige tilfælde af sletning i et B-træ. Dette B-træ er af størrelsesorden 5, hvilket betyder, at det mindste antal underordnede knudepunkter, som enhver knude kan have, er 3, og det maksimale antal underknuder, som enhver knude kan have, er 5. Hvorimod det mindste og et maksimale antal nøgler enhver knude kan have er henholdsvis 2 og 4.

I ovenstående eksempel:

• Målnoden har målnøglen, der skal slettes
• Målknuden har flere nøgler end minimumsnøgler
• Slet blot nøglen

I ovenstående eksempel:

• Målknuden har nøgler svarende til minimumsnøgler, så den kan ikke slettes direkte, da den vil overtræde betingelserne

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

• Målknuden vil låne en nøgle fra den umiddelbare søskende, i dette tilfælde en forgænger i rækkefølge (venstre søskende), fordi den ikke har nogen efterfølger i rækkefølge (højre søskende)
• Den maksimale værdi af den inordnede forgænger vil blive overført til forælderen, og forælderen vil overføre den maksimale værdi til målknuden (se diagrammet nedenfor)

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

• Målknuden vil låne en nøgle fra den umiddelbare søskende, i dette tilfælde, efterfølger i rækkefølge (højre søskende), fordi dens forgænger i rækkefølge (venstre søskende) har nøgler svarende til minimumsnøgler.
• Minimumsværdien af ​​efterfølgeren i rækkefølge vil blive overført til den overordnede, og den overordnede vil overføre den maksimale værdi til målknuden.

I eksemplet nedenfor har målknuden ikke nogen søskende, der kan give sin nøgle til målknuden. Derfor er sammenlægning påkrævet.

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

• Flet målnoden med enhver af dens umiddelbare søskende sammen med overordnet nøgle
• Nøglen fra den overordnede node vælges som søskende i mellem de to fletteknuder
• Slet målnøglen fra den flettede node

Slette Operation pseudokode

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

Produktion:

Det største element slettes fra B-træet.

Resumé

• B Tree er en selvbalancerende datastruktur til bedre søgning, indsættelse og sletning af data fra disken.
• B Træ er reguleret af den angivne grad
• B Trænøgler og noder er arrangeret i stigende rækkefølge.
• Søgeoperationen 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ættelsesoperationen 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 i forhold til forskellige tilfælde og derefter omstrukturerer B Tree-knuderne i overensstemmelse hermed.
• Sletningsoperationen af ​​B Tree søger først efter målnøglen, der skal slettes, sletter den, evaluerer gyldigheden baseret på flere tilfælde som minimums- og maksimumsnøgler for målknuden, søskende og forælder.