Cursul 13. B-Arbori

1. Generalităţi

Un B-arbore este un arbore oarecare echilibrat, destinat căutării de informaţii memorate pe disc magnetic (sau alt suport adresabil direct). Sunt similari cu arborii RN, dar în plus şi minimizează operaţiile de I/O.De obicei un B-arbore are înălţimea O(log2n). B-arborii sunt o generalizare naturală a arborilor binari; dacă un nod x conţine n[x] chei, atunci x are n[x]+1 fii. Cheile nodului x sunt folosite pentru a separa domeniul de chei vizibile din x în n[x]+1 subdomenii, fiecare vizibil prin unul din fii lui x. Când se caută o cheie într-un B-arbore există n[x]+1 posibilităţi de parcurgere, în funcţie de rezultatul comparării cu cele n[x]chei memorate în nodul x.

Exemplu:

2. Chestiuni tehnice privind memoria

Memoria unui computer se compune din:- memoria internă (memoria principală de tip ROM şi RAM) compusă din din chip-uri de

memorie din silicon, fiecare dintre ele putând să păstreze mai multe milioane de biţi; costul acestei tehnologii este mai scump per bit de informaţie decât costul similar al tehnologiei magnetice pe disc.

- memoria externă (memoria secundară) rezidentă de obicei pe disc magnetic; capacitatea acestui tip de suport depăşeşte cu câteva ordine de mărime capacitatea memoriei principale.

În figura următoare este prezentată, schematic, o unitate de disc magnetic clasică.

1

Nodurile colorate indică traseul de căutare al cheii R

Suprafaţa discului este acoperită cu o peliculă de material magnetizabil. Capul de citire/scriere poate citi/scrie de/pe această suprafaţă în timpul rotaţiei acesteia. Braţul de citire/scriere poate poziţiona capul la diferite distanţe de centrul discului. Un cerc concentric formează o pistă. De obicei o pistă este divizată în arce, iar unul sau mai multe arce formează o pagină. O pagină este de lungime egală cu un multiplu de 512 (de obicei 2048 sau mai mult). Pagina este unitatea de bază a schimbului dintre disc şi memoria internă.Timpul de acces la o pagină constă din:

- timpul necesar poziţionării capului pe pistă (pista e adresabilă!);- timpul de aşteptare a trecerii paginii (şi pagina e adresabilă) dorite prin dreptul capului.

Timpul de acces este mult mai mare decât timpul de citire/scriere deoarece acesta din urmă este asociat unei activităţi electronice pe când primul este asociat unei activităţi mecanice. Mai mult şi acest timp electronic este mult mai mare decât timpul de prelucrare ale informaţiilor citite. Se poate, aşadar, analiza separat cele doua componente ale timpului de execuţie:

- după numărul de accese la disc;- timpul de prelucrare al informaţiilor.Nu vom face această analiză ci vom trece direct la concluzia ei, în privinţa B-arborilor. În fiecare

moment, sistemul poate păstra în memoria internă numai un număr limitat de pagini. Algoritmii specifici B-arborilor presupun că există suficient spaţiu în memoria internă în acest scop.

Pe cele mai multe sisteme, timpii de execuţie ai algoritmilor de B-arbori sunt extrem de sensibili la numărul de operaţii de citire/scriere disc. Din acest motiv ar fi normal ca un nod în B-arbore să aibă lungimea unei pagini disc. De asemenea, numărul de fii (succesori direcţi) ai unui nod este bine să fie cât mai mare.

De obicei, factorul de ramificare este între 50 şi 2000, în funcţie de lungimea cheii şi de lungimea unei pagini. Un factor de ramificare mare reduce drastic înălţimea arborelui şi numărul de accese la disc pentru o cheie. De exemplu un B-arbore cu factorul de ramificare 1001 şi înalţinea 2, permite memorarea unui miliard de chei. Deoarece nodul rădăcină poate fi păstrat permanent în memorie, sunt necesare numai 2(două) accesări de disc pentru a găsi orice cheie din acest arbore.

În figura următoare se redă schematic un astfel de B-arbore.

2

3. Definiţia B-arborelui

Înainte de a da definiţia unui –arbore să spunem că de regulă se obişnuieşte, tocmai pentru a creşte factorul de ramificare, ca, nodurile interne să se memoreze numai chei şi pointeri spre fii, iar informaţia adiţională (pointer la ea) să fie înregistrată doar în frunze.

Un B-arbore T este un arbore cu rădăcină (radacina[T]) care are următoarele 5 proprietăţi:

1. Fiecare nod x are următoarele câmpuri:a. n[x], numărul curent de chei memorate în x,b. cele n[x] chei, memorate în ordine crescătoare: cheie1[x]cheie2[x] ...cheien[x][x];c. valoarea booleană frunză[x], care este true dacă x este nod frunză şi false dacă nodul

este intern. 2. Dacă x este intern, el mai conţine n[x]+1 pointeri spre fiii lui c1[x],c2[x],...,cn[x]+1[x]. Nodurile frunză nu au fii, astfel câmpurile lor ci sunt nedefinite.3. Cheile cheiei[x] separă domeniile de chei aflate în fiecare subarbore: dacă k1, k2... kn[x]+1 este

un sistem de cheie oarecare memorate într-un subarbore cu rădăcina ci[x], atunci:

k1 cheie1[x] k2 cheie2[x] ...cheien[x][x] kn[x]+1;

4. Fiecare frunză se află la aceeaşi adâncime, care este înălţimea h a B-arborelui5. Există o limitare inferioară şi una superioară a numărului de chei ce pot fi conţinute într-un nod.

Aceste margini pot fi exprimate printr-un întreg fixat t≥2, numit grad minim al B-arborelui:a. Fiecare nod, cu excepţia rădăcinii, trebuie să aibă cel puţin t-1 chei şi în consecinţă cel

puţin t fii; dacă arborele este nevid, atunci rădăcina trebuie să aibă cel puţin o cheie;b. Fiecare nod poate să aibă cel mult 2t-1 chei; de aceea, orice nod intern poate să aiba cel

mult 2t fii; un nod cu 2t-1 chei se va numi nod plin. Deci t-1 n[x] 2t-1 şi

t nr.fii 2t (nr. de fii sau pointeri)

Obs. Cel mai simplu B-arbore apare când t=2. Orice nod intern poate avea 2,3 sau 4 fii, (şi 1,2 sau 3 chei) motiv pentru care i se mai spune 2-3-4 arbore. În practică se folosesc valori mult mai mari pentru t.

3

4. Înălţimea unui B-arbore

Numărul de accese la disc este proporţional cu înălţimea B-arbore arborelui. Vom analiza acum cazul cel mai nefavorabil pentru înalţime.Proprietate.

Dacă n ≥ 1, atunci, pentru orice B-arbore T cu n chei de înălţime h şi gradul minim t ≥ 2, avem

h logt(n+1)/2

Demonstraţie:Dacă un B-arbore are înălţimea h, fiecare nod intern va avea un număr minim de t-1 chei

(rădăcina are 1 cheie); astfel există 2 noduri pe nivelul 1, 2t noduri pe nivelul 2, 2t2 noduri pe nivelul 3, ş.a.m.d., 2th-1 noduri pe nivelul h, conform figurii urmatoare.De aceea numărul n al cheilor satisface inegalitatea:

h logt(n+1)/2

Din această formulă se deduce puterea B-arborilor în raport cu arborii RN. Dacă t (fiind şi baza logaritmului) este mare numărul nodurilor scade cu factorul log t şi deci numărul de accesări ale discului se reduce.

6.Operaţii de bază în B-arbore

Vom da unele proceduri pentru căutare, creare, şi inserare şi vom presupune următoarele convenţii:

- rădăcina B-arborelui se află întotdeauna în memoria internă, nu se impune operaţia „read disk”

- operaţia „read disk” se impune la citirea unui nod intern.

Procedurile sunt prezentate „dintr-o singură trecere”, arborele fiind parcurs de la rădăcină spre frunze, fără reveniri.

a. Căutarea în B-arbore4

Căutarea seamănă cu căutarea într-un arbore binar, dar nu avem „decizie binară” ci o ramificare multiplă (vezi ciclul CâtTimp). Apel cu CautaB_Arbore(radacina[T],k). Procedura are 2 parametrii:- un pointer x la nod şi - valoarea de căutare k a cheii. Returnează cuplul (y,i), unde:- y este pointer la un nod iar- i este un indice astfel ca cheiei[y]=k,

Procedura CautaB_Arbore(x,k)i ← 1

CatTimp (in[x] si k > cheiei[x]) executai ← i+1

SfCatTimpDaca (in[x] si k = cheiei[x])

Atunci return (x,i) // succes, am gasit! SfDaca

Daca frunza(x)Atunci return (NULL,0) // nu am gasit cheia k, stopAltfel // Read-disk(ci[x]), deci eventual

// se citeste nodul fiu ci[x] return CautaB_Arbore(ci[x],k)// apel recursiv

SfDacaSfProcedura

b. Crearea unui B-Arbore

Procedura va crea nodul rădăcină:

Procedura CreazaB_Arbore(T)x ← AlocaNod() // alocare nod (procedura complexa), x e

// pointerfrunza[x] ← truen[x] ← 0WriteDisk(x) // procedura de scriere pe discradacina[T] ← x

SfProcedura

c. Inserează într-un B-Arbore

Inserarea este mai complicată, pentru că, de exemplu nu se poate insera o cheie într-un nod plin (care are 2t-1 chei). De aceea se foloseşte o procedură de divizare a unui nod plin y în 2 noduri în jurul cheii mediane cheiet[y], având fiecare nod câte t-1 chei fiecare. Cheia mediană cheiet[y] se deplasează „in sus” la locul potrivit în nodul părinte (care înainte de deplasare nu trebuie să fie plin) spre a repera fiecare din cei doi subarbori obţinuţi prin divizarea lui y. Dacă nodul y nu are părinte (deci e radacina B-arborelui) atunci se crează o nouă rădăcină şi înălţimea B-arborelui creşte cu unu.Vom da procedura DivideFiuB_Arbore, care are ca parametri de intrare:

- nod intern x care nu este plin, - un indice i şi- un nod y astfel încât y = ci[x] este un fiu plin al lui x;

5

Procedura divide nodul y în două şi rearanjează x astfel încât acesta va avea încă un fiu.Figura următoare ilustrează acest proces.

Procedura DivideFiuB_Arbore(x,i,y)z ← AlocaNod() //alocare nod zfrunza[z] ← frunza[y] //creare zn[z] ← t-1

Pentru j ← 1,t-1 executa //copiaza cheile in zcheiej[z] ← cheiej+t[y]

SfPtDaca nu frunza[y] //copiaza pointerii in z

AtunciPentru j ← 1,t executa

cj[z] ← cj+t[y]SfPt

SfDacan[y] ← t-1 //actualizeaza numarul de chei din yPentru j ← n[x]+1,i+1,-1 execută //muta pointerii din x la dreapta cu 1 pozitie

cj+1[x] ← cj[x]SfPtci+1[x] ← z //ci+1 devine z

Pentru j ← n[x],i,-1 //muta cheile la dreapta cu o pozitiecheiej+1[x] ← cheiej[x]

SfPtcheiei[x] ← cheiet[y] //modifica cheiei[x]n[x] ← n[x] + 1 //mareste nr de chei din x cu unaWriteDisk(y)WriteDisk(z)WriteDisk(x)

SfProcedura

Complexitatea este Θ(t).Operaţia de inserare a unei chei k este acum mult uşurată şi se execută într-o singură parcurgere,

coborând în arbore şi cere O(h) accesări disc. Procedura InsertB_Arbore foloseşte procedura de mai sus DivideFiuB_Arbore spre a se asigura că nici un descendent nu va deveni nod plin. Mai foloseşte şi o altă procedură InsertB_ArboreNeplin.

Procedura InsertB_Arbore(T,k)r ← radacina[T]Daca n[r]=2t-1 // pe ramura Atunci se face pentru radacina

Atunci // adica radacina este nod plins ← AlocaNod()radacina[T] ← sfrunza[s] ← falsen[s] ← 0c1[s] ← rDivideFiuB_Arbore(s,1,r)InsertB_ArboreNeplin(s,k)

6

AltfelInsertB_ArboreNeplin(r,k)

SfDacaSfProcedura

Următoarea procedură InsertB_ArboreNeplin inserează cheia k în nodul x despre care se presupune că nu este plin la momentul apelulul.Procedura InsertB_ArboreNeplin(x,k)

i ← n[x]Daca frunza[x] // insereaza daca nodul x e frunza

AtunciCatTimp (i≥1 si k< cheiei[x]) executa

cheiei+1[x] ← cheiei[x] i ← i-1

SfCatTimpcheiei+1[x] ← kn[x] ← n[x]+1WriteDisk(x)

Altfel // daca x nu e frunzaCatTimp (i≥1 si k< cheiei[x]) executa

i ← i-1SfCatTimpi ← i+1ReadDisk(ci[x])Daca n[ci[x]] = 2t-1

AtunciDivideFiuB_Arbore(x,i,ci[x])Daca k > cheiei[x]

Atunci i ← i+1SfDaca

SfDacaInsertB_ArboreNeplin(ci[x],k)

SfDacaSfProcedura

7