I det følgende selvstudie lærer vi om B Tree-datastrukturen og overvejer at visualisere den.
Så lad os komme i gang.
Hvad er et B-træ?
Det B Træ er en speciel type flervejs søgetræ , almindeligvis kendt som M-vej træ, som balancerer sig selv. På grund af deres afbalancerede struktur bliver disse træer almindeligvis brugt til at drive og administrere enorme databaser og forenkle søgninger. I et B-træ kan hver node højst have n underordnede noder. B Tree er et eksempel på Multilevel Indexing i et Database Management System (DBMS). Blad- og interne noder vil begge have postreferencer. B Tree er kendt som Balanced Stored Tree, fordi alle bladknuderne er på samme niveau.
Følgende diagram er et eksempel på et B-træ:
Figur 1. A B Træ med rækkefølge 3
Forstå reglerne for B-træet
Følgende er de vigtige egenskaber ved et B-træ:
- Alle bladknuderne er på samme niveau.
- B-træets datastruktur er defineret af udtrykket minimumsgrad 'd'. Værdien af 'd' afhænger af størrelsen af diskblokken.
- Hver node, undtagen roden, skal bestå af mindst d-1 nøgler. Rodnoden kan bestå af minimum 1 nøgle.
- Alle noder (inklusive rodknuden) må højst bestå af (2d-1) nøgler.
- Antallet af børn i en node er lig med tilføjelse af antallet af nøgler til stede i det og .
- Alle nøgler i en node er sorteret i stigende rækkefølge. Barnet mellem to nøgler, k1 og k2, består af alle nøglerne mellem henholdsvis k1 og k2.
- I modsætning til det binære søgetræ vokser B-træets datastruktur og krymper fra roden. Hvorimod det binære søgetræ vokser nedad og krymper nedad.
- I lighed med andre selvafbalancerede binære søgetræer er tidskompleksiteten af B-træets datastruktur for operationer som søgning, indsættelse og sletning. O(log?n) .
- Indsættelsen af en knude i B-træet sker kun ved bladknuden.
Lad os overveje følgende eksempel på et B-træ med minimumsorden 5.
nummerering af alfabetet
Figur 2. A B Ordenstræ 5
Bemærk: Værdien af minimumsordren er meget mere end 5 i en praktisk B-træer.
I ovenstående diagram kan vi observere, at alle bladknuder er på samme niveau, og alle ikke-bladknuder har intet tomt undertræ og består af nøgler en mindre end antallet af deres børn.
Den faste formulering af B-træets regler:
Hvert B-træ afhænger af et positivt konstant heltal kendt som MINIMUM , som bruges til at bestemme antallet af dataelementer, der kan opbevares i en enkelt node.
Regel 1: Roden kan have så få som kun ét dataelement (eller endda ingen dataelementer, hvis det heller ikke er underordnede); hver anden node har mindst MINIMUM dataelementer.
Regel 2: Det maksimale antal dataelementer, der er gemt i en node, er det dobbelte af værdien af MINIMUM .
Regel 3: Dataelementerne i hver knude i B-træet er lagret i et delvist fyldt array, sorteret fra det mindste dataelement (ved indeks 0 ) til det største dataelement (ved den endelige udnyttede position af arrayet).
Regel 4: Det samlede antal undertræer under en ikke-bladsknude er altid én mere end antallet af dataelementer i den node.
- undertræ 0, undertræ 1,...
Regel 5: Med hensyn til enhver ikke-bladsknude:
- Et dataelement ved indeks er større end alle dataelementerne i undertrænummeret jeg af noden, og
- Et dataelement ved indeks er mindre end alle dataelementerne i undertrænummeret i+1 af noden.
Regel 6: Hvert blad i et B-træ har samme dybde. Dermed sikrer det, at et B-træ forhindrer problemet med et ubalanceret træ.
Operationer på en B-træ-datastruktur
For at sikre, at ingen af egenskaberne for en B-træ-datastruktur krænkes under operationerne, kan B-træet opdeles eller sammenføjes. Følgende er nogle operationer, som vi kan udføre på et B-træ:
- Søgning efter et dataelement i B Tree
- Indsættelse af et dataelement i B Tree
- Sletning af et dataelement i B Tree
Søgeoperation på et B-træ
Søgning efter et element i et B-træ ligner det i et binært søgetræ. Men i stedet for at tage en tovejsbeslutning (venstre eller højre) som et binært søgetræ, træffer et B-træ en m-vejsbeslutning ved hver node, hvor m er antallet af børn i noden.
Trin til at søge efter et dataelement i et B-træ:
c#
Trin 1: Søgningen begynder fra rodnoden. Sammenlign søgeelementet k med roden.
Trin 1.1: Hvis rodknuden består af elementet k, vil søgningen være færdig.
Trin 1.2: Hvis elementet k er mindre end den første værdi i roden, vil vi flytte til barnet længst til venstre og søge efter barnet rekursivt.
Trin 1.3.1: Hvis roden kun har to børn, flytter vi til barnet længst til højre og søger rekursivt i børneknuderne.
Trin 1.3.2: Hvis roden har mere end to nøgler, vil vi søge i resten.
Trin 2: Hvis elementet k ikke findes efter at have krydset hele træet, er søgeelementet ikke til stede i B-træet.
Lad os visualisere ovenstående trin ved hjælp af et eksempel. Antag, at vi ønskede at søge efter en nøgle k=34 i følgende B-træ:
Figur 3.1. Et givet B-træ
- Først vil vi kontrollere, om nøglen k = 34 er ved rodknuden. Da nøglen ikke er ved roden, går vi videre til dens underordnede noder. Vi kan også observere, at rodknuden har to børn; derfor vil vi sammenligne den nødvendige værdi mellem de to nøgler.
Figur 3.2. Nøglen k er ikke til stede ved roden - Nu hvor vi kan bemærke, at nøglen k er større end rodknuden, dvs. 30, vil vi fortsætte med det rigtige underordnede af roden.
Figur 3.3. Tasten k > 30, flyt til højre barn - Vi vil nu sammenligne nøglen k med værdierne til stede på knudepunktet, dvs. henholdsvis 40 og 50. Da nøglen k er mindre end den venstre nøgle, dvs. 40, vil vi flytte til venstre underordnede af noden.
Figur 3.4. Nøglen k<40, move to left child< li> - Da værdien i venstre underordnede 40 er 34, hvilket er den nødvendige værdi, kan vi konkludere, at nøglen er fundet, og søgeoperationen er fuldført.
Figur 3.4. Nøglen k = 34, venstre barn på 40
Vi sammenlignede nøglen med fire forskellige værdier i ovenstående eksempel, indtil vi fandt den. Den tidskompleksitet, der kræves for søgeoperationen i et B-træ, er således O(log?n) .
Indsættelse af operation på et B-træ
Mens vi indsætter et dataelement i et B-træ, skal vi først kontrollere, om det element allerede er til stede i træet eller ej. Hvis dataelementet findes i B-træet, sker indsættelsesoperationen ikke. Men hvis det ikke er tilfældet, går vi videre med indsættelsen. Der er to scenarier, der skal tages hånd om, mens du indsætter et element i bladknuden:
Trin til at indsætte et dataelement i et B-træ:
Trin 1: Vi starter med at beregne det maksimale antal nøgler i noden på basis af rækkefølgen af B-træet.
Trin 2: Hvis træet er tomt, tildeles en rodknude, og vi indsætter den nøgle, der fungerer som rodknudepunktet.
Trin 3: Vi vil nu søge i den relevante node for indsættelse.
.net tutorial
Trin 4: Hvis noden er fuld:
Trin 4.1: Vi indsætter dataelementerne i stigende rækkefølge.
Trin 4.2: Hvis dataelementerne er større end det maksimale antal nøgler, opdeler vi den fulde node ved medianen.
Trin 4.3: Vi vil skubbe mediantasten opad og opdele venstre og højre tast som venstre og højre underordnede.
Trin 5: Hvis noden ikke er fuld, indsætter vi noden i stigende rækkefølge.
Lad os visualisere ovenstående trin ved hjælp af et eksempel. Antag, at vi skal oprette et B-træ af orden 4. De dataelementer, der skal indsættes i B-træet, er 5,3,21,11,1,16,8,13,4 og 9 .
- Da m er lig med 3, er det maksimale antal nøgler for en node = m-1 = 3-1 = 2 .
- Vi starter med at indsætte 5 i det tomme træ.
Figur 4.1. Indsættelse 5 - Vi vil nu indsætte 3 i træet. Da 3 er mindre end 5, indsætter vi 3 til venstre for 5 i den samme node.
Figur 4.2. Indsættelse 3 - Vi vil nu indsætte 21 i træet, og da 21 er større end 5, vil det blive indsat til højre for 5 i samme knude. Men da vi ved, at det maksimale antal nøgler i noden er 2, vil en af disse nøgler blive flyttet til en node ovenfor for at opdele den. Således vil 5, det midterste dataelement, bevæge sig op, og 3 og 21 bliver henholdsvis dets venstre og højre knudepunkt.
Figur 4.3. Indsættelse 21 - Nu er det tid til at indsætte det næste dataelement, dvs. 11, som er større end 5, men mindre end 21. Derfor vil 11 blive indsat som en nøgle til venstre for noden bestående af 21 som en nøgle.
Figur 4.4. Indsættelse 11 - På samme måde vil vi indsætte det næste dataelement 1 i træet, og som vi kan observere, er 1 mindre end 3; derfor vil den blive indsat som en nøgle til venstre for noden bestående af 3 som en nøgle.
Figur 4.5. Indsættelse 1 - Nu vil vi indsætte dataelement 16 i træet, som er større end 11, men mindre end 21. Antallet af nøgler i den node overstiger dog det maksimale antal nøgler. Derfor vil noden opdeles og flytte den midterste nøgle til roden. Derfor vil 16 blive indsat til højre for de 5, der deler 11 og 21 i to separate knudepunkter.
Figur 4.6. Indsættelse 16 - Dataelementet 8 vil blive indsat som en nøgle til venstre for 11.
Figur 4.7. Indsættelse 8 - Vi vil indsætte 13 i træet, som er mindre end 16 og større end 11. Derfor bør dataelement 13 indsættes til højre for noden bestående af 8 og 11. Men da det maksimale antal nøgler i træet kan kun være 2, vil der ske en opdeling, som flytter det midterste dataelement 11 til ovenstående knudepunkt og 8 og 13 til to separate knudepunkter. Nu vil ovenstående node bestå af 5, 11 og 16, hvilket igen overstiger det maksimale nøgletal. Derfor vil der være endnu en opdeling, hvilket gør dataelementet 11 til rodknudepunktet med 5 og 16 som børn.
Figur 4.8. Indsættelse 13 - Da dataelementet 4 er mindre end 5, men større end 3, vil det blive indsat til højre for knudepunktet bestående af 1 og 3, hvilket vil overskride det maksimale antal nøgler i en knude igen. Derfor vil der opstå et spild igen og flytte 3'eren til den øverste knude ved siden af 5.
Figur 4.9. Indsættelse 4 - Til sidst vil dataelementet 9, som er større end 8, men mindre end 11, blive indsat til højre for knudepunktet bestående af 8 som en nøgle.
Figur 4.10. Indsættelse 9
I ovenstående eksempel har vi udført forskellige sammenligninger. Den første værdi blev direkte indsat i træet; derefter skulle hver værdi sammenlignes med de tilgængelige noder i det pågældende træ. Tidskompleksiteten for indsættelsesoperationen i et B-træ afhænger af antallet af noder og .
Sletning af operation på et B-træ
Sletning af et dataelement på et B-træ indeholder tre primære hændelser:
- Søger den node, hvor nøglen, der skal slettes, findes,
- Sletning af nøglen, og
- Afbalancering af træet evt.
Mens du sletter et element fra træet, kan der opstå en tilstand kendt som Underflow. Underflow opstår, når en node består af mindre end minimumsantallet af nøgler; det burde holde.
Følgende er nogle termer, der skal forstås, før du visualiserer sletnings-/fjernelseshandlingen:
Følgende er tre fremtrædende tilfælde af sletningsoperationen i et B-træ:
Case 1: Sletningen/fjernelsen af nøglen ligger i bladknuden - Denne sag er yderligere opdelt i to forskellige sager:
1. Sletningen/fjernelsen af nøglen krænker ikke egenskaben for det mindste antal nøgler, en node skal have.
Lad os visualisere dette tilfælde ved at bruge et eksempel, hvor vi sletter nøgle 32 fra det følgende B-træ.
Figur 4.1: Sletning af en bladnode-nøgle (32) fra B-træet
Som vi kan observere, krænker sletning af 32 fra dette træ ikke ovenstående egenskab.
2. Sletningen/fjernelsen af nøglen krænker egenskaben for det mindste antal nøgler, en node skal have. I dette tilfælde skal vi låne en nøgle fra dens nærmeste søskendenode i rækkefølgen fra venstre mod højre.
Først vil vi besøge den nærmeste venstresøskende. Hvis venstre søskendenode har mere end et minimum antal nøgler, vil den låne en nøgle fra denne node.
linket liste java
Ellers vil vi tjekke for at låne fra den nærmeste højre søskendenode.
Lad os nu visualisere denne sag ved hjælp af et eksempel, hvor vi vil slette 31 fra ovenstående B-træ. Vi vil låne en nøgle fra venstre søskendenode i dette tilfælde.
Figur 4.2: Sletning af en bladnode-nøgle (31) fra B-træet
Hvis begge de nærliggende søskendenoder allerede består af et minimum antal nøgler, så vil vi flette knudepunktet med enten den venstre søskendeknude eller den højre. Denne proces med fletning udføres gennem den overordnede node.
Lad os visualisere igen ved at slette tasten 30 fra ovenstående B-træ.
læs csv-filen i java
Figur 4.3: Sletning af en bladnode-nøgle (30) fra B-træet
Tilfælde 2: Sletningen/fjernelsen af nøglen ligger i non-Leaf noden - Denne sag er yderligere opdelt i forskellige sager:
1. Den ikke-blade/interne node, som fjernes, erstattes af en forgænger i orden, hvis den venstre underordnede node har mere end minimumsantallet af nøgler.
Lad os visualisere dette tilfælde ved at bruge et eksempel, hvor vi sletter nøglen 33 fra B-træet.
Figur 4.4: Sletning af en bladnode-nøgle (33) fra B-træet
2. Den ikke-blade/interne knude, som fjernes, erstattes af en efterfølger i rækkefølge, hvis den højre underordnede knude har mere end minimumsantallet af nøgler.
Hvis et af børnene har et minimum antal nøgler, vil vi flette venstre og højre underknudepunkt.
Lad os visualisere dette tilfælde ved at slette nøglen 30 fra B-træet.
Figur 4.5: Sletning af en bladnode-nøgle (30) fra B-træet
Efter sammenlægning, hvis forældreknudepunktet har mindre end minimumsantallet af nøgler, kan man lede efter søskende, som i Tilfælde 1 .
Case 3: I det følgende tilfælde skrumper træets højde. Hvis målnøglen ligger i en intern node, og fjernelse af nøglen fører til færre nøgler i noden (hvilket er mindre end det nødvendige minimum), så kig efter forgængeren i rækkefølge og efterfølgeren i rækkefølge. Hvis begge børn har et minimum antal nøgler, kan der ikke lånes. Dette fører til Sag 2(3) , dvs. sammenlægning af underordnede knudepunkter.
Vi vil igen lede efter søskende for at låne en nøgle. Men hvis søskende også består af et minimum antal nøgler, så vil vi flette noden med søskende sammen med forældreknudepunktet og arrangere underordnede noder i henhold til kravene (stigende rækkefølge).
Lad os visualisere dette tilfælde ved hjælp af et eksempel, hvor vi sletter dataelementet 10 fra det givne B-træ.
Figur 4.6: Sletning af en bladnode-nøgle (10) fra B-træet
Tidskompleksiteten i ovenstående eksempler varierer afhængigt af det sted, hvorfra nøglen skal slettes. Tidskompleksiteten for sletningsoperationen i et B-træ er således O(log?n) .
Konklusionen
I denne tutorial har vi lært om B-træet og visualiseret dets forskellige operationer med forskellige eksempler. Vi har også forstået nogle grundlæggende egenskaber og regler for B-træet.