B-træ i datastruktur: Søg, indsæt, slet

Hvad er et B-træ?

B Træ er en selvbalancerende datastruktur baseret på et specifikt sæt regler for at søge, indsætte og slette data på en hurtigere og hukommelseseffektiv måde. For at opnå dette følges følgende regler for at oprette et B-træ.

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

Regler for B-Tree

Her er vigtige regler for at oprette et B-træ:

• Alle blade vil blive oprettet på samme niveau.
• Et B-træ bestemmes af et antal grader, som også kaldes "orden" (specificeret af en ekstern aktør, såsom en programmør), omtalt som 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 nøgler, som en rodnode samt dens undernoder kan indeholde, beregnes ved hjælp af denne formel: m − 1. For eksempel:

  m = 4
  max keys: 4 − 1 = 3

• Hver node, undtagen roden, skal indeholde et minimum antal nøgler af [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 et B-træ:

• Reducerer antallet af læsninger på disken.
• B-træer kan nemt optimeres for at justere deres størrelse (dvs. antallet af underordnede noder) 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 gemmes på disken i blokke. Når disse data overføres til hovedhukommelsen (eller RAM), kaldes de en datastruktur.
• I tilfælde af enorme mængder data kræver søgning efter én post på disken læsning af hele disken; dette øger tid og forbrug af hovedhukommelse på grund af høj diskadgangsfrekvens og datastørrelse.
• For at overkomme dette oprettes der indekstabeller, der gemmer postreferencen for posterne baseret på de blokke, de befinder sig i. Dette reducerer tids- og hukommelsesforbruget drastisk.
• Da vi har enorme data, kan vi oprette indekstabeller på flere niveauer.
• Et flerniveauindeks kan designes ved hjælp af et B-træ til keeping dataene sorteres på en selvbalancerende måde.

Søg Operation

Søgeoperationen er den enkleste operation på et B-træ. Følgende algoritme anvendes:

• Lad nøglen (værdien), der skal søges efter, være “k”.
• Begynd at søge fra roden og kryds rekursivt ned.
• Hvis k er mindre end rodværdien, søg i det 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 et B-træ er et selvbalancerende træ, kan man ikke tvinge en nøgle ind 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.

I ovenstående eksempel:

• Søg efter den relevante position i noden for nøglen.
• Indsæt nøglen i målnoden, og kontroller reglerne.
• Har noden efter indsættelse mere end eller lig med det minimale antal nøgler, som er 1? I dette tilfælde ja, det har den. Tjek den næste regel.
• Har noden efter indsættelse mere end det maksimale antal nøgler, som er 3? I dette tilfælde nej, det har den ikke. Det 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 vil splittes, og den midterste nøgle bliver rodnoden for resten af ​​de to noder.
• I tilfælde af et lige antal nøgler, vil den midterste node blive valgt ved venstrebias eller højrebias.

I ovenstående eksempel:

• Noden har færre end det maksimale antal nøgler.
• 1 er indsat ud for 3, men reglen for stigende rækkefølge er overtrådt.
• For at løse dette er nøglerne sorteret.

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

I ovenstående eksempel:

• Noden har nøgler svarende til max nøgler.
• Nøglen er indsat i målnoden, men den overtræder reglen om maksimalt antal 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

Sletteoperationen har flere regler end indsættelses- og søgeoperationerne. Følgende algoritme gælder:

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

Hvis målnøglen er i bladknuden

• Target er i bladnoden, mere end min-nøgler. Sletning af dette vil ikke krænke egenskaben for B-træet.
• Target er i bladnoden, og den har min-nøglenoder. Sletning af dette vil krænke B-træets egenskab.
• Målnoden kan låne en nøgle fra den umiddelbare venstre node eller den umiddelbare højre node (søskende).
• Søskende vil sige Ja hvis den har mere end det minimale antal nøgler.
• Nøglen lånes fra den overordnede node, den maksimale værdi overføres til den overordnede node, den maksimale værdi fra den overordnede node overføres til målnoden, og målværdien fjernes.
• Target er i bladnoden, men ingen søskende har mere end det minimale antal nøgler: søg efter nøglen, flet med søskende og minimum antallet af overordnede noder, det samlede antal nøgler vil nu være mere end min, og målnøglen vil blive erstattet med minimum antallet af en overordnet node.

Hvis målnøglen er i en intern node

• Vælg enten en forgænger i rækkefølge eller en efterfølger i rækkefølge.
• I tilfælde af en forgænger i rækkefølge, vil den maksimale nøgle fra dens venstre undertræ blive valgt.
• I tilfælde af en efterfølger i en bestemt rækkefølge, vil den minimale nøgle fra dens 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 max-tasten 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 den rækkefølgefølgende minimumsnøgle.
• 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 foregående undertræ i rækkefølge.
• Hvis målet efter sletning har færre end min. nøgler, låner målnoden den maksimale værdi fra sin søskende via søskendenodens forælder.
• Den maksimale værdi af den forælder vil blive taget af målet, men med noderne med den maksimale værdi af den søskende.

Lad os nu forstå sletningsoperationen med et eksempel.

Ovenstående diagram viser forskellige tilfælde af sletteoperationen i et B-træ. Dette B-træ er af orden 5, hvilket betyder, at det mindste antal underordnede noder, en node kan have, er 3, og det maksimale antal underordnede noder, en node kan have, er 5. Hvorimod det mindste og maksimale antal nøgler, en node kan have, er henholdsvis 2 og 4.

I ovenstående eksempel:

• Målnoden har målnøglen, der skal slettes.
• Målnoden har flere nøgler end minimumsantallet af nøgler.
• Slet blot nøglen.

I ovenstående eksempel:

• Målnoden har nøgler lig med minimumsnøgler, så vi kan ikke slette den direkte, da det vil overtræde betingelserne.

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

• Målnoden låner en nøgle fra en umiddelbart søskende, i dette tilfælde forgængeren i samme rækkefølge (venstre søskende), fordi den ikke har nogen efterfølger i samme rækkefølge (højre søskende).
• Den maksimale værdi af forgængeren i rækkefølge overføres til den overordnede nod, og den overordnede nod overfører den maksimale værdi til målnoden (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ålnoden låner en nøgle fra en umiddelbar søskende, i dette tilfælde den rækkefølgesvise efterfølger (højre søskende), fordi dens rækkefølgesvise forgænger (venstre søskende) har nøgler lig med minimum af nø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ålnoden ingen søskende, der kan give sin nøgle til målnoden. Derfor er sammenlægning påkrævet. Se proceduren for sletning af en sådan nøgle:

• Flet målnoden med en af ​​dens umiddelbare søskende sammen med den overordnede nøgle.
• Nøglen fra den overordnede node vælges, som sidder mellem de to fusionerende noder.
• Slet målnøglen fra den fusionerede node.

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

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

Ofte Stillede Spørgsmål