B stablo u strukturi podataka: pretraživanje, umetanje, brisanje

Što je B stablo?

B Drvo je samobalansirajuća struktura podataka temeljena na određenom skupu pravila za pretraživanje, umetanje i brisanje podataka na brži i memorijski učinkovit način. Kako bi se to postiglo, slijede se sljedeća pravila za stvaranje B stabla.

B-stablo je posebna vrsta stabla u strukturi podataka. Ovu metodu su prvi put predstavili McCreight i Bayer 1972. godine, nazvavši je Visinski uravnoteženo m-smjerno stablo pretraživanja. Pomaže vam u očuvanju sortiranih podataka i omogućuje razne operacije poput umetanja, pretraživanja i brisanja u kraćem vremenu.

Pravila za B-Tree

Evo važnih pravila za stvaranje B-stabla:

• Svi listovi će biti stvoreni na istoj razini.
• B-stablo je određeno brojem stupnjeva, koji se naziva i "red" (određen od strane vanjskog aktera, poput programera), a naziva se 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 ključeva koje korijenski čvor, kao i njegovi podređeni čvorovi, mogu sadržavati izračunava se ovom formulom: m − 1, Na primjer:

  m = 4
  max keys: 4 − 1 = 3

• Svaki čvor, osim korijena, mora sadržavati minimalan broj ključeva [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

Evo razloga za korištenje B-stabla:

• Smanjuje broj čitanja na disku.
• B-stabla se mogu lako optimizirati kako bi se prilagodila njihova veličina (tj. broj podređenih čvorova) 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 je u pitanju čitanje i pisanje velikih blokova podataka.

Povijest B stabla

• Podaci se na disku pohranjuju u blokovima. Ti se podaci, kada se unesu u glavnu memoriju (ili RAM), nazivaju struktura podataka.
• U slučaju velikih količina podataka, traženje jednog zapisa na disku zahtijeva čitanje cijelog diska; to povećava vrijeme i potrošnju glavne memorije zbog velike učestalosti pristupa disku i veličine podataka.
• Kako bi se to prevladalo, stvaraju se indeksne tablice koje spremaju reference zapisa na temelju blokova u kojima se nalaze. To drastično smanjuje vrijeme i potrošnju memorije.
• Budući da imamo ogromne podatke, možemo izraditi indeksne tablice na više razina.
• Višerazinski indeks može se dizajnirati korištenjem B stabla za keeping podaci sortirani na način samobalansiranja.

Traži OperaANJE

Operacija pretraživanja je najjednostavnija operacija na B stablu. Primjenjuje se sljedeći algoritam:

• Neka je ključ (vrijednost) koja se traži „k“.
• Započnite pretraživanje od korijena i rekurzivno idite prema dolje.
• Ako je k manji od korijenske vrijednosti, pretražuje se lijevo podstablo; ako je k veći od korijenske vrijednosti, pretražuje se 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 samobalansirajuće stablo, 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.

U gornjem primjeru:

• Potražite odgovarajuću poziciju u čvoru za ključ.
• Umetnite ključ u ciljni čvor i provjerite pravila.
• Nakon umetanja, ima li čvor veći ili jednak minimalnom broju 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, nema. To znači da B stablo ne krši nikakva pravila i da je umetanje dovršeno.

U gornjem primjeru:

• Čvor je dosegao maksimalan 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 lijevom ili desnom pristranošću.

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 tome, 13 i 2 mogu se lako umetnuti u čvor jer 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.
• Primjenjuju se tri uvjeta 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 krajnjem čvoru, više od min ključeva. Brisanje ovoga neće narušiti svojstvo B stabla.
• Target nalazi se u krajnjem čvoru i ima min ključnih čvorova. Brisanjem ovoga narušit će se svojstvo B stabla.
• Ciljni čvor može posuditi ključ od neposrednog lijevog čvora ili neposrednog desnog čvora (brata/sestre).
• Brat će reći Da ako ima više od minimalnog broja ključeva.
• Ključ će biti posuđen od roditeljskog čvora, maksimalna vrijednost će biti prenesena roditelju, maksimalna vrijednost roditeljskog čvora će biti prenesena ciljnom čvoru, a ciljna vrijednost će biti uklonjena.
• Target je u listovnom čvoru, ali nijedan braća i sestre nemaju više od minimalnog broja ključeva: traži se ključ, spaja se s braćom i sestrama i minimalnim brojem roditeljskih čvorova, ukupan broj ključeva sada će biti veći od min, a ciljni ključ će biti zamijenjen minimalnim brojem roditeljskog čvora.

Ako je ciljni ključ u unutarnjem čvoru

• Odaberite ili prethodnika po redoslijedu ili nasljednika po redoslijedu.
• U slučaju prethodnika u redoslijedu, bit će odabran maksimalni ključ iz njegovog lijevog podstabla.
• U slučaju nasljednika po redoslijedu, bit će odabran minimalni ključ iz njegovog desnog podstabla.
• Ako prethodnik ciljnog ključa u redoslijedu ima više od minimalnog broja ključeva, tek tada može zamijeniti ciljni ključ s maksimalnim brojem prethodnika u redoslijedu.
• Ako prethodnik ciljnog ključa po redoslijedu nema više od min ključeva, potražite minimalni ključ nasljednika po redoslijedu.
• 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 s maksimalnim elementom podstabla prethodnog reda.
• Ako nakon brisanja ciljni čvor ima manje od min ključeva, tada će ciljni čvor posuditi maksimalnu vrijednost od svog brata/sestre putem roditelja brata/sestre.
• Cilj će uzeti maksimalnu vrijednost roditelja, ali s čvorovima maksimalne vrijednosti brata/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 minimalni broj podređenih čvorova koje bilo koji čvor može imati 3, a maksimalni broj podređenih čvorova koje bilo koji čvor može imati 5. Dok su minimalni i maksimalni broj ključeva koje bilo koji čvor može 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 minimalnom broju ključeva, tako da ga ne možemo izravno izbrisati jer bi to prekršilo uvjete.

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

• Ciljni čvor će posuditi ključ od neposrednog brata/sestre, u ovom slučaju, prethodnika po redoslijedu (lijevog brata/sestre), jer nema nasljednika po redoslijedu (desnog brata/sestre).
• Maksimalna vrijednost prethodnika u redoslijedu bit će prenesena roditelju, a roditelj će prenijeti maksimalnu vrijednost ciljnom čvoru (vidi dijagram ispod).

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

• Ciljni čvor će posuditi ključ od neposrednog brata/sestre, u ovom slučaju, nasljednika po redoslijedu (desnog brata/sestre), jer njegov prethodnik po redoslijedu (lijevog brata/sestre) ima ključeve jednake minimalnom broju ključeva.
• 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/sestru koji može dati svoj ključ ciljnom čvoru. Stoga je potrebno spajanje. Pogledajte postupak brisanja takvog ključa:

• Spoji ciljni čvor s bilo kojim od njegovih neposrednih braće i sestara zajedno s roditeljskim ključem.
• Odabire se ključ iz roditeljskog čvora koji se nalazi između dva čvora koji se spajaju.
• Izbrišite ciljni ključ iz spojenog čvora.

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

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

Pitanja i odgovori