En el següent tutorial, coneixerem l'estructura de dades de l'arbre B i ens plantegem visualitzar-la.
Així doncs, comencem.
Què és un arbre B?
El B Arbre és un tipus especial d'arbre de cerca múltiple , comunament conegut com el Camí M arbre, que s'equilibra. A causa de la seva estructura equilibrada, aquests arbres s'utilitzen habitualment per operar i gestionar grans bases de dades i simplificar les cerques. En un arbre B, cada node pot tenir com a màxim n nodes fills. B Tree és un exemple d'indexació multinivell en un sistema de gestió de bases de dades (DBMS). Els nodes de fulla i interns tindran referències de registre. L'arbre B es coneix com a arbre emmagatzemat equilibrat perquè tots els nodes de fulla estan al mateix nivell.
El diagrama següent és un exemple d'arbre B:
Figura 1. A B Arbre amb ordre 3
Entendre les regles de l'arbre B
Les següents són les propietats importants d'un arbre B:
- Tots els nodes de la fulla estan al mateix nivell.
- L'estructura de dades de l'arbre B es defineix pel terme grau mínim 'd'. El valor de 'd' depèn de la mida del bloc de disc.
- Cada node, excepte l'arrel, ha de constar almenys d-1 claus. El node arrel pot constar d'un mínim d'1 clau.
- Tots els nodes (inclòs el node arrel) poden consistir com a màxim (2d-1) claus.
- El nombre de fills d'un node és igual al suma del nombre de claus presents en ell i .
- Totes les claus d'un node s'ordenen en ordre ascendent. El nen entre dues claus, k1 i k2, consta de totes les claus que van entre k1 i k2, respectivament.
- A diferència de l'arbre de cerca binari, l'estructura de dades de l'arbre B creix i es redueix des de l'arrel. Mentre que l'arbre de cerca binari creix cap avall i es redueix cap avall.
- De manera similar a altres arbres de cerca binaris autoequilibrats, la complexitat temporal de l'estructura de dades de l'arbre B per a operacions com la cerca, la inserció i la supressió és O(log?n) .
- La inserció d'un node a l'arbre B només es produeix al node de fulla.
Considerem l'exemple següent d'un arbre B d'ordre mínim 5.
Figura 2. A B Arbre d'ordre 5
Nota: El valor de la comanda mínima és molt més que 5 en un pràctic B Trees.
Al diagrama anterior, podem observar que tots els nodes fulla estan al mateix nivell, i tots els nodes que no són fulla no tenen un subarbre buit i consisteixen en claus una menys que el nombre dels seus fills.
La formulació conjunta de les regles de l'arbre B:
Cada arbre B depèn d'un nombre enter constant positiu conegut com MINIM , que s'utilitza per determinar el nombre d'elements de dades que es poden mantenir en un sol node.
Regla 1: L'arrel pot tenir tan sols un element de dades (o fins i tot cap element de dades si tampoc no és fill); tots els altres nodes tenen almenys MINIM elements de dades.
Regla 2: El nombre màxim d'elements de dades emmagatzemats en un node és el doble del valor de MINIM .
Regla 3: Els elements de dades de cada node de l'arbre B s'emmagatzemen en una matriu parcialment plena, ordenada a partir de l'element de dades més petit (a l'índex 0 ) a l'element de dades més gran (a la posició final utilitzada de la matriu).
Regla 4: El nombre total de subarbres per sota d'un node no full és sempre un més que el nombre d'elements de dades en aquest node.
- subarbre 0,subarbre 1,...
Regla 5: Pel que fa a qualsevol node que no sigui full:
- Un element de dades a l'índex és més gran que tots els elements de dades del número de subarbre i del node, i
- Un element de dades a l'índex és menor que tots els elements de dades del número de subarbre i+1 del node.
Regla 6: Cada fulla d'un arbre B té la mateixa profunditat. Així, assegura que un arbre B evita el problema d'un arbre desequilibrat.
int a cadena
Operacions en una estructura de dades d'arbre B
Per tal d'assegurar que cap de les propietats d'una estructura de dades d'un arbre B es violi durant les operacions, l'arbre B es pot dividir o unir. A continuació es mostren algunes operacions que podem realitzar en un arbre B:
- Cerca d'un element de dades a l'arbre B
- Inserció d'un element de dades a l'arbre B
- Supressió d'un element de dades a l'arbre B
Operació de cerca en un arbre B
La cerca d'un element en un arbre B és similar a la d'un arbre de cerca binari. Però en comptes de prendre una decisió bidireccional (esquerra o dreta) com un arbre de cerca binari, un arbre B pren una decisió de dues vies a cada node, on m és el nombre de fills del node.
Passos per cercar un element de dades en un arbre B:
Pas 1: La cerca comença des del node arrel. Compareu l'element de cerca, k, amb l'arrel.
Pas 1.1: Si el node arrel consta de l'element k, la cerca estarà completa.
Pas 1.2: Si l'element k és menor que el primer valor de l'arrel, ens mourem al fill més esquerre i cercarem el fill de forma recursiva.
Pas 1.3.1: Si l'arrel només té dos fills, ens mourem al fill més a la dreta i cercarem recursivament els nodes fills.
Pas 1.3.2: Si l'arrel té més de dues claus, buscarem la resta.
Pas 2: Si l'element k no es troba després de travessar tot l'arbre, aleshores l'element de cerca no està present a l'arbre B.
Visualitzem els passos anteriors amb l'ajuda d'un exemple. Suposem que volíem cercar una clau k=34 al següent arbre B:
Figura 3.1. Un arbre B donat
- En primer lloc, comprovarem si la clau k = 34 es troba al node arrel. Com que la clau no es troba a l'arrel, passarem als seus nodes fills. També podem observar que el node arrel té dos fills; per tant, compararem el valor requerit entre les dues claus.
Figura 3.2. La clau k no està present a l'arrel - Ara que podem notar que la clau k és més gran que el node arrel, és a dir, 30, procedirem amb el fill dret de l'arrel.
Figura 3.3. La tecla k > 30, mou al nen dret - Ara compararem la clau k amb els valors presents al node, és a dir, 40 i 50, respectivament. Com que la tecla k és menor que la tecla esquerra, és a dir, 40, ens mourem al fill esquerre del node.
Figura 3.4. La clau k<40, move to left child< li> - Com que el valor del fill esquerre de 40 és 34, que és el valor requerit, podem concloure que s'ha trobat la clau i s'ha completat l'operació de cerca.
Figura 3.4. La clau k = 34, el fill esquerre de 40
Hem comparat la clau amb quatre valors diferents a l'exemple anterior fins que l'hem trobat. Així, la complexitat temporal necessària per a l'operació de cerca en un arbre B és O(log?n) .
Operació d'inserció en un arbre B
Mentre inserim un element de dades en un arbre B, primer hem de comprovar si aquest element ja està present a l'arbre o no. Si l'element de dades es troba dins de l'arbre B, l'operació d'inserció no es produeix. Tanmateix, si aquest no és el cas, continuarem amb la inserció. Hi ha dos escenaris que cal tenir en compte durant la inserció d'un element al node fulla:
Passos per inserir un element de dades en un arbre B:
Pas 1: Començarem calculant el nombre màxim de claus del node en funció de l'ordre de l'arbre B.
Pas 2: Si l'arbre està buit, s'assigna un node arrel i inserirem la clau que actua com a node arrel.
Pas 3: Ara buscarem el node aplicable per inserir-lo.
Pas 4: Si el node està ple:
Pas 4.1: Inserirem els elements de dades en ordre ascendent.
Pas 4.2: Si els elements de dades són superiors al nombre màxim de claus, dividirem el node complet a la mitjana.
Pas 4.3: Empenjarem la tecla mitjana cap amunt i dividirem les tecles esquerra i dreta com a fill esquerre i dret.
Pas 5: Si el node no està ple, inserirem el node en ordre ascendent.
Visualitzem els passos anteriors amb l'ajuda d'un exemple. Suposem que hem de crear un arbre B d'ordre 4. Els elements de dades que cal inserir a l'arbre B són 5,3,21,11,1,16,8,13,4 i 9 .
- Com que m és igual a 3, el nombre màxim de claus per a un node = m-1 = 3-1 = 2 .
- Començarem inserint 5 a l'arbre buit.
Figura 4.1. Inserció 5 - Ara inserirem 3 a l'arbre. Com que 3 és menor que 5, inserirem 3 a l'esquerra de 5 al mateix node.
Figura 4.2. Inserció 3 - Ara inserirem 21 a l'arbre, i com que 21 és més gran que 5, s'inserirà a la dreta de 5 al mateix node. Tanmateix, com sabem que el nombre màxim de claus al node és 2, una d'aquestes claus es mourà a un node superior per tal de dividir-la. Així, 5, l'element de dades central, es mourà cap amunt, i 3 i 21 es convertiran en els seus nodes esquerre i dret, respectivament.
Figura 4.3. Inserció 21 - Ara és el moment d'inserir el següent element de dades, és a dir, 11, que és més gran que 5 però inferior a 21. Per tant, s'inserirà 11 com a clau a l'esquerra del node format per 21 com a clau.
Figura 4.4. Inserció 11 - De la mateixa manera, inserirem el següent element de dades 1 a l'arbre, i com podem observar, 1 és menor que 3; per tant, s'inserirà com a clau a l'esquerra del node format per 3 com a clau.
Figura 4.5. Inserció 1 - Ara, inserirem l'element de dades 16 a l'arbre, que és més gran que 11 però inferior a 21. Tanmateix, el nombre de claus d'aquest node supera el nombre màxim de claus. Per tant, el node es dividirà, movent la tecla central a l'arrel. Per tant, s'inserirà 16 a la dreta del 5, dividint 11 i 21 en dos nodes separats.
Figura 4.6. Inserció 16 - L'element de dades 8 s'inserirà com a clau a l'esquerra de 11.
Figura 4.7. Inserció 8 - Inserirem 13 a l'arbre, que és inferior a 16 i superior a 11. Per tant, l'element de dades 13 s'ha d'inserir a la dreta del node format per 8 i 11. Tanmateix, com que el nombre màxim de claus de l'arbre pot només sigui 2, es produirà una divisió, movent l'element de dades central 11 al node anterior i 8 i 13 en dos nodes separats. Ara, el node anterior constarà de 5, 11 i 16, que de nou supera el nombre màxim de claus. Per tant, hi haurà una altra divisió, fent de l'element de dades 11 el node arrel amb 5 i 16 com a fills.
Figura 4.8. Inserció 13 - Com que l'element de dades 4 és inferior a 5 però superior a 3, s'inserirà a la dreta del node format per 1 i 3, que tornarà a superar el recompte màxim de claus en un node. Per tant, es tornarà a produir un vessament, movent el 3 al node superior al costat del 5.
Figura 4.9. Inserció 4 - Finalment, l'element de dades 9, que és més gran que 8 però inferior a 11, s'inserirà a la dreta del node format per 8 com a clau.
Figura 4.10. Inserció 9
En l'exemple anterior, hem realitzat diferents comparacions. El primer valor es va inserir directament a l'arbre; després d'això, s'havia de comparar cada valor amb els nodes disponibles en aquest arbre. La complexitat temporal de l'operació d'inserció en un arbre B depèn del nombre de nodes i .
Operació d'eliminació d'un arbre B
La supressió d'un element de dades en un arbre B conté tres esdeveniments principals:
l'actor ranbir kapoor edat
- Cercant el node on existeix la clau que s'ha d'esborrar,
- Esborrant la clau, i
- Equilibrar l'arbre, si cal.
Quan s'elimina un element de l'arbre, es pot produir una condició coneguda com a desbordament inferior. El desbordament es produeix quan un node consta de menys del nombre mínim de tecles; hauria de aguantar.
Els següents són alguns termes que cal entendre abans de visualitzar l'operació de supressió/eliminació:
Els següents són tres casos destacats de l'operació de supressió en un arbre B:
Cas 1: la supressió/eliminació de la clau es troba al node Leaf - Aquest cas es divideix a més en dos casos diferents:
1. La supressió/eliminació de la clau no viola la propietat del nombre mínim de claus que ha de tenir un node.
Visualitzem aquest cas utilitzant un exemple on suprimirem la clau 32 del següent arbre B.
Figura 4.1: Eliminació d'una clau de node fulla (32) de l'arbre B
Com podem observar, suprimir 32 d'aquest arbre no infringeix la propietat anterior.
2. La supressió/eliminació de la clau viola la propietat del nombre mínim de claus que ha de tenir un node. En aquest cas, hem de demanar prestada una clau del seu node germà proper en l'ordre d'esquerra a dreta.
En primer lloc, visitarem el germà proper Esquerra. Si el node germà esquerre té més d'un nombre mínim de claus, demanarà prestada una clau d'aquest node.
En cas contrari, comprovarem per demanar prestat del node germà dret proper.
Visualitzem ara aquest cas amb l'ajuda d'un exemple on esborrarem 31 de l'arbre B anterior. En aquest cas, demanarem prestada una clau del node germà esquerre.
Figura 4.2: Eliminació d'una clau de node fulla (31) de l'arbre B
Si els dos nodes germans propers ja consten d'un nombre mínim de claus, fusionarem el node amb el node germà esquerre o amb el dret. Aquest procés de fusió es fa a través del node pare.
Tornem a visualitzar-nos eliminant la clau 30 de l'arbre B anterior.
Figura 4.3: Eliminació d'una clau de node fulla (30) de l'arbre B
Cas 2: la supressió/eliminació de la clau es troba al node que no és Full - Aquest cas es divideix a més en diferents casos:
1. El node que no és Full/Intern, que s'elimina, es substitueix per un predecessor en ordre si el node fill esquerre té més del nombre mínim de claus.
exemples de sistemes operatius
Visualitzem aquest cas utilitzant un exemple on esborrarem la clau 33 de l'arbre B.
Figura 4.4: Eliminació d'una clau de node fulla (33) de l'arbre B
2. El node que no és Full/Intern, que s'elimina, es substitueix per un successor en ordre si el node secundari dret té més del nombre mínim de claus.
Si qualsevol dels fills té un nombre mínim de claus, fusionarem els nodes secundaris esquerre i dret.
Visualitzem aquest cas suprimint la clau 30 de l'arbre B.
Figura 4.5: Eliminació d'una clau de node fulla (30) de l'arbre B
Després de la fusió, si el node pare té menys del nombre mínim de claus, es poden buscar els germans, com en Cas 1 .
Cas 3: En el cas següent, l'alçada de l'arbre es redueix. Si la clau de destinació es troba en un node intern i l'eliminació de la clau comporta menys claus al node (que és inferior al mínim necessari), busqueu el predecessor en ordre i el successor en ordre. Si els dos fills tenen un nombre mínim de claus, no es pot demanar préstec. Això porta a Cas 2(3) , és a dir, fusionar els nodes fills.
Tornarem a buscar el germà per agafar una clau en préstec. Tanmateix, si el germà també consta d'un nombre mínim de claus, fusionarem el node amb el germà juntament amb el node pare i organitzarem els nodes fills segons els requisits (ordre ascendent).
Visualitzem aquest cas amb l'ajuda d'un exemple on esborrarem l'element de dades 10 de l'arbre B donat.
Figura 4.6: Eliminació d'una clau de node fulla (10) de l'arbre B
La complexitat temporal dels exemples anteriors varia depenent de la ubicació des d'on s'ha de suprimir la clau. Per tant, la complexitat de temps per a l'operació d'eliminació en un arbre B és O(log?n) .
La conclusió
En aquest tutorial, hem après sobre l'arbre B i hem visualitzat les seves diferents operacions amb diferents exemples. També hem entès algunes propietats i regles fonamentals de l'arbre B.