B STABLO u strukturi podataka: pretraživanje, umetanje, brisanje Operacija Primjer

Pravila za B-Tree

Ovdje su važna pravila za stvaranje B_Tree

• Svi listovi će biti stvoreni na istoj razini.
• B-stablo je određeno brojem stupnjeva, koji se također naziva "poredak" (određen od strane vanjskog aktera, poput programera), koji se naziva

  m

  pa nadalje. Vrijednost

  m

  ovisi o veličini bloka na disku na kojem se primarno nalaze podaci.

• Lijevo podstablo čvora imat će manje vrijednosti od desne strane podstabla. To znači da su čvorovi također poredani uzlaznim redoslijedom s lijeva na desno.
• Maksimalni broj podređenih čvorova, korijenski čvor kao i njegovi podređeni čvorovi mogu sadržavati izračunava se prema ovoj formuli:

  m – 1

  Na primjer:

  m = 4
  max keys: 4 – 1 = 3
  

• Svaki čvor, osim korijena, mora sadržavati minimalne ključeve od

  [m/2]-1

  Na primjer:

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

• Maksimalni broj podređenih čvorova koji čvor može imati jednak je njegovom stupnju, što je

  m

• Najmanji broj djece koju čvor može imati je polovica reda, što je m/2 (uzima se gornja vrijednost).
• Svi ključevi u čvoru poredani su rastućim redoslijedom.

Zašto koristiti B-Tree

Ovdje su razlozi korištenja B-Tree

• Smanjuje broj čitanja napravljenih na disku
• B Stabla se mogu lako optimizirati za prilagodbu veličine (to je broj čvorova djece) prema veličini diska
• To je posebno dizajnirana tehnika za rukovanje velikom količinom podataka.
• To je koristan algoritam za baze podataka i datotečne sustave.
• Dobar izbor kada se radi o čitanju i pisanju velikih blokova podataka

Povijest B stabla

• Podaci se pohranjuju na disku u blokovima, ti podaci, kada se unesu u glavnu memoriju (ili RAM) nazivaju se strukturom podataka.
• U slučaju velikih podataka, pretraživanje jednog zapisa na disku zahtijeva čitanje cijelog diska; to povećava potrošnju vremena i glavne memorije zbog visoke učestalosti pristupa disku i veličine podataka.
• Kako bi se to prevladalo, kreiraju se indeksne tablice koje spremaju referencu zapisa zapisa na temelju blokova u kojima se nalaze. To drastično smanjuje potrošnju vremena i memorije.
• Budući da imamo ogromne podatke, možemo izraditi indeksne tablice na više razina.
• Indeks na više razina može se dizajnirati korištenjem B stabla za održavanje sortiranih podataka na samouravnotežujući način.

Traži OperaANJE

Operacija pretraživanja je najjednostavnija operacija na B stablu.

Primjenjuje se sljedeći algoritam:

• Neka ključ (vrijednost) koju treba pretraživati ​​pomoću “k”.
• Započnite pretraživanje od korijena i rekurzivno idite prema dolje.
• Ako je k manji od korijenske vrijednosti, pretraži lijevo podstablo, ako je k veće od korijenske vrijednosti, pretraži desno podstablo.
• Ako čvor ima pronađeno k, jednostavno vratite čvor.
• Ako k nije pronađen u čvoru, idite dolje do djeteta s većim ključem.
• Ako k nije pronađen u stablu, vraćamo NULL.

umetak OperaANJE

Budući da je B stablo stablo koje se samo balansira, ne možete prisilno umetnuti ključ u bilo koji čvor.

Primjenjuje se sljedeći algoritam:

• Pokrenite operaciju pretraživanja i pronađite odgovarajuće mjesto umetanja.
• Umetnite novi ključ na odgovarajuće mjesto, ali ako čvor već ima maksimalan broj ključeva:
• Čvor će se zajedno s novoumetnutim ključem odvojiti od srednjeg elementa.
• Srednji element postat će roditelj za druga dva podređena čvora.
• Čvorovi moraju preurediti ključeve uzlaznim redoslijedom.

SAVJET

Sljedeće nije točno u vezi s algoritmom umetanja: Budući da je čvor pun, stoga će se podijeliti, a zatim će se umetnuti nova vrijednost

U gornjem primjeru:

• Potražite ključ na odgovarajućem mjestu u čvoru
• Umetnite ključ u ciljni čvor i provjerite pravila
• Nakon umetanja, ima li čvor više od minimalnog broja ključeva, koji je 1? U ovom slučaju, da, ima. Provjerite sljedeće pravilo.
• Nakon umetanja, ima li čvor više od maksimalnog broja ključeva, koji je 3? U ovom slučaju, ne, nije. To znači da stablo B ne krši nikakva pravila i da je umetanje dovršeno.

U gornjem primjeru:

• Čvor je dosegao najveći broj ključeva
• Čvor će se podijeliti, a srednji ključ će postati korijenski čvor preostala dva čvora.
• U slučaju parnog broja ključeva, srednji čvor će biti odabran lijevim ili desnim prednaprezanjem.

U gornjem primjeru:

• Čvor ima manje od maksimalnog broja ključeva
• 1 je umetnut pored 3, ali je prekršeno pravilo uzlaznog redoslijeda
• Kako bi se to popravilo, ključevi su sortirani

Slično, 13 i 2 mogu se lako umetnuti u čvor budući da ispunjavaju pravilo manje od maksimalnog broja ključeva za čvorove.

U gornjem primjeru:

• Čvor ima ključeve jednake max ključevima.
• Ključ je umetnut u ciljni čvor, ali krši pravilo maksimalnog broja ključeva.
• Ciljni čvor je podijeljen, a srednji ključ prema lijevoj pristranosti sada je roditelj novih podređenih čvorova.
• Novi čvorovi raspoređeni su uzlaznim redoslijedom.

Slično, na temelju gornjih pravila i slučajeva, ostale vrijednosti mogu se jednostavno umetnuti u B stablo.

Izbrisati OperaANJE

Operacija brisanja ima više pravila od operacija umetanja i pretraživanja.

Primjenjuje se sljedeći algoritam:

• Pokrenite operaciju pretraživanja i pronađite ciljni ključ u čvorovima
• Tri su uvjeta primijenjena na temelju lokacije ciljnog ključa, kao što je objašnjeno u sljedećim odjeljcima

Ako je ciljni ključ u čvoru lista

• Target je u čvoru lista, više od min ključeva.
• Ovo brisanje neće narušiti svojstvo B stabla
• Target je u lisnom čvoru, ima min ključnih čvorova
• Brisanjem ovoga narušit ćete svojstvo B stabla
• Target čvor može posuditi ključ od neposrednog lijevog čvora ili neposrednog desnog čvora (brat)
• Brat će reći Da ako ima više od minimalnog broja ključeva
• Ključ će se posuditi od nadređenog čvora, maksimalna vrijednost će se prenijeti roditelju, maksimalna vrijednost nadređenog čvora prenijet će se ciljnom čvoru i ukloniti ciljnu vrijednost
• Target je u lisnom čvoru, ali nijedna braća i sestre nemaju više od minimalnog broja ključeva
• Traži ključ
• Spajanje s braćom i sestrama i minimalnim nadređenim čvorovima
• Ukupni ključevi sada će biti veći od min
• Ciljni ključ bit će zamijenjen minimumom nadređenog čvora

Ako je ciljni ključ u unutarnjem čvoru

• Ili odaberite, prethodnik po redu ili nasljednik po redu
• U slučaju prethodnika po redu, bit će odabran maksimalni ključ iz njegovog lijevog podstabla
• U slučaju nasljednika po redu, bit će odabran minimalni ključ iz njegovog desnog podstabla
• Ako redoslijed prethodnika ciljnog ključa ima više od min ključeva, samo tada može zamijeniti ciljni ključ maksimumom redoslijeda prethodnika
• Ako redoslijed prethodnika ciljnog ključa nema više od min ključeva, potražite minimalni ključ redoslijeda nasljednika.
• Ako redoslijed prethodnika i nasljednika ciljnog ključa imaju manje od min ključeva, tada spojite prethodnika i nasljednika.

Ako je ciljni ključ u korijenskom čvoru

• Zamijenite maksimalnim elementom podstabla prethodnika prema redoslijedu
• Ako, nakon brisanja, cilj ima manje od min ključeva, tada će ciljni čvor posuditi maksimalnu vrijednost od svog brata preko roditelja brata.
• Maksimalnu vrijednost roditelja preuzet će cilj, ali s čvorovima maksimalne vrijednosti brata ili sestre.

Razmotrimo sada operaciju brisanja na primjeru.

Gornji dijagram prikazuje različite slučajeve operacije brisanja u B-stablu. Ovo B-stablo je reda 5, što znači da je najmanji broj podređenih čvorova koje svaki čvor može imati 3, a maksimalan broj podređenih čvorova koji bilo koji čvor može imati je 5. Dok je minimalni i maksimalni broj ključeva bilo kojeg čvora mogu imati 2 odnosno 4.

U gornjem primjeru:

• Ciljni čvor ima ciljni ključ za brisanje
• Ciljni čvor ima više ključeva od minimalnog broja ključeva
• Jednostavno izbrišite ključ

U gornjem primjeru:

• Ciljni čvor ima ključeve jednake minimalnim ključevima, pa ga ne možete izravno izbrisati jer će prekršiti uvjete

Sada, sljedeći dijagram objašnjava kako izbrisati ovaj ključ:

• Ciljni čvor će posuditi ključ od neposrednog brata, u ovom slučaju, prethodnika po redu (lijevog brata) jer nema nasljednika po redu (desnog brata)
• Maksimalna vrijednost redoslijeda prethodnika će se prenijeti na roditelja, a roditelj će prenijeti maksimalnu vrijednost na ciljni čvor (pogledajte dijagram u nastavku)

Sljedeći primjer ilustrira kako izbrisati ključ koji treba vrijednost od njegovog nasljednika po redu.

• Ciljni čvor će posuditi ključ od neposrednog brata, u ovom slučaju, nasljednika po redu (desni brat) jer njegov prethodnik po redu (lijevi brat) ima ključeve jednake minimalnim ključevima.
• Minimalna vrijednost nasljednika po redu bit će prebačena na roditelja, a roditelj će prenijeti maksimalnu vrijednost na ciljni čvor.

U donjem primjeru, ciljni čvor nema nijednog brata koji može dati svoj ključ ciljnom čvoru. Stoga je potrebno spajanje.

Pogledajte postupak brisanja takvog ključa:

• Spojite ciljni čvor s bilo kojim od njegovih neposrednih srodnika zajedno s nadređenim ključem
• Ključ nadređenog čvora odabire se kao braća i sestre između dva čvora koja se spajaju
• Izbrišite ciljni ključ iz spojenog čvora

Izbrisati Operacijski pseudo kod

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

Izlaz:

Najveći element se briše iz B-stabla.

rezime

• B Tree je struktura podataka koja se sama uravnotežuje za bolje pretraživanje, umetanje i brisanje podataka s diska.
• B Stablo je regulirano navedenim stupnjem
• B Ključevi stabla i čvorovi raspoređeni su uzlaznim redoslijedom.
• Operacija pretraživanja B stabla je najjednostavnija, koja uvijek počinje od korijena i počinje provjeravati je li ciljni ključ veći ili manji od vrijednosti čvora.
• Operacija umetanja B stabla prilično je detaljna, koja prvo pronalazi odgovarajući položaj umetanja za ciljni ključ, umeće ga, procjenjuje valjanost B stabla u odnosu na različite slučajeve, a zatim restrukturira čvorove B stabla u skladu s tim.
• Operacija brisanja B stabla prvo traži ciljni ključ koji treba izbrisati, briše ga, procjenjuje valjanost na temelju nekoliko slučajeva kao što su minimalni i maksimalni ključevi ciljnog čvora, braće i sestara i roditelja.