În următorul tutorial, vom afla despre structura de date B Tree și vom lua în considerare vizualizarea acesteia.
Asadar, haideti sa începem.
Ce este un arbore B?
The B Arborele este o tip special de arbore de căutare cu mai multe căi , cunoscut sub numele de M-way copac, care se echilibrează. Datorită structurii lor echilibrate, acești arbori sunt utilizați în mod obișnuit pentru a opera și gestiona baze de date imense și pentru a simplifica căutările. Într-un arbore B, fiecare nod poate avea cel mult n noduri copil. B Tree este un exemplu de indexare pe mai multe niveluri într-un sistem de management al bazelor de date (DBMS). Nodurile Leaf și Internal vor avea ambele referințe de înregistrare. Arborele B este cunoscut sub numele de Arborele stocat echilibrat deoarece toate nodurile frunzelor sunt la același nivel.
Următoarea diagramă este un exemplu de arbore B:
Figura 1. A B Arborele cu ordinea 3
Înțelegerea regulilor arborelui B
Următoarele sunt proprietățile importante ale unui arbore B:
- Toate nodurile frunzelor sunt la același nivel.
- Structura de date B Tree este definită de termenul de grad minim „d”. Valoarea lui „d” depinde de dimensiunea blocului de disc.
- Fiecare nod, cu excepția rădăcinii, trebuie să fie format din cel puțin d-1 chei. Nodul rădăcină poate consta dintr-un minim de o cheie.
- Toate nodurile (inclusiv nodul rădăcină) pot consta în cel mult (2d-1) chei.
- Numărul de copii ai unui nod este egal cu adăugarea numărului de chei prezente în acesta și .
- Toate cheile unui nod sunt sortate în ordine crescătoare. Copilul dintre două chei, k1 și k2, este format din toate cheile cuprinse între k1 și, respectiv, k2.
- Spre deosebire de arborele de căutare binar, structura de date a arborelui B crește și se micșorează de la rădăcină. În timp ce Arborele de căutare binar crește în jos și se micșorează în jos.
- Similar altor arbori de căutare binari auto-echilibrați, complexitatea timpului a structurii de date a arborelui B pentru operațiuni precum căutarea, inserarea și ștergerea este O(log?n) .
- Inserarea unui Nod în Arborele B are loc numai la Nodul Frunză.
Să luăm în considerare următorul exemplu de arbore B de ordin minim 5.
Figura 2. A B Arborele ordinului 5
Notă: Valoarea comenzii minime este mult mai mare de 5 într-un practic B Trees.
În diagrama de mai sus, putem observa că toate nodurile frunză sunt la același nivel și toate nodurile care nu sunt frunze nu au un subarboresc gol și constau din chei cu una mai puțin decât numărul copiilor lor.
Formularea setată a regulilor arborelui B:
Fiecare Arbore B depinde de un număr întreg constant pozitiv cunoscut ca MINIM , care este utilizat pentru a determina numărul de elemente de date care pot fi păstrate într-un singur nod.
Regula 1: Rădăcina poate avea doar un singur element de date (sau chiar niciun element de date dacă nu este și copii); orice alt nod are cel puțin MINIM elemente de date.
tutorial java
Regula 2: Numărul maxim de elemente de date stocate într-un nod este de două ori mai mare decât valoarea lui MINIM .
Regula 3: Elementele de date ale fiecărui nod al Arborelui B sunt stocate într-o matrice parțial umplută, sortată din cel mai mic element de date (la index 0 ) la cel mai mare element de date (la poziția finală utilizată a matricei).
Regula 4: Numărul total de subarbori de sub un nod fără frunză este întotdeauna cu unul mai mult decât numărul de elemente de date din acel nod.
- subarborele 0, subarborele 1,...
Regula 5: În ceea ce privește orice nod fără frunză:
- Un element de date la index este mai mare decât toate elementele de date din numărul subarboresc i a nodului, și
- Un element de date la index este mai mic decât toate elementele de date din numărul subarboresc i+1 a nodului.
Regula 6: Fiecare frunză dintr-un arbore B are aceeași adâncime. Astfel, se asigură că un arbore B previne problema unui arbore dezechilibrat.
Operații pe o structură de date B Tree
Pentru a ne asigura că niciuna dintre proprietățile unei structuri de date B Tree nu este încălcată în timpul operațiunilor, Arborele B poate fi împărțit sau alăturat. Următoarele sunt câteva operații pe care le putem efectua pe un arbore B:
- Căutarea unui element de date în B Tree
- Inserarea unui element de date în arborele B
- Ștergerea unui element de date din arborele B
Operațiune de căutare pe un arbore B
Căutarea unui element într-un arbore B este similară cu cea dintr-un arbore de căutare binar. Dar, în loc să ia o decizie în două sensuri (Stânga sau Dreapta) ca un Arbore de căutare binar, un Arbore B ia o decizie în două sensuri la fiecare nod, unde m este numărul de copii ai nodului.
Pași pentru a căuta un element de date într-un arbore B:
Pasul 1: Căutarea începe de la nodul rădăcină. Comparați elementul de căutare, k, cu rădăcina.
Pasul 1.1: Dacă nodul rădăcină este format din elementul k, căutarea va fi completă.
Pasul 1.2: Dacă elementul k este mai mic decât prima valoare din rădăcină, vom trece la copilul din stânga și vom căuta copilul recursiv.
Pasul 1.3.1: Dacă rădăcina are doar doi copii, vom trece la copilul din dreapta și vom căuta recursiv nodurile copil.
Pasul 1.3.2: Dacă rădăcina are mai mult de două chei, vom căuta restul.
matrice de șiruri în programarea c
Pasul 2: Dacă elementul k nu este găsit după parcurgerea întregului arbore, atunci elementul de căutare nu este prezent în arborele B.
Să vizualizăm pașii de mai sus cu ajutorul unui exemplu. Să presupunem că dorim să căutăm o cheie k=34 în următorul arbore B:
Figura 3.1. Un arbore B dat
- În primul rând, vom verifica dacă cheia k = 34 este la nodul rădăcină. Deoarece cheia nu se află la rădăcină, vom trece la nodurile sale copil. De asemenea, putem observa că nodul rădăcină are doi copii; prin urmare, vom compara valoarea cerută între cele două chei.
Figura 3.2. Cheia k nu este prezentă la rădăcină - Acum că putem observa că cheia k este mai mare decât nodul rădăcină, adică 30, vom continua cu copilul drept al rădăcinii.
Figura 3.3. Tasta k > 30, mutați la copilul drept - Vom compara acum cheia k cu valorile prezente pe nod, adică 40 și, respectiv, 50. Deoarece cheia k este mai mică decât tasta din stânga, adică 40, ne vom deplasa la copilul din stânga al nodului.
Figura 3.4. Cheia k<40, move to left child< li> - Deoarece valoarea din copilul din stânga 40 este 34, care este valoarea necesară, putem concluziona că cheia este găsită și operația de căutare este finalizată.
Figura 3.4. Cheia k = 34, copilul stâng de 40
Am comparat cheia cu patru valori diferite în exemplul de mai sus până am găsit-o. Astfel, complexitatea de timp necesară pentru operația de căutare într-un arbore B este O(log?n) .
Operația de inserare pe un arbore B
În timp ce inserăm un element de date într-un arbore B, trebuie mai întâi să verificăm dacă acel element este deja prezent în arbore sau nu. Dacă elementul de date este găsit în Arborele B, atunci operația de inserare nu are loc. Totuși, dacă nu este cazul, vom continua cu inserarea. Există două scenarii care trebuie avute în vedere la inserarea unui element în nodul frunză:
Pași pentru a insera un element de date într-un arbore B:
Pasul 1: Vom începe prin a calcula numărul maxim de chei din nod pe baza ordinii Arborelui B.
Pasul 2: Dacă arborele este gol, este alocat un nod rădăcină și vom introduce cheia care acționează ca nod rădăcină.
Pasul 3: Vom căuta acum nodul aplicabil pentru inserare.
Pasul 4: Dacă nodul este plin:
Pasul 4.1: Vom introduce elementele de date în ordine crescătoare.
Pasul 4.2: Dacă elementele de date sunt mai mari decât numărul maxim de chei, vom împărți întregul nod la mediană.
excepție de aruncare java
Pasul 4.3: Vom împinge tasta mediană în sus și vom împărți tastele stânga și dreapta ca copil stâng și drept.
Pasul 5: Dacă nodul nu este plin, vom introduce nodul în ordine crescătoare.
Să vizualizăm pașii de mai sus cu ajutorul unui exemplu. Să presupunem că ni se cere să creăm un arbore B de ordinul 4. Elementele de date necesare pentru a fi inserate în arborele B sunt 5,3,21,11,1,16,8,13,4 și 9 .
- Deoarece m este egal cu 3, numărul maxim de chei pentru un nod = m-1 = 3-1 = 2 .
- Vom începe prin a introduce 5 în copacul gol.
Figura 4.1. Inserarea 5 - Vom introduce acum 3 în arbore. Deoarece 3 este mai mic decât 5, vom insera 3 la stânga lui 5 în același nod.
Figura 4.2. Inserarea 3 - Vom insera acum 21 în arbore și, deoarece 21 este mai mare decât 5, va fi inserat la dreapta lui 5 în același nod. Cu toate acestea, deoarece știm că numărul maxim de chei din nod este 2, una dintre aceste chei va fi mutată într-un nod de mai sus pentru a o împărți. Astfel, 5, elementul de date din mijloc, se va deplasa în sus, iar 3 și 21 vor deveni nodurile sale stânga și respectiv dreapta.
Figura 4.3. Se introduce 21 - Acum este timpul să introduceți următorul element de date, adică 11, care este mai mare de 5, dar mai mic de 21. Prin urmare, 11 va fi inserat ca o cheie în stânga nodului format din 21 ca o cheie.
Figura 4.4. Inserarea 11 - În mod similar, vom introduce următorul element de date 1 în arbore și, după cum putem observa, 1 este mai mic decât 3; prin urmare, va fi inserat ca cheie în stânga nodului format din 3 ca cheie.
Figura 4.5. Inserarea 1 - Acum, vom introduce elementul de date 16 în arbore, care este mai mare decât 11, dar mai mic de 21. Cu toate acestea, numărul de chei din acel nod depășește numărul maxim de chei. Prin urmare, nodul se va împărți, mutând cheia din mijloc la rădăcină. Prin urmare, 16 va fi inserat la dreapta celor 5, împărțind 11 și 21 în două noduri separate.
Figura 4.6. Introducerea 16 - Elementul de date 8 va fi inserat ca o cheie la stânga lui 11.
Figura 4.7. Inserarea 8 - Vom insera 13 în arbore, care este mai mic decât 16 și mai mare decât 11. Prin urmare, elementul de date 13 ar trebui inserat în dreapta nodului format din 8 și 11. Cu toate acestea, deoarece numărul maxim de chei din arbore poate fie doar 2, va avea loc o scindare, mutand elementul de date din mijloc 11 la nodul de mai sus și 8 și 13 în două noduri separate. Acum, nodul de mai sus va consta din 5, 11 și 16, ceea ce depășește din nou numărul maxim de chei. Prin urmare, va exista o altă divizare, făcând din elementul de date 11 nodul rădăcină cu 5 și 16 drept copii.
Figura 4.8. Introducerea 13 - Deoarece elementul de date 4 este mai mic de 5 dar mai mare de 3, acesta va fi inserat în dreapta nodului format din 1 și 3, care va depăși din nou numărul maxim de chei dintr-un nod. Prin urmare, va apărea din nou o scurgere, mutând 3 în nodul superior de lângă 5.
Figura 4.9. Inserarea 4 - În cele din urmă, elementul de date 9, care este mai mare decât 8 dar mai mic de 11, va fi inserat în dreapta nodului format din 8 ca cheie.
Figura 4.10. Inserarea 9
În exemplul de mai sus, am efectuat diferite comparații. Prima valoare a fost introdusă direct în arbore; după aceea, fiecare valoare trebuia comparată cu nodurile disponibile în acel arbore. Complexitatea timpului pentru operația de inserare într-un arbore B depinde de numărul de noduri și .
Operația de ștergere pe un arbore B
Ștergerea unui element de date dintr-un arbore B conține trei evenimente principale:
- Căutând nodul unde există cheia de șters,
- Ștergerea cheii și
- Echilibrarea copacului, dacă este necesar.
În timpul ștergerii unui element din arbore, poate apărea o condiție cunoscută sub numele de Underflow. Underflow apare atunci când un nod este format din mai puțin decât numărul minim de taste; ar trebui să țină.
Următorii sunt câțiva termeni care trebuie înțeleși înainte de a vizualiza operația de ștergere/eliminare:
Următoarele sunt trei cazuri proeminente ale operațiunii de ștergere într-un arbore B:
Cazul 1: Ștergerea/înlăturarea cheii se află în nodul Leaf - Acest caz este împărțit în continuare în două cazuri diferite:
1. Ștergerea/înlăturarea cheii nu încalcă proprietatea numărului minim de chei pe care ar trebui să le dețină un nod.
Să vizualizăm acest caz folosind un exemplu în care vom șterge cheia 32 din următorul arbore B.
Figura 4.1: Ștergerea unei chei de nod frunză (32) din arborele B
După cum putem observa, ștergerea 32 din acest arbore nu încalcă proprietatea de mai sus.
2. Ștergerea/înlăturarea cheii încalcă proprietatea numărului minim de chei pe care ar trebui să le dețină un nod. În acest caz, trebuie să împrumutăm o cheie de la nodul său frate apropiat, în ordinea de la stânga la dreapta.
În primul rând, vom vizita fratele din stânga apropiat. Dacă nodul frate stânga are mai mult de un număr minim de chei, va împrumuta o cheie de la acest nod.
În caz contrar, vom verifica să împrumutăm de la nodul de frate Dreapta apropiat.
Să vizualizăm acum acest caz cu ajutorul unui exemplu în care vom șterge 31 din arborele B de mai sus. În acest caz, vom împrumuta o cheie de la nodul fratelui din stânga.
Figura 4.2: Ștergerea unei chei de nod frunză (31) din arborele B
Dacă ambele noduri de frați proximi constau deja dintr-un număr minim de chei, atunci vom îmbina nodul fie cu nodul frate stâng, fie cu cel din dreapta. Acest proces de îmbinare se face prin nodul părinte.
forma completă ssh
Să vizualizăm din nou ștergând cheia 30 din arborele B de mai sus.
Figura 4.3: Ștergerea unei chei de nod frunză (30) din arborele B
Cazul 2: Ștergerea/Ștergerea cheii se află în nodul non-Leaf - Acest caz este împărțit în continuare în diferite cazuri:
1. Nodul non-Leaf/Intern, care este eliminat, este înlocuit cu un predecesor în ordine dacă nodul copil din stânga are mai mult decât numărul minim de chei.
Să vizualizăm acest caz folosind un exemplu în care vom șterge cheia 33 din arborele B.
Figura 4.4: Ștergerea unei chei de nod frunză (33) din arborele B
2. Nodul non-Frunză/Intern, care este eliminat, este înlocuit cu un succesor în ordine dacă nodul secundar dreapta are mai mult decât numărul minim de chei.
Dacă oricare dintre copii are un număr minim de chei, atunci vom îmbina nodurile copil stânga și dreapta.
Să vizualizăm acest caz ștergând cheia 30 din arborele B.
Figura 4.5: Ștergerea unei chei de nod frunză (30) din arborele B
După îmbinare, dacă nodul părinte are mai puțin decât numărul minim de chei, se pot căuta frații, ca în Cazul 1 .
Cazul 3: În cazul următor, înălțimea copacului se micșorează. Dacă cheia țintă se află într-un nod intern, iar eliminarea cheii duce la mai puține chei în nod (care este mai mică decât minimul necesar), atunci căutați predecesorul în ordine și succesorul în ordine. Dacă ambii copii au un număr minim de chei, atunci împrumutul nu poate avea loc. Asta duce la Cazul 2(3) , adică îmbinarea nodurilor copil.
Vom căuta din nou fratele pentru a împrumuta o cheie. Cu toate acestea, dacă fratele constă și dintr-un număr minim de chei, atunci vom îmbina nodul cu fratele împreună cu nodul părinte și vom aranja nodurile copil conform cerințelor (ordine crescătoare).
Să vizualizăm acest caz cu ajutorul unui exemplu în care vom șterge elementul de date 10 din arborele B dat.
Figura 4.6: Ștergerea unei chei de nod frunză (10) din arborele B
Complexitatea timpului din exemplele de mai sus variază în funcție de locația de unde trebuie ștearsă cheia. Astfel, complexitatea timpului pentru operația de ștergere într-un arbore B este O(log?n) .
Concluzia
În acest tutorial, am învățat despre Arborele B și am vizualizat diferitele sale operațiuni cu exemple diferite. De asemenea, am înțeles câteva proprietăți și reguli fundamentale ale Arborelui B.