Ingineria programării

Acest proiect implementeazǎ operaţiile ce se realizeazǎ în mod curent cu structura avansatǎ de date denumitǎ B-arbore (B-Tree în englezǎ).

Documentul de faţǎ conţine aspectele teoretice legate de aceastǎ structurǎ de date.

Se vor detalia algoritmii de :

• cǎutare

• inserare

• ştergere

1. Prezentare

B-arborii reprezintǎ o structurǎ de date avansatǎ folositǎ pe scarǎ largǎ la implementarea bazelor de date şi care asigurǎ timpi optimi de operare cu informaţia stocatǎ pe suport magnetic care este o memorie mult mai mare decǎt cea internǎ, dar şi mult mai lentǎ. Ei pot fi priviţi ca o generalizare a arborilor de cǎutare la care s-au adus îmbunǎtǎţiri în ceea ce priveşte posibilitatea operǎrii cu pagini de memorie mari.

Arborii B exploateazǎ eficient memoria externǎ a calculatorului, depozitatǎ în general pe disc magnetic. Ei sunt folosiţi pentru realizarea sistemelor de baze de date deoarece duc la un numǎr redus de accese la disc. Datoritǎ acestei utilizǎri a lor şi operaţiile pe arbori-B se analizeazǎ atât din punctul de vedere al complexitǎţii în timp cât şi al numǎrului de accesǎri ale discului.

1. Nodul x are câmpurile :

a) n(x) - numǎrul de chei din nod

b) cheile din nod, în numǎr de n(x), ordonate: cheie1(x) _ . . . _cheien(x)(x)

c) un flag frunzǎ(x) care ne spune dacǎ nodul este sau nu frunzǎ

d) mulţimea c a fiilor care este vidǎ pentru frunze şi are n(x) + 1 elemente în rest: c1(x) . . . cn(x)+1(x)

e) între subarbori existǎ o relaţie de ordine parţialǎ, cheile dintr-un nod mǎrginind plajele de valori ale fiilor nodului (am notat cu ki o cheie oarecare din ci(x))

k1 ≤ cheie1(x) ≤ k2 ≤ . . . ≤ cheien(x)(x) ≤ kn(x)+1

2. ordinul sau gradul minim t ≥2 al arborelui care apare în douǎ constrângeri esenţiale

a) Fiecare nod, mai puţin rǎdǎcina, trebuie sǎ aibǎ cel puţin t − 1 chei. Dacǎ arborele nu este vid, rǎdǎcina are cel puţin o cheie.

b) Fiecare nod poate avea cel mult 2t − 1 chei, deci cel mult 2t fii.

Pentru t = 2, ceea ce se obţine se numeşte 2 − 3 − 4 arbore (un nod are 2, 3 sau 4 fii), iar pentru t = 3 se numeşte 3 − 4 − 5 − 6 arbore. În multe cǎrţi aceşti arbori sunt trataţi separat drept cazuri mai simple de arbori-B.

Cercetǎrile statistice aratǎ cǎ valorile cele mai bune pentru t sunt între 50 şi 2000, dupǎ care curba eficienţei structurii are o pantǎ descendentǎ.

Se demonstreazǎ uşor (prin inducţie) cǎ, dacǎ notǎm cu n numǎrul total de noduri şi cu h înǎlţimea, atunci

n ≥ 2th − 1

de unde se obţne relaţia

h ≤ logt[(n + 1)/2]

Complexitatea în spaţiu este tot O(log n) ca la arborii de cǎutare, dar baza logaritmului poate avea valori mari, înǎlţimea arborelui fiind practic mult mai micǎ. De exemplu pentru t = 1500, dacǎ folosim rezultatul de mai sus pentru h = 3 (rǎdǎcina plus 2 nivele) obţinem un numǎr minim de chei de 6,749,999,999 adicǎ de ordinul miliardelor! Iar numǎrul de accesǎri ale discului scade cu log t, pentru cǎ este proporţional cu înǎlţimea.

Corectitudinea algoritmilor ce urmeazǎ constǎ în garantarea pǎstrǎrii proprietǎţilor de B-arbore. Voi încerca sǎ se sublinieze acest fapt fie prin observaţii, fie prin detalierea pseudocodului.

Facultatea de Informatica - Manageriala