U sljedećem vodiču naučit ćemo o strukturi podataka B Tree i razmotriti njezinu vizualizaciju.

Dakle, počnimo.

Što je B stablo?

The B Drvo je posebna vrsta stabla višesmjernog pretraživanja , općenito poznat kao M-put drvo, koje se samo uravnotežuje. Zbog svoje uravnotežene strukture, ova se stabla obično koriste za rad i upravljanje ogromnim bazama podataka i pojednostavljenje pretraživanja. U B stablu svaki čvor može imati najviše n podređenih čvorova. B stablo je primjer višerazinskog indeksiranja u sustavu upravljanja bazom podataka (DBMS). I list i unutarnji čvorovi imat će reference zapisa. Stablo B poznato je kao uravnoteženo pohranjeno stablo jer su svi čvorovi lista na istoj razini.

Sljedeći dijagram je primjer B stabla:

Slika 1. A B Stablo s redoslijedom 3

Razumijevanje pravila stabla B

Sljedeća su važna svojstva B stabla:

123 film

1. Svi čvorovi lista su na istoj razini.
2. Struktura podataka B stabla definirana je pojmom minimalnog stupnja 'd'. Vrijednost 'd' ovisi o veličini bloka diska.
3. Svaki čvor, isključujući korijen, mora se sastojati od najmanje d-1 ključeva. Korijenski čvor može se sastojati od najmanje 1 ključa.
4. Svi čvorovi (uključujući korijenski čvor) mogu se sastojati od najviše (2d-1) tipke.
5. Broj djece čvora jednak je dodavanje broja ključeva prisutnih u njemu i .
6. Svi ključevi čvora poredani su uzlaznim redoslijedom. Dijete između dva ključa, k1 i k2, sastoji se od svih ključeva koji se nalaze između k1 i k2.
7. Za razliku od stabla binarnog pretraživanja, struktura podataka stabla B raste i smanjuje se od korijena. Dok binarno stablo pretraživanja raste prema dolje i smanjuje se prema dolje.
8. Slično drugim stablima samouravnoteženog binarnog pretraživanja, vremenska složenost strukture podataka stabla B za operacije poput pretraživanja, umetanja i brisanja je O(log?n) .
9. Umetanje čvora u stablo B događa se samo u čvoru lista.

Razmotrimo sljedeći primjer B stabla minimalnog reda 5.

Slika 2. A B Stablo reda 5

Napomena: vrijednost minimalne narudžbe je mnogo veća od 5 u praktičnim B stablima.

U gornjem dijagramu možemo uočiti da su svi lisnati čvorovi na istoj razini, a svi nelisni čvorovi nemaju prazno podstablo i sastoje se od ključeva za jedan manje od broja njihovih potomaka.

Postavljena formulacija pravila B stabla:

Svako B stablo ovisi o pozitivnom konstantnom cijelom broju poznatom kao MINIMUM , koji se koristi za određivanje broja podatkovnih elemenata koji se mogu držati u jednom čvoru.

Pravilo 1: Korijen može imati samo jedan podatkovni element (ili čak niti jedan podatkovni element ako također nema djece); svaki drugi čvor ima najmanje MINIMUM elementi podataka.

Pravilo 2: Maksimalni broj podatkovnih elemenata pohranjenih u čvoru dvostruka je vrijednost MINIMUM .

Pravilo 3: Podatkovni elementi svakog čvora B stabla pohranjeni su u djelomično ispunjenom nizu, sortirani od najmanjeg podatkovnog elementa (na indeksu 0 ) do najvećeg podatkovnog elementa (na konačnoj korištenoj poziciji niza).

Pravilo 4: Ukupan broj podstabala ispod čvora koji nije list uvijek je za jedan veći od broja podatkovnih elemenata u tom čvoru.

• podstablo 0, podstablo 1,...

Pravilo 5: S obzirom na bilo koji čvor koji nije list:

1. Element podataka u indeksu veći je od svih elemenata podataka u broju podstabla i čvora, i
2. Element podataka na indeksu manji je od svih elemenata podataka u broju podstabla i+1 čvora.

Pravilo 6: Svaki list u stablu B ima istu dubinu. Stoga osigurava da stablo B sprječava problem neuravnoteženog stabla.

Operacije na podatkovnoj strukturi B stabla

Kako bi se osiguralo da nijedno od svojstava podatkovne strukture B stabla nije narušeno tijekom operacija, B stablo se može podijeliti ili spojiti. Slijede neke operacije koje možemo izvesti na B stablu:

1. Pretraživanje podatkovnog elementa u B stablu
2. Umetanje podatkovnog elementa u B stablo
3. Brisanje podatkovnog elementa u B stablu

Operacija pretraživanja na stablu B

Pretraživanje elementa u stablu B slično je onom u stablu binarnog pretraživanja. Ali umjesto donošenja dvosmjerne odluke (lijevo ili desno) poput binarnog stabla pretraživanja, B stablo donosi m-smjernu odluku na svakom čvoru gdje je m broj djece čvora.

Koraci za pretraživanje podatkovnog elementa u B stablu:

Korak 1: Pretraga počinje od korijenskog čvora. Usporedite traženi element, k, s korijenom.

Korak 1.1: Ako se korijenski čvor sastoji od elementa k, pretraga će biti završena.

Korak 1.2: Ako je element k manji od prve vrijednosti u korijenu, pomaknut ćemo se na krajnje lijevo dijete i pretražiti dijete rekurzivno.

Korak 1.3.1: Ako korijen ima samo dva djeteta, pomaknut ćemo se na krajnje desno dijete i rekurzivno pretražiti dijete čvorove.

Korak 1.3.2: Ako root ima više od dva ključa, pretražit ćemo ostatak.

Korak 2: Ako element k nije pronađen nakon obilaska cijelog stabla, tada traženi element nije prisutan u B stablu.

Predstavimo gore navedene korake uz pomoć primjera. Pretpostavimo da želimo tražiti ključ k=34 u sljedećem B stablu:

Slika 3.1. Zadano B stablo

1. Prvo ćemo provjeriti je li ključ k = 34 je u korijenskom čvoru. Budući da ključ nije u korijenu, prijeći ćemo na njegove podređene čvorove. Također možemo uočiti da korijenski čvor ima dvoje djece; stoga ćemo usporediti traženu vrijednost između dva ključa.
   
   Slika 3.2. Ključ k nije prisutan u korijenu
2. Sada kada možemo primijetiti da je ključ k veći od korijenskog čvora, tj. 30, nastavit ćemo s desnim djetetom korijena.
   
   Slika 3.3. Tipka k > 30, pomaknite se na desno dijete
3. Sada ćemo usporediti ključ k s vrijednostima prisutnim na čvoru, tj. 40 odnosno 50. Budući da je ključ k manji od lijevog ključa, tj. 40, pomaknut ćemo se na lijevo dijete čvora.
   
   Slika 3.4. Ključ k<40, move to left child< li>
4. Budući da je vrijednost u lijevom djetetu od 40 34, što je tražena vrijednost, možemo zaključiti da je ključ pronađen i da je operacija pretraživanja završena.
   
   Slika 3.4. Ključ k = 34, lijevi potomak od 40

Uspoređivali smo ključ s četiri različite vrijednosti u gornjem primjeru dok ga nismo pronašli. Dakle, vremenska složenost potrebna za operaciju pretraživanja u B stablu je O(log?n) .

Umetanje operacije na B stablo

Prilikom umetanja podatkovnog elementa u B stablo, prvo moramo provjeriti je li taj element već prisutan u stablu ili ne. Ako se podatkovni element pronađe unutar stabla B, tada se operacija umetanja ne događa. Međutim, ako to nije slučaj, mi ćemo nastaviti s umetanjem. Postoje dva scenarija o kojima je potrebno voditi računa prilikom umetanja elementa u lisni čvor:

Čvor se ne sastoji od više od MAKSIMALNOG broja ključeva -Umetnut ćemo ključ u čvor na njegovo pravo mjesto.Čvor se sastoji od MAKSIMALNOG broja ključeva -Umetnut ćemo ključ u puni čvor, a zatim će se izvršiti operacija dijeljenja, koja će cijeli čvor podijeliti na tri dijela. Drugi ili srednji ključ premjestit će se na nadređeni čvor, a prvi i treći dio će djelovati kao lijevi odnosno desni podređeni čvor. Ovaj proces će se ponoviti s nadređenim čvorom ako se također sastoji od MAKSIMALNOG broja ključeva.

Koraci za umetanje podatkovnog elementa u B stablo:

sql klauzule

Korak 1: Počet ćemo izračunavanjem maksimalnog broja ključeva u čvoru na temelju redoslijeda stabla B.

Korak 2: Ako je stablo prazno, dodjeljuje se korijenski čvor, a mi ćemo umetnuti ključ koji djeluje kao korijenski čvor.

Korak 3: Sada ćemo pretražiti odgovarajući čvor za umetanje.

Korak 4: Ako je čvor pun:

Korak 4.1: Elemente podataka umetnut ćemo uzlaznim redoslijedom.

Korak 4.2: Ako su elementi podataka veći od maksimalnog broja ključeva, podijelit ćemo puni čvor na medijanu.

Korak 4.3: Gurnut ćemo srednji ključ prema gore i podijeliti lijevu i desnu tipku kao lijevo i desno dijete.

Korak 5: Ako čvor nije pun, umetnut ćemo čvor uzlaznim redoslijedom.

Predstavimo gore navedene korake uz pomoć primjera. Pretpostavimo da se od nas traži da stvorimo B stablo reda 4. Elementi podataka koje treba umetnuti u B stablo su 5,3,21,11,1,16,8,13,4 i 9 .

1. Budući da je m jednako 3, najveći broj ključeva za čvor = m-1 = 3-1 = 2 .
2. Počet ćemo s umetanjem 5 u praznom stablu.
   
   Slika 4.1. Umetanje 5
3. Sada ćemo u stablo umetnuti 3. Budući da je 3 manje od 5, umetnut ćemo 3 lijevo od 5 u istom čvoru.
   
   Slika 4.2. Umetanje 3
4. Sada ćemo u stablo umetnuti 21, a budući da je 21 veće od 5, bit će umetnuto desno od 5 u istom čvoru. Međutim, kako znamo da je najveći broj ključeva u čvoru 2, jedan od tih ključeva bit će premješten u čvor iznad kako bi se podijelio. Tako će se 5, srednji podatkovni element, pomaknuti prema gore, a 3 i 21 postat će njegov lijevi odnosno desni čvor.
   
   Slika 4.3. Umetanje 21
5. Sada je vrijeme za umetanje sljedećeg podatkovnog elementa, tj. 11, koji je veći od 5, ali manji od 21. Stoga će 11 biti umetnut kao ključ s lijeve strane čvora koji se sastoji od 21 kao ključa.
   
   Slika 4.4. Umetanje 11
6. Slično, u stablo ćemo umetnuti sljedeći podatkovni element 1, a kao što možemo primijetiti, 1 je manji od 3; stoga će biti umetnut kao ključ s lijeve strane čvora koji se sastoji od 3 kao ključ.
   
   Slika 4.5. Umetanje 1
7. Sada ćemo u stablo umetnuti podatkovni element 16, koji je veći od 11, ali manji od 21. Međutim, broj ključeva u tom čvoru premašuje maksimalni broj ključeva. Stoga će se čvor podijeliti, pomicanjem srednjeg ključa u korijen. Stoga će 16 biti umetnuto desno od 5, dijeleći 11 i 21 u dva odvojena čvora.
   
   Slika 4.6. Umetanje 16
8. Element podataka 8 bit će umetnut kao ključ lijevo od 11.
   
   Slika 4.7. Umetanje 8
9. U stablo ćemo umetnuti 13, što je manje od 16 i veće od 11. Stoga, podatkovni element 13 treba umetnuti desno od čvora koji se sastoji od 8 i 11. Međutim, budući da maksimalan broj ključeva u stablu može bude samo 2, dogodit će se razdvajanje, pomicanje srednjeg podatkovnog elementa 11 u gornji čvor, a 8 i 13 u dva odvojena čvora. Sada će se gornji čvor sastojati od 5, 11 i 16, što opet premašuje maksimalni broj ključeva. Stoga će doći do još jednog razdvajanja, čineći podatkovni element 11 korijenskim čvorom s 5 i 16 kao svojom djecom.
   
   Slika 4.8. Umetanje 13
10. Budući da je podatkovni element 4 manji od 5, ali veći od 3, bit će umetnut s desne strane čvora koji se sastoji od 1 i 3, što će ponovno premašiti maksimalni broj ključeva u čvoru. Stoga će ponovno doći do izlijevanja, pomičući 3 u gornji čvor pored 5.
    
    Slika 4.9. Umetanje 4
11. Na kraju, podatkovni element 9, koji je veći od 8, ali manji od 11, bit će umetnut desno od čvora koji se sastoji od 8 kao ključ.
    
    Slika 4.10. Umetanje 9

U gornjem primjeru izvršili smo različite usporedbe. Prva vrijednost je izravno umetnuta u stablo; nakon toga se svaka vrijednost morala usporediti s čvorovima dostupnim u tom stablu. Vremenska složenost za operaciju umetanja u B stablo ovisi o broju čvorova i .

Brisanje operacije na stablu B

Brisanje podatkovnog elementa na B stablu sadrži tri primarna događaja:

1. Pretraživanje čvora u kojem postoji ključ za brisanje,
2. Brisanje ključa i

• Balansiranje stabla, ako je potrebno.

Prilikom brisanja elementa iz stabla može se pojaviti stanje poznato kao Underflow. Underflow se događa kada se čvor sastoji od manje od minimalnog broja ključeva; trebalo bi držati.

Slijede neki pojmovi koje je potrebno razumjeti prije vizualizacije operacije brisanja/uklanjanja:

Prethodnik po redu:Najznačajniji ključ na lijevom podređenom čvoru poznat je kao njegov redoslijed prethodnik.Nasljednik po redu:Sporedni ključ na desnom podređenom čvoru poznat je kao njegov nasljednik po redu.

Slijede tri istaknuta slučaja operacije brisanja u B stablu:

Slučaj 1: Brisanje/uklanjanje ključa nalazi se u čvoru lista - Ovaj slučaj je dalje podijeljen u dva različita slučaja:

1. Brisanje/uklanjanje ključa ne narušava svojstvo minimalnog broja ključeva koje bi čvor trebao držati.

Vizualizirajmo ovaj slučaj pomoću primjera u kojem ćemo izbrisati ključ 32 iz sljedećeg stabla B.

Slika 4.1: Brisanje ključa lisnog čvora (32) iz B stabla

zasebni niz u Javi

Kao što možemo primijetiti, brisanje 32 iz ovog stabla ne krši gornje svojstvo.

2. Brisanje/uklanjanje ključa krši svojstvo minimalnog broja ključeva koje bi čvor trebao držati. U ovom slučaju, moramo posuditi ključ od njegovog najbližeg srodnog čvora redoslijedom slijeva nadesno.

Prvo ćemo posjetiti najbližeg lijevog brata ili sestru. Ako Lijevi bratski čvor ima više od minimalnog broja ključeva, on će posuditi ključ od ovog čvora.

Inače, provjerit ćemo posuditi od najbližeg desnog bratskog čvora.

Predstavimo sada ovaj slučaj uz pomoć primjera gdje ćemo izbrisati 31 iz gornjeg B stabla. U ovom slučaju ćemo posuditi ključ od lijevog srodnog čvora.

Slika 4.2: Brisanje ključa lisnog čvora (31) iz B stabla

Ako se oba proksimativna srodna čvora već sastoje od minimalnog broja ključeva, tada ćemo spojiti čvor ili s lijevim srodnim čvorom ili s desnim. Ovaj proces spajanja se vrši preko nadređenog čvora.

Ponovno vizualizirajmo brisanjem ključa 30 iz gornjeg stabla B.

Slika 4.3: Brisanje ključa lisnog čvora (30) iz B stabla

Slučaj 2: Brisanje/uklanjanje ključa nalazi se u čvoru koji nije list - Ovaj slučaj je dalje podijeljen na različite slučajeve:

1. Čvor koji nije list/unutarnji, a koji je uklonjen, zamjenjuje se prethodnikom po redu ako lijevi čvor dijete ima više od minimalnog broja ključeva.

Vizualizirajmo ovaj slučaj na primjeru gdje ćemo izbrisati ključ 33 iz B stabla.

Slika 4.4: Brisanje ključa lisnog čvora (33) iz B stabla

2. Čvor koji nije list/unutarnji, a koji je uklonjen, zamjenjuje se nasljednikom po redu ako desni čvor dijete ima više od minimalnog broja ključeva.

Ako bilo koje dijete ima minimalni broj ključeva, tada ćemo spojiti lijevi i desni čvor djeteta.

Vizualizirajmo ovaj slučaj brisanjem ključa 30 iz stabla B.

Slika 4.5: Brisanje ključa lisnog čvora (30) iz B stabla

Nakon spajanja, ako nadređeni čvor ima manji od minimalnog broja ključeva, može se potražiti braća i sestre, kao u Slučaj 1 .

Slučaj 3: U sljedećem slučaju visina stabla se smanjuje. Ako se ciljni ključ nalazi u internom čvoru, a uklanjanje ključa dovodi do manjeg broja ključeva u čvoru (što je manje od potrebnog minimuma), tada potražite redoslijed prethodnika i redoslijed nasljednika. Ako oba djeteta imaju minimalni broj ključeva, tada do posuđivanja ne može doći. Ovo vodi do Slučaj 2(3) , tj. spajanje podređenih čvorova.

Ponovno ćemo potražiti brata ili sestru da posudimo ključ. Međutim, ako se srodni čvor također sastoji od minimalnog broja ključeva, tada ćemo spojiti čvor sa srodnim čvorom zajedno s nadređenim čvorom i rasporediti podređene čvorove prema zahtjevima (uzlazni redoslijed).

Vizualizirajmo ovaj slučaj uz pomoć primjera gdje ćemo izbrisati podatkovni element 10 iz zadanog B stabla.

Slika 4.6: Brisanje ključa lisnog čvora (10) iz B stabla

Vremenska složenost u gornjim primjerima varira ovisno o mjestu s kojeg ključ treba izbrisati. Dakle, vremenska složenost za operaciju brisanja u B stablu je O(log?n) .

Zaključak

U ovom vodiču naučili smo o stablu B i vizualizirali njegove različite operacije na različitim primjerima. Također smo razumjeli neka temeljna svojstva i pravila B stabla.