Complexitatea Algoritmilor de Cautare In Baze de Date
CUPRINS
Cap. 1. Introducere
1.1. Argumentul temei
1.2. Domeniul temei
Cap. 2 Baze de date și utilitatea lor
2. 1. Componentele unui Sistem de Baze de Date
2.2. Arhitectura internă a Sistemelor de Baze de Date
2.3. Limbaje și interfețe ale Sistemelor de Baze de Date
2.4. Avantajele oferite de Sistemele de Baze de Date
2.5. Clasificarea Sistemelor de Baze de Date
Cap 3 Necesitatea operațiilor rapide de căutare
3.1. Căutarea înregistrarilor într-o bază de date folosind FoxPro
3.2. Căutarea rapidă în tabele indexate
Cap 4 Căutarea arborescentă
4.1. Tipuri de organizare a fișierelor
4.1.1. Fișiere secvențiale
4.1.2. Fișiere cu dispersie
4.1.3. Fișiere cu index rar
4.1.4. Fișiere cu index dens
4.1.4. Fișiere cu structura de B-arbore
4.2. Modelul arborescent sau ierarhic
4.3. Arbori B prezentare, probleme/exerciții/exemple C++
Cap 5. Căutarea cu dispersie (hashing)
5.1. Funcția hash
5.2. Tabele hash
5.3. Aplicații
Cap 6. Metode de căutare în fișiere mari
Introducere
1.1 Argumentul temei
Am ales lucrarea „Complexitatea algoritmilor de căutare în baze de date” deoarece consider că tema aleasă este una practică și de actualitate, găsirea rapidă a informațiilor fiind operația care definește cel mai bine o bază de date complex.
Structura lucrării este gândită astfel :
Baze de date și utilitatea lor
Căutarea rapidă în baze de date
Căutarea arborescentă
Căutarea cu dispersie (hashing)
Căutarea în fișiere mari
Concluzii
Bibliografie
Domeniul temei
Sistemele de baze de date au devenit o componentă esențială a vieții de fiecare zi în societatea modernă. În cursul oricărei zile, fiecare dintre noi desfășurăm activități care implică interacțiunea cu o bază de date, ca de exemplu, depunerea sau extragerea unor sume de bani din bancă, rezervarea biletelor la tren sau avion, rezervarea locurilor la hotel, căutarea unei referințe bibiografice într-o bibliotecă computerizată (digital library), etc. 1.2 Domeniul temei
Față de vechile metode de înregistrare a datelor privind diferite activități pe fișe (documente scrise) sau chiar în fișiere pe disc, sistemul de baze de date oferă avantaje considerabile, ceea ce explică extinsa utilizare a acestora. Câteva dintre avantajele oferite sunt prezentate în continuare :
Viteză mare de regăsire și actualizare a informațiilor
Compactitate ridicată : volumul ocupat de sistemele de baze de date este mult mai redus decât volumul ocupat de documente scrise sau de fișiere necorelate
Redundanță scăzută a datelor memorate, care se obține prin partajarea datelor între mai mulți utilizatori și aplicații. În stocarea pe fișe sau în fișiere a datelor, fiecare aplicație conținea propriile seturi de date. În sistemele de baze de date, mai multe aplicații pot folosi date comune, memorate o singură dată
Menținerea integrității datelor prin politica de securitate (drepturi de acces diferențiate în funcție de rolul utilizatorilor), prin gestionarea tranzacțiilor și prin refacerea datelor în caz de funcționare defectuoasă a diferitelor componente hardware sau software
Independența datelor față de suportul hardware utilizat. Sistemele de gestiune a bazelor de date oferă o vedere (view) externă a datelor, care nu se modifică atunci când se schimbă suportul de memorare fizic, ceea ce asigură imunitatea structurii bazei de date și a aplicațiilor la modificări ale sistemului hardware utilizat
2. Baze de date și utilitatea lor
În sensul cel mai larg, o bază de date (database) este o colecție de date corelate din punct de vedere logic, care reflectă un anumit aspect al lumii reale și este destinată unui anumit grup de utilizatori. O bază de date poate fi creată și menținută manual (de exemplu, fișele de evidență a cărților dintr-o bibliotecă, așa cum erau folosite cu ani în urmă) sau computerizat, ceea ce reprezintă obiectul cursului de față.
Sistemele de gestiune a bazelor de date (în limba engleză "database management system" – SGDB) reprezintă totalitatea programelor utilizate pentru crearea, interogarea și întreținerea unei baze de date. Include două categorii de module: module care sunt comune cu cele ale sistemelor de operare ale calculatoarelor și module cu funcții specifice bazei de date. Subsistemele monitor conțin programele de control al perifericelor și sistemul de gestiune a fișierelor. Subsistemele externe sunt alcătuite din procesorul de definiție și programul de administrare. Alături de acestea există programe de descriere a bazei de date și cereri de prelucrare.Între utilizator și sistem există două interfețe: definirea bazei de date și utilizarea bazei de date. Definirea unei baze de date se execută sub controlul procesorului de definiție (PD), capabil să prelucreze programe de descriere, formulate folosind limbaje specializate cunoscute sub denumirea de limbaje de definiție a datelor (LDD).
Sistemele de baze de date pot avea dimensiuni (număr de înregistrări) extrem de variate, de la câteva zeci de înregistrări (de exemplu, o agendă cu numere de telefon) sau poate ajunge la sute de milioane de înregistrări (de exemplu, într-un sistem de plată a taxelor și impozitelor).
Ca și utilitate bazele de date ne permit posibilitatea de a efectua mai multe categorii de operații asupra datelor stocate:
Introducerea de noi date (insert);
Ștergerea unora din datele existente (delete);
Modificarea datelor memorate (update);
Interogarea bazei de date (query), pentru a regăsi anumite informații, selectate după un criteriu ales.
Definiția unei colecții de date ca fiind o bază de date se aplică, în sens mai restrâns, acelor colecții de date care permit toate operațiile de mai sus, inclusiv operația de interogare. Simple colecții de fișe (documente) dau fișiere de date, care conțin înregistrări cu o organizare simplă și care nu admit operații de interogare (selectarea unor informații după un criteriu ales), nu sunt considerate baze de date. De exempu, un editor de text (ca Microsoft Word) permite memorarea unor informații (texte), care pot fi create, modificate și consultate, dar nu se pot efectua operații de interogare. La fel, un instrument de calcul tabelar (cum este Microsoft Excel) oferă reprezentarea în diferite forme a unor date (tabele, grafice), dar nu permite operații de interogare.
2. 1. Componentele unui Sistem de Baze de Date
Componenele unui sistem de baze de date sunt: hardware, software, utilizatori, date (Figura 2.1).
Figura 2.1. Componentele unui Sistem de Baze de Date
Hardware. Sistemele de baze de date sunt, de regulă, instalate pe calculatoare de uz general, de la calculatoare PC standard, până la stații multiprocesor puternice. Bineînțeles, performanțele generale de operare ale calculatorului (numărul și viteza procesoarelor, dimensiunea și viteza de operare a memoriei principale) influențează în mod corespunzător performanțele sistemului de baze de date. Dar, ceea ce interesează în mod deosebit în utilizarea unui calculator pentru un sistem de baze de date este volumul (capacitatea) memoriei secundare, utilizată pentru memorarea colecției de date persistente ale bazei de date. Dat fiind că într-un sistem de baze de date este necesar accesul rapid la oricare din înregistrările de date, pentru memorarea acestora se folosesc discurile magnetice (hard-discuri).
Software. Între baza de date (colecția de date memorate fizic în fișiere pe hard-discuri) și utilizatorii sistemului există un nivel software, numit Sistem de Gestiune a Bazei de Date (SGBD) (Database Management System – DBMS). Toate cererile utilizatorilor de a accesa baza de date (pentru introducere, ștergere, modificare sau interogare) sunt gestionate (administrate) de către SGBD, care eliberează utilizatorii de necesitatea de a cunoaște organizarea particulară ale sistemului (driverele de disk, fișieree memorate, structura înregistrărilor de date). Cu alte cuvinte, SGBD permite utilizatorilor să aibă o viziune (vedere – view) la un nivel înalt a bazei de date, precum și acces la aceasta prin operații de nivel înalt, independent de detaliile de organizare hardware ale sistemului. Mai mult, SGBD-ul permite protecția datelor împotriva acceselor neautorizate, asigurând integritatea bazei de date.
SGBD-ul este cea mai importantă componentă software a unui sistem de baze de date, dar nu este singura componentă utilizată. Astfel, orice SGBD este dezvoltat și executat sub controlul sistemului de operare al calcuatorului respectiv. De asemenea, sunt folosite numeroase alte componente software pentru proiectarea, dezvoltarea sau exploatarea aplicațiilor de baze de date.
Utilizatori. Utilizatorii unui sistem de baze de date se pot împărți în trei categorii: programatorii de aplicații, utilizatorii finali și administratorul bazei de date.
Programatorii de aplicații sunt cei care scriu (dezvoltă) aplicațiile de baze de date, folosind limbaje de programare de nivel înalt (Cobol, PL/1, Fortran, C, C++, Java, Basic) cu extensii care permit încorporarea unor operații specifice de acces la baza de date. Aplicațiile rezultate pot fi aplicații cu execuție independentă (batch-processing) sau pot fi aplicații conversaționale (on-line) utilizate de utilizatorii finali ai sistemului pentru a accesa (într-un mod mai eficient și mai sigur) baza de date.
Utilizatorii finali sunt acei utilizatori care accesează baza de date prin intermediul unui program de aplicație care le conferă numai anumite posibilități de execuție și drepturi limitate de acces la date. Utilizatorii finali sunt persoane cu pregătire tehnică minimală, care efectuează un volum mare de operații asupra bazei de date, dar nu trebuie să cunoască mai mult decât posibilitățile oferite de programul pe care îl utilizează. De exemplu, utilizatorii finali ai unui sistem de rezervare a biletelor de avion sunt agenți de vânzări, care folosesc programul adevcat (scris de programatorii de aplicații), fără să fie necesar să cunoască întreaga structură a bazei de date.
Administratorul bazei de date este o persoană cu înaltă calificare tehnică care are ca sarcină menținerea funcționalității bazei de date prin stabilirea drepturilor de acces a diferitelor categorii de utilizatori, prin efectuarea operațiilor periodice de salvare a datelor (backup), prin monitorizarea performanțelor sistemului.
Date. Datele memorate într-o bază de date sunt date persisente, adică date care rămân memorate pe suport magnetic, independent de execuția programelor de aplicații. Datele persistente ale unei baze de date se introduc, se șterg sau se actualizează folosind date de intrare (provenind de a tastatură, sau recepționte prin transfer de mesaje). Datele de intrare sunt date nepersistente; ele sunt generate de utilizatori și sunt memorate (devenind date persistente) numai după ce au fost validate (acceptate) de către SGBD. Datele de ieșire ale unui sistem de baze de date sunt, de asemenea, date nepersistente; ele provin din operații de interogare a bazei de date și sunt puse a dispoziția utilizatorului (sub formă de afișări, rapoarte tipărite, etc).
Toate aceste componente asigură exploatarea unei baze de date după ce aceasta a fost proiectată și realizată. Activitatea de proiectare a unei baze de date implică alte categorii de personal cu înaltă calificare tehnică (analiști, programatori) sau administrativă (administrator de date). Proiectanții bazelor de date au responsabilitatea de a analiza realitatea reprezentată (modelată) de baza de date respectivă, de a identifica datele necesare să fie memorate, care să asigure menținerea evidenței activității dorite. De asemenea, în cursul proiectării t magnetic, independent de execuția programelor de aplicații. Datele persistente ale unei baze de date se introduc, se șterg sau se actualizează folosind date de intrare (provenind de a tastatură, sau recepționte prin transfer de mesaje). Datele de intrare sunt date nepersistente; ele sunt generate de utilizatori și sunt memorate (devenind date persistente) numai după ce au fost validate (acceptate) de către SGBD. Datele de ieșire ale unui sistem de baze de date sunt, de asemenea, date nepersistente; ele provin din operații de interogare a bazei de date și sunt puse a dispoziția utilizatorului (sub formă de afișări, rapoarte tipărite, etc).
Toate aceste componente asigură exploatarea unei baze de date după ce aceasta a fost proiectată și realizată. Activitatea de proiectare a unei baze de date implică alte categorii de personal cu înaltă calificare tehnică (analiști, programatori) sau administrativă (administrator de date). Proiectanții bazelor de date au responsabilitatea de a analiza realitatea reprezentată (modelată) de baza de date respectivă, de a identifica datele necesare să fie memorate, care să asigure menținerea evidenței activității dorite. De asemenea, în cursul proiectării unei baze de date, proiectanții selectează componentele hardware (sistemul de calcul), software (sistem de operare, SGBD, instrumente de dezvoltare și limbaje de programare), stabilesc structura conceptuală a bazei de date și mențin interacțiunea cu utilizatorii potențiali, pentru a asigura cerințele de prelucrare ale acestora.
2.2. Arhitectura internă a Sistemelor de Baze de Date
Arhitectura internă a unui sistem de baze de date propusă prin standardul ANSI/X3/SPARC (1975) conține trei nivele funcționale: nivelul intern, nivelul extern și nivelul conceptual (Figura 2.2).
Figura 2.2. Arhitectura internă a Sistemelor de Baze de Date
Nivelul intern este nivelul de reprezentare a datelor pe suportul fizic.
Nivelul extern reprezintă modul în care datele sunt percepute de utilizatori, existând câte o vedere (view) individuală a datelor pentru fiecare utilizator.
Nivelul conceptual corespunde unei reprezentări unice și abstracte a datelor, care asigură legătura între nivelul extern și cel intern. Nivelul conceptual este o vedere a întregului conținut a bazei de date prin intermediul schemei conceptuale a acesteia.
Toate aceste reprezentări sunt accesate prin intermediul SGBD-ului care asigură, de asemenea, cele două corespondențe (mappings): între nivelul extern și nivelul conceptual și între nivelul conceptual și nivelul intern.
2.3. Limbaje și interfețe ale Sistemelor de Baze de Date
Orice SGBD suportă două categorii de limbaje conceptuale: limbaje de descriere a datelor (LDD, Data Description Language – DDL) și limbaje de manipulare a datelor (LMD, Data Manipulation Language – DML). LDD permit definirea conceptuală a datelor, fără referință la modul de memorare fizică a datelor, asigurând în acest fel independența datelor în sistemele de baze de date. LMD asigură operațiile de introducere și prelucrare a datelor (actualizare, ștergere, interogare).
În momentul actual, limbajul cel mai frecvent utilizat în sistemele de baze de date relaționale este limbajul SQL (Structured Query Language), care include componentele LDD și LMD. Orice operație asupra unei baze de date relaționale se adresează SGBD-ului prin instrucțiuni SQL.
Instrucțiunile SQL pot fi trimise de către utilizatori în mod interactiv (de la o consolă) și sunt prelucrate direct de o componentă a SGBD sau pot fi înglobate (embeded SQL) în limbaje de programare de nivel înalt (Cobol, Fortran, C, C++, PL/1, Java, Basic) și transmise SGBD-ului în cursul execuției programelor respective. Programele de aplicații de baze de date mai prezintă, de regulă, interfețe grafice cu meniuri și comenzi prin intermediul cărora utilizatorii finali pot introduce, modifica sau selecta diferite date sau criterii de selecție.
De asemenea, multe SGBD-uri conțin o interfață specială pentru administratorul bazei de date, prin care acesta poate crea conturi, utilizatori, drepturi, etc.
2.4. Avantajele oferite de Sistemele de Baze de Date
Față de metodele mai vechi de înregistrare a datelor privind diferite activități pe fișe (documente scrise) sau chiar în fișiere pe disc, sistemele de baze de date oferă avantaje considerabile, ceea ce explică extinsa utilizare a acestora. Câteva dintre avantajele oferite sunt prezentate în continuare.
Compactitate ridicată față de volumul ocupat de documente scrise sau de fișiere necorelate.
Viteză mare de regăsire și actualizare a informațiilor, folosind interogări ale bazei de date.
Reducerea redundanței datelor memorate, prin partajarea datelor între mai mulți utilizatori și aplicații. În stocarea pe fișe sau în fișiere a datelor, fiecare aplicație conținea propriile seturi de date. În sistemele de baze de date, mai multe aplicații pot folosi date comune, memorate o singură dată. De exemplu, o aplicație de personal și o aplicație de rezultate la examene dintr-o universitate care exploatează o singură bază de date, pot folosi aceleași informații referitoare a structurarea facultăților și a secțiilor.
Posibilitatea de introducere a standardelor privind modul de stocare a datelor, ceea ce permite interschimbul informațiilor între diferite organizații.
Menținerea integrității datelor prin politica de securitate (drepturi de acces diferențiate în funcție de rolul utilizatorilor), prin gestionarea tranzacțiior și prin refacerea datelor în caz de funcționare defectuoasă a diferitelor componente hardware sau software.
Independența datelor față de suportul hardware utilizat. Sistemele de gesiune a bazelor de date oferă o vedere (view) externă (logică) a datelor, care nu se modifică atunci când se schimbă suportul de memorare fizic, ceea ce asigură imunitatea structurii bazei de date și a aplicațiilor la modificări ale sistemului hardware utilizat.
2.5. Clasificarea Sistemelor de Baze de Date
Se pot lua în considerație mai multe criterii de clasificare ale sistemelor de baze de date.
Clasificare după modelul de date. Majoritatea sistemelor de baze de date actuale se bazează pe modelul de date relațional (relațional data model) sau pe modelul de date obiect (object data model). Dezvoltarea continuă a acestor modele a condus către o nouă categorie de baze de date, numite obiect-reaționale, care combină caracteristicile modelului relațional cu cele ale modelului obiect. De asemenea, mai sunt încă în funcțiune baze de date în modele mai vechi (modelul ierarhic sau modelul rețea). Modelele de date utilizate de SGBD-uri vor fi studiate în capitolul următor.
Clasificare după numărul de utilizatori. Majoritatea sistemelor de baze de date sunt sisteme multi-utilizator, adică permit accesul concurent (în același timp) a mai multor utilizatori la aceeași bază de date. Un număr redus de sistemelor de baze de date sunt de tip mono-utilizator, adică suportă accesul doar a unui singur utilizator (la un moment dat).
Clasificare după numărul de stații pe care este distribuită baza de date. Există două categorii de sisteme de baze de date: centralizate și distribuite.
Un sistem de baze de date este centralizat dacă datele sunt stocate pe o singură stație (calculator). Un sistem centralizat poate suporta unul sau mai mulți utilizatori, dar, în ambele situații, datele, ca și SGBD-ul, rezidă în întregime pe o singură stație.
Un sistem de baze de date distribuit poate avea datele, ca și SGDB-ul, distribuite în mai multe stații interconectate într-o rețea de comunicație. Sistemele de baze de date pot fi reprezentate din punct de vedere a utilizării lor printr-o arhitectură de tip client-server.
Într-un sistem centralizat (Figura 2.3) există un singur server, care este chiar SGBD-ul, care răspunde cererilor unui singur client (în sistemele mono-utilizator) sau mai multor clienți (în sistemele multi-utilizator), accesând baza de date respectivă. Clienții sunt programe de aplicații, oferite de furnizorul SGBD-ului sau dezvoltate de programatori (utilizatori). Aplicațiile client pot fi executate pe stații diferite, conectate printr-o rețea de comunicație cu stația pe care este executat serverul. Această arhitectură permite o prelucrare distribuită a datelor și, mai mult, o configurare a sistemului adaptată cerințelor de calcul particulare. Astfel, serverul bazei de date poate fi un sistem puternic, echipat corespunzător (cu volum mare de memorie secundară), în timp ce fiecare client este o stație personală, cu putere de calcul adecvată aplicației executate.
Figura 2.3. Sisteme de baze de date centralizate: (a) mono-utilizator; (b) multi-utilizator
Sistemele de baze de date distribuite pot fi reprezentate într-un mod asemănător din perspectiva structurării client-server (Figura 2.4).
Figura 2.4. Sistem de baze de date distribuită
Mai multe servere, conținând SGBD și date sunt distribuite pe stații conectate printr-o rețea de comunicație, în timp ce aplicațiile client rulează pe alte stații din rețea și solicită servicii de la servere. Numeroase probleme de partiționare a datelor memorate, de optimizare, de transparență a accesului sunt rezolvate de către SGDB distribuite.
Necesitatea operațiilor rapide de căutare
Bazele de date voluminoase sunt foarte greu de exploatat fara ajutorul unui mecanism de căutare, care sa permită regasirea oricărei date în timp util.
Căutarea înregistrărilor într-o bază de date folosind FoxPro
LOCATE FOR <expL1>
[<domeniu>][WHILE <expL2>]
Efectul comenzii respective este acela de poziționare a indicatorului de înregistrări pe prima înregistrare care respectă condiția, pentru care valoarea expresiei logice este adevărată.
Comanda caută prima înregistrare care respectă condiția <expL1> în baza de date activă. Domeniul înregistrărilor care se testează este dat de clauzele <domeniu> si WHILE, cel implicit fiind ALL.
La găsirea unei înregistrari care respectă condiția <expL1>, indicatorul de înregistrări se va poziționa pe înregistrarea respectivă.
Într-o bază de date pot exista mai multe înregistrări ce respectă o condiție dată. Prima dintre acestea va fi gasită folosind comanda LOCATE, următoarele vor fi găsite prin intermediul comenzii CONTINUE.
Testarea reușitei sau nereușitei căutarii se face cu ajutorul funcțiilor RECNO ( ), FOUND ( ) si EOF ( ).
FOUND ([<expL1> / <expC>])
Returnează adevărat în cazul unei căutari cu succes și fals în caz contrar.
<expN>, <expC> identifică baza de date la care se referă funcția.
Exemplu Să se găsească primele două mijloace fixe în folosința din baza de date
USE mfixe
LOCATEFOR stare = .t.
?FOUND ( )
.T.
?EOF ( )
-F
?RECNO ( )
1.
CONTINUE
? FOUND ( )
.T.
?RECNO ( )
3.
USE
3.2 Căutarea rapidă în tabele indexate
Indexarea este o metodă de accesare rapidă a conținutului unei tabele, fară a duplica datele într-o altă tabelă. Indexarea presupune un set de pointeri ordonați logic prin valoarea unei chei.
Exemplu: ELEVI.DBF (nume,pren,clasa,absn) Parcurgerea ordonată după nume se poate face prin construirea unui index care să rețină numărul înregistrării din tabelă și criteriul "nume". Liniile acestui index sunt ordonate după valorile cheii. Solicitarea de a accesa tabela ELEVI prin cheia "nume" va impune parcurgerea indexului. Pentru fiecare linie din index pointer-ul ajunge la articolul cu datele propriu-zise. Indexarea realizează o legatură logică între index și fișierul de date prin numărul articolului. Se observă în desenul alăturat:
Indecsii pot fi depuși în fișiere index (.CDX) asociate tabelei, au același nume și se deschid/închid odata cu tabela, orice operație de actualizare asupra acesteia reflectându-se automat si asupra tuturor indecsilor membri. Se mai numescfișiere index structurale.
O tabelă paote avea mai mulți indecși dar numai unul este, la un moment dat, activ și determină criteriul de parcurgere.
Tipuri de indecși:
· Regular index – este folosit pentru selectarea ordinii de parcurgere din câmpurile non-cheie;
· Unique index – este folosit pentru selectarea ordinii de parcurgere bazată pe prima apariție a valorii în câmpul specificat;
· Candidate index – este folosit în tabelele incluse într-o bază de date care au deja fixat indexul primar dar care doresc verificarea valorilor unice și în alt câmp decât în câmpul cheie. Se pot folosi, desigur, și în tabelele libere.
· Primary index – este folosit în contextul unei tabele incluse într-o bază de date și asigură introducerea valorilor unice pentru cheie articolelor.O tabelă are un singur index primar.
3.3 Crearea unui index
INDEX ON<exp> TAG <tag> [UNIQUE] [DESCENDING] [ASCENDING] [FOR<cond>]
Comanda INDEX permite crearea unui reper index cu numele <nume-tag>. Reperul se depune în fișierul structurat asociat tabelei. Criteriul de indexare este dat de expresia din clauza ON<exp>. Clauzele A/D pot indica sensul ordonării, implicit fiind cel crescator.
Exemplu: fie tabela ELEVI.DBF cu urmatorul continut
index on clasa tag clasa unique | creare tag clasa în fisierul structural elevi.cdx
list | se permite accesul la primul articol al fiecărei clase
Activarea și precizarea indexului principal
SET ORDER TO TAG <tag> USE <bd> ORDER <tag>
Exemplu: use elevi order nume && activ este tag-ul nume din Elevi.cdx
set order to tag unu && activ este tag-ul nume din Elevi.cdx
set order to 0 && se consideră tabela neordonată
ștergerea unui index
Comanda DELETE TAG <tag> se folosește pentru ștergerea unui reper.
Exemplu: delete tag nume
Definirea vizuală a indecsilor
Realizarea interactivă a indecșilor pentru o tabelă presupune deschiderea ferestrei Table Designer ( care se deschide cu comanda Modify Structure ).
3.3 Căutare rapidă și poziționare în tabela indexată
Una dintre funcțiile importante ale unei baze de date (SGBD – Sistem de Gestiune a Bazelor de Date) este accesarea rapidă a tabelei. Condiția impusă este ca tabela sa fie indexată după expresia de căutare.
1.Comanda FIND <expC>| '<expC>' – caută în tabelă printre valorile de indexare prima valoare care este egală cu <expC> de căutare. Expresia de căutare este o constantă și trebuie încadrată obligatoriu de delimitatorii de șir dacă espresia de căutare începe cu spații.
2.Comanda SEEK <exp> – caută în tabelă activă prima valoare a cheii de indexare care este egală cu expresia de căutare. Căutarea se oprește la primul articol din tabela care are cheia de indexare egală cu valoarea expresiei, dacă o astfel de înregistrare există. În cazul în care căutarea nu a avut succes se mută pointerul de fișier pe EOF sau pe BOF În funcție de modul de setare a calculatorului – cu comanda SET NEAR ON | OFF – care determină unde se va situa pointerul după căutarea cu SEEK fară succes: pentru ON se poziționează pe BOF, pentru OFF (implicit) se poziționează pe EOF.
Exemplu : efectul comenzii SET NEAR ON/OFF
use elevi
index on cls tag cls
set near off
seek '12B' &&căutați o valoare care nu există
?found()
.F. &&se afișează false pentru căutare eșuată
set near on
seek '12A' &&căutați o valoare care există
?recno() && va afișa numărul înregistrării unde a găsit valoarea căutata
display nume && va afișa numele elevului căutat
3.Funcțiile de test asupra succesului sau insuccesului căutarii sunt:
FOUND() care întoarce .T. dacă articolul s-a găsit;
EOF() care întoarce .T. dacă articolul căutat nu s-a găsit
4.Funcția de căutare SEEK (<exp>[,<nr-zona>/<alias>]) – caută prima înregistrare pentru care cheia de indexare este egală cu <exp>. Dacă se găsește, funcția întoarce .T. iar indicatorul de înregistrări se va poziționa pe înregistrarea gasită; altfel întoarce .F. și pointerul de fișier va fi poziționat după ultimul articol. Căutarea se realizează în fișierul identificat prin <alias> sau numărul zonei în care este deschis.
ExempluL1: pentru tabela ELEVI.DBF
use elevi order nume
find 'popescu' && se caută persoana cu numele Popescu
?found() && funcția FOUND va întoarce .T.
var='popescu' && se poate face căutarea cu o variabilă var
find var && dar se apelează la macrosubstituție
?recno() && funcția va întoarce numărul curent al înregistrarii căutate
var='popescu' &&altă metodă de căutare – cu seek
seek var
?found()
Brow
ExempluL2: efectul comenzii SET EXACT ON/OFF – comanda se folosește pentru compararea a 2 șiruri de caractere de lungimi diferite. Argumentul ON cere specificarea a șirului de caractere integral pentru căutarea unei înregistrări, iar argumentul OFF (implicit) cere specificarea primelor caractere din șirul căutat
set exact on
seek 'popescu'
set exact off &&asigură căutarea cu o parte a cheii de indexare
seek 'pop '
Exercitiu: Fie tabela MECIURI.dbf care reține toate meciurile din campionat.
Cerința:completați "codul" fiecărui meci cu o informație care să identifice poziția meciului în programul competițional, cronologic, pentru aceeași dată, în ordinea alfabetică a locului de desfășurare și, dacă sunt meciuri în aceeași zi, în acelașii loc, le vom aranja în funcție de oră.
use meciuri
sort on data_desf,localitate, ora to man
use man
replace all cod with recno()
list
use
erase meciuri.dbf
rename man.dbf to meciuri.dbf
4. Căutarea arborescenta
4.1. Tipuri de organizare a fișierelor
În organizarea fișierelor se ține seama de mai mulți factori cum ar fi frecvența cu care se efectuează anumite tipuri de operații asupra fișierelor, câmpurile implicate in operațiile de căutare (cheile fișierului) sau relația in care se află inregistrările fișierului cu alte informații din sistem. Dacă exită ponteri la unele inregistrări din fișier se spune că fișierul este cu inregistrăi fixate și în acest caz fiecare înregistrare rămane, de obicei pe locul pe care a fost introdusă, locul ocupat de o astfel de înregistrare nu mai poate fi refolosit după eliminarea înregistrării. În caz contrar se spune că fișierul este cu înregistrări nefixate, înregistrările putând fi mutate sau spațiul eliberat prin eliminarea unor înregistrări putând fi reutilizat.
Cele mai des utilizate tipuri de organizare a fișierelor sunt: secvențial, cu dispersie, cu index rar, cu index dens, cu structura de B-arbore. Aceste cinci tipuri de organizare a fișierelor vor fi descrise pe scurt in cele ce urmează.
4.1.1. Fișiere secvențiale
Fișierele secvențiale (englezește – heap files) presupun înregistrările memorate ca elementele unei liste liniare de cele mai multe ori in blocuri consecutive, legate intre ele prin pointeri sau prin construirea unui tabel separat cu adresele acestor blocuri ce permit accesul la ele.
Inserarea unui element se face de cele mai multe ori prin adăugarea noului element la sfârșitul listei (în special în cazul fișierelor cu înregistrări fixate și neordonate). Inserarea se mai poate face prin includerea noi înregistrări pe primul loc disponibil pentru fișiere cu înregistrări nefixate și cu biți de ștergere, prin includerea noii înregistrări într-un bloc existent sau unul nou și legarea ei în lista pentru înregistrări fixate sau ordonate, prin deplasarea fizică a unor înregistrări pentru a face loc noiiî nregistrări în cazul fișierelor cu înregistrări nefixate si ordonate sau prin alte tehnici asemănătoare.
Ștergerea unui element se face prin înlocuirea elementului care se elimină cu ultimul element al fișierului, prin deplasarea elementelor care urmează înregistrării care se elimină cu un element către începutul fișierului pentru fișiere cu înregistrări nefixate si fară bit de ștergere, eventual ordonate, prin modificarea bitului de ștergere sau prin eliminarea din lista cu legaturi și marcarea înregistrării ca libera. Pentru fișierele cu înregistrări nefixate pentru care unele blocuri nu mai conțin înregistrări, acele blocuri sunt eliberate și pot fi reutilizate.
Modificarea unui element se face de obicei prin citirea âînregistrării corespunzatoare, modificarea câmpurilor implicate și rescrierea în acelașii loc a valorilor rezultate. Pentru fișierele ordonate pentru care sunt afectate câmpuri ce contribuie la ordonare operația de modificare presupune citirea valorilor înregistrării implicate, ștergerea înregistrării din fișier, modificarea valorilor câmpurilor și inserarea unei noi înregistrări cu valorile reactualizate.
Căutarea unui element se poate face prin parcurgerea secvențială a tuturor elementelor fișierelor și verificarea condițiilor de selecționare a înregistrării examinate. Aceasta metodă presupune in medie examinarea a (N+1)/2 înregistrări la o căutare cu succes și a N înregistrări la o căutare fără succes, unde N este numărul de înregistrări din fișier. Dacă fișierul este ordonat și se face căutare după cheie (câmpurile după care s-a făut ordonarea) se obține o eficiență mai bună în cazul căutării secvențiale la căutarea fără succes și anume în medie (N+1)/2 înregistrări examinate dar mai eficiente sunt căutările binare care dau in medie log N înregistrăi examinate sau căutările cu calculul adresei care dau in medie log log N înregistrări examinate (vezi [Knuth]).
Avantaje: programe simple de organizare și utilizare, nefolosirea sau folosirea în mică măsura a spațiului suplimentar pentru legături sau alte informații, posibilități multiple de reorganizare, uneori permit operare simplă utilizabilă pentru fișiere dinamice.
Dezavantaje: numărul mare de elemente examinate în medie la căutare, operații dificile în cazul fișierelor ordonate.
Utilizare: Dacă în cazul unor fișiere mari organizarea secvențiala este practic ineficientă, în cazul unor fișiere de dimensiuni mici se poate utiliza cu succes aceastăorganizare.
4.1.2 Fișiere cu dispersie
Fișierele cu dispersie (englezește – hashed files) grupeazș înregistrările în clase de înregistrări fiecare clasă fiind memorată în unul sau mai multe blocuri de memorie. Apartenența unei înregistrări la una din clase este determinată rapid (de obicei printr-un proces de calcul) în funcție de valoarea pe care o are cheia înregistrării. Funcția care determină această corespondență se numește funcție de dispersie Fiecare clasă este organizată prin metode de organizare secvențială.
Numărul de clase și modul de calcul al clasei asociate unei înregistrări se aleg in așa fel încât să asigure pe de o parte o distribuție cât mai uniformă în claseși pe de altă parte ca numărul mediu de înregistrări într-o clasă să nu fie prea mare pentru a da un timp rezonabil la căutare. O funcție de dispersie des utilizată este cea care interpretează șirul de biți corespunzător chei ca un număr natural iar clasa asociată elementului este dată de restul împărțirii acestui număr la numărul de clase (eventual adunat cu 1 dacă numerotarea începe de la 1 și nu de la 0).
În implementarea fișierelor cu dispersie se construiește o listă numită director cu pointeri la blocul de începere corespunzător fiecărei clase, blocurile unei aceleiași clase fiind înlănțuite ultimul bloc având pointer nul. Directorul este memorat în blocuri ale fișierului și dacă este de dimensiuni mici este încărcat în memoria principală de câte ori se lucrează cu fișierul respectiv pentru a micșora numărul de accese la memoria externa.
Operațiile cu fișiere cu dispersie se fac analog cu operațiile cu fișiere secvențiale, singura deosebire fiind dată de localizarea clasei corespunzătoare înregistrării implicate.
Dacă clasele devin prea mari se pune problema reorganizării fișierului cu mărirea numărului de clase. O bună alegere a funcției de calcul a clasei permite ca în cazul unei măriri de un număr de ori a numărului claselor, noua funcție de calcul să stabilească drept noi clase repartiții ale vechilor clase. De exemplu dacă se dublează numărul de clase și funcția de împrăștiere este obținută ca restul unei împărțiri la numărul de clase, atunci orice clasă i se împarte în două clase distincte și anume i și n+i unde n este numărul inițial de clase. Deci în acest caz operația de reorganizare se poate face clasă cu clasă.
Avantaje: timp relativ redus de acces pentru clase de dimensiuni mici, programe relativ simple de gestionare și utilizare, posibilități de organizare în cazul fișierelor cu înregistrări fixate.
Dezavantaje: spațiu suplimentar pentru organizarea claselor, posibile reorganizări, dificilă parcurgerea în ordine a înregistrărilor din tot fișierul.
Utilizare: organizare destul de des utilizată în tehnicile de implementare a bazelor de date mai ales pentru modelele rețea si ierarhic; cu posibilități bune de operare în cazul fișierelor dinamice.
4.1.3. Fișiere cu index rar
Fișierele cu index rar sau indexat secvețtiale presupun memorarea înregistrărilor într-un fișier numit fișierul principal în ordinea crescătoare a cheilor și grupate pe pagini. Se adaugă un alt fișier, numit fișierul index ce conține pentru fiecare pagină din fișierul principal câte o înregistrare cu valoarea celei mai mari chei din pagina si adresa de început a paginii. Fișierul index este ordonat crescător în raport cu valoarea cheii folosind pentru el o metodă de organizare oarecare. De cele mai multe ori pagina corespunde cu un bloc. Înlanțuirea blocurilor în ordinea crescătoare a cheilor permite parcurgerea secvențială ordonată a fișierului. Din necesități practice se pot înlănțui și blocurile corespunzătoare fișierului index.
Căutarea se face cu o căutare în fișierul index prin metode adecvate organizării lui (căutare liniară, căutare binară sau căutare prin calculul adresei) pentru găsirea unei îregistrări ce conține cea mai mică cheie mai mare sau egală cu cheia căutată. Adresa din acea înregistrare dă posibilitatea accesului la pagina care poate conține înregistrarea căutată. Apoi se face o căutare secvențială sau prin altă metodă in acea pagină. Eventual se testează bitul de existență sau bitul de ștergere dacă aceștia există.
Inserarea se face urmând procedeul de la căutare pentru determinarea paginii unde urmează să apară noua înregistrare și dacă mai este loc în pagina se aplică procedeul de inserare în fișier ordonat, altfel se introduce un bloc nou cu distribuirea înregistrărilor implicate și modificarea corespunzatoare a fișierului index. Dacă cheia noii înregistrări este mai mare decât cea mai mare cheie existența în fișier trebuie modificată cheia ultimei pagini din index punând cheia ultimei înregistrări introduse.
Ștergerea unui element se face prin eliminarea elementului din lista ordonată corespunzătoare paginii în care apare acea înregistrare. Dacă blocul nu mai conține nici-o înregistrare se elimină blocul respectiv din fișierul principal cu modificarea corespunzătoare a indexului. Se observă că în cazul în care se elimină înregistrarea cu cheia cea mai mare din pagină sistemul funcționează corect și dacă lăsam neschimbat indexul in acest caz.
Modificarea se face prin citire, schimbarea valorilori și rescriere când nu sunt afectate câmpuri ce aparțin cheii sau prin stergere și inserare în cazul afectării unor câmpuri ce apar in cheie.
Pentru fișierele cu înregistrări fixate indexul nu se schimbă iar noile înregistrări introduse și care nu mai încap în blocurile corespunzătoare lor în blocuri noi legate de acestea formând clase ca la fișierele prin dispersie. Dacă clasele devin foarte mari trebuie aplicată o reorganizare. Parcurgerea in ordine a înregistrărilor se poate face dacă se asociază fiecărei înregistrări un pointer la înregistrarea următoare.
Avantaje: spațiu supimentar pentru reprezentarea fișierului index relativ redus, permite determinarea inregistrarilor cu chei intr-un interval dat, bine adaptabil pentru fișiere dinamice, fișierele index nu sunt cu înregistrări fixate ceea ce permite reorganizări mai simple și permite aflarea înregistrării cu cheia cea mai mică dintre cele cu chei mai mari decât o valoare dată (cheia ce acoperă o valoare v dată).
Dezavantaje: uneori poate să consume spațiu suplimentar mult dacă paginile nu sunt încarcăte pâna aproape de capacitatea maxima, operații de depșire a capacității unei pagini dificil de manevrat.
Utilizare: Se folosesc in special la organizarea unor fișiere statice sau pentru îmbunătațirea timpului de acces la alte fișiere index.
4.1.4. Fișiere cu index dens
Organizarea cu index dens presupune asocierea la un fișier numit fișierul de baza a unui alt fișier numit fișier index cu acelașii numar de înregistrări ca fișierul de baza. Înregistrările din fișierul index conțin, ca și în cazul fișierelor cu index rar, perechi formate din cheile înregistrărilor fișierului de bază și pointeri la aceste înregistrări dar de data aceasta pentru toate înregistrările fișierului de baza. Pentru fișierul index se poate folosi oricare dintre tipurile de organizări prezentate.
Avantaje: inregistrările fișierului index sunt nefixate ceea ce permite o organizare mai eficientă, înregistrările fișierului index fiind mai scurte decât ale fișierului de baza numartul de blocuri ce trebuiesc accesate este mai mic pentru diferitele operații cu fișierul, la același fișier de bază pot fi asociate mai multe fișiere index corespunzătoare diferitelor chei. Poate fi utilizat in transformarea unui fișier cu înregistrari fixate intr-un fișier cu înregistrări nefixate.
Dezavantaje: spatiu suplimentar ocupat, necesitatea combinării cu alte metode, neasigurarea unei bune acoperiri a spațiului alocat.
4..1.5. Fișiere cu structura de B-arbore
Pentru fișierele de dimensiuni foarte mari se poate privi indexul din organizarea indexat secventială ca un fisier de bază și pentru el să se organizeze un fișier index rar. Procedand recursiv până se obține un fișier index ce ocupă un singur bloc obținem o structură indexată pe mai multe nivele foarte flexibilă și eficientă de arbore echilibrat care are drept frunze blocuri ce conțin pointeri la inregistrările fișierului sau eventual chiar înregistrările dacă fișierul nu este cu înregistrări fixate. Numele de B-arbore al acestor structuri vine de la denumirea in limba engleză a lor balanced trees.
Pentru a asigura o ocupare eficientă a spațiului toate operațiile care se fac in B-arbori respectă condiția de a lăsa in toate blocurile cu excepția eventual a rădăcinii a unui numar de înregistrări mai mare decat jumătate din capacitatea blocului respectiv. Daca de exemplu un nod intern poate memora 2d-1 înregistrări (cheie+adresa bloc) și o frunză poate sa memoreze 2e-1 înregistrări atunci nodurile interne cu excepția eventual a rădăcinii trebuie să aiba cel puțin de înregistrări și frunzele trebuie să aibă cel puțin e înregistrări.
Se observă că intr-un B-arbore ultima cheie a fiecărui bloc nu este necesară presupunându-se că orice înregistrare cu cheia mai mare decât penultima cheie a blocului se află în blocul dat de ultimul pointer.
Căutarea se face începând de la radăcina și luand în continuare blocul dat de adresa corespunzătoare celei mai mici valori a unei chei dintre cele mai mari sau egale cu cheia cautată (in căutarea liniara este prima cheie mai mare sau egală cu cheia căutata) apoi aplicând acest procedeu recursiv pâna se ajunge la o frunză unde poate fi găsită
înregistrarea căutată
Inserarea se face prin localizarea ca la căutare a blocului unde ar trebui să se afle noua înregistrare și prin inserarea acelei înregistrări in blocul găsit dacă mai este loc. Dacă toate înregistrărle blocului sunt ocupate se creeaza un nou bloc cele două blocuri împărțindu-și în mod egal înregistrările și apoi inserânu-se la nivelul imediat superior adresa noului bloc împreună cu cea mai mare cheie a lui (se presupune că in blocul nou introdus s-au pus înregistrările cu cele mai mici chei. Dacă se ajunge astfel la rădacina arborele crește numărul nivelelor cu unu noua rădacina avand în acest caz doi fii: un bloc nou introdus și vechea rădăcină.
Ștergerea se face prin localizarea înregistrării care se elimină ca la căutare și se elimină această înregistrare din bloc. Dacă în bloc rămân mai mult de jumătate înregistrări ocupate atunci procesul se termină, altfel blocul respectiv se combină cu un bloc vecin fie redistribuind înregistrările fie, dacă și acel bloc este la limita inferioară se formează din cele două blocuri unul singur. Combinarea a doua blocuri poate produce modificări sau ștergeri și la nivelele superioare uneori (foarte rar) putând micșora înălțimea arborelui (cazul unei rădăcini cu numai doi fii care se combină într-un singur bloc).
Modificarea se face la fel ca și pentru celălalte metode în funcție de faptul dacă sunt afectate sau nu câmpurile cheie.
Pentru operațiile cu B-arbori se fac un număr de citiri/scrieri de blocuri de ordinul lui (log n – log e)/log d unde n este numărul de înregistrari din fișier, o frunză poate sa conțina cel mult 2e-1 înregistrări și un nod intermediar poate să conțina cel mult 2d-1 perechi cu chei și adrese.
Avantaje: aplicabil cu foarte bune rezultate în cazul fișierelor dinamice datorită numărului mic de blocuri accesate în operații și a numărului mic de operații la reactualizări, permite furnizarea listei elementelor în ordinea dată de cheie, se poate aplica oricărui fișier unul sau mai mulți B-arbori care să lucreze ca fișiere index, o buna ocupare a spațiului alocat (in medie circa 75% spațiu ocupat).
Dezavantaje: dificil de programat operațiile cu B-arbori, folosire spațiu suplimentar pentru nodurile interne.
4.2.Modelul arborescent sau ierarhic.
Sistemele de baze de date au in vedere trei tipuri de structuri de reprezentare a informațiilor la nivel logic și de operare cu ele și anume modelul relațional, modelul rețea și modelul arborescent sau ierarhic.
Modelul ierarhic (arborescent)
Modelul ierarhic poate fi privit ca un caz particular al modelului rețea in care diagrama asociată este o pădure (mulțime de arbori) și in care toate legăturile sunt pe direcția drumului de la rădăcină la nodul fiu din relație, toate relațiile fiind de tipul unu-la-mai-mulți.
Ca și in cazul celorlalte două modele există posibilitatea interpretării diagramelor entitate-relație sub formă modelului ierarhic. Pentru evitarea redondanțelor in modelul ierarhic se folosește noțiunea de element virtual care înlocuiește dublura unui element prin adresa elementului respectiv fiecare element apărând în baza de date reală o singura dată. În felul acesta se evita unele redondanțe.
Operațiile din bazele de date de tip ierarhic se traduc în procese de parcurgere a arborilor. Elemntele virtuale permit în acest caz legarea informațiilor din aceeași entitate sau din entități diferite.
Pentru prelucrarea eficientă a unei relații de tip mai-mulți-la-mai-mulți între entitățile A și B se pot introduce doi arbori: unul cu tatăl A și fiu virtual B și unul cu tatăl B și fiu virtual A.
Transformarea diagramelor entitate-relație în paduri se face în mai multe etape. Mai întâi se transformă o astfel de diagramă intr-o rețea prin metodele prezentate anterior. Apoi se construiesc pe rând arbori selectând ca radacină a lor un nod din rețea neselectat înca și cu cât mai puține arce care să intre în el din noduri neselectate. Se adaugă apoi cât mai există arcele ce pleacă din noduri selectate in acest arbore fie către noduri deja selectate în alți arbori și în acest caz aceste noduri se declară virtuale, fie către noduri incă neselectate care se adaugă arborelui și se consideră astfel selectate. Procedeul continuă pâna nu mai sunt noduri neselectate.
Implementarea la nivel logic pentru modelul ierarhic poate fi cea utilizată pentru modelul rețea sau prin înregistrări de lungime variabilă. Formatele acestor înregistrari se construiesc prin procedeul urmă
tor: formatul asociat unei frunze avand campurile a este a* iar pentru un nod interior cu campurile b si pentru care fii sai au formatele asociate a1,a2,…,ak asociem formatul (b a1 a2 … ak)*. Deci pentru baza de date se obțin un numar de fișiere cu lungimi variabile egal cu numarul de arbori din schema asociata bazei de date respective.
Datele sunt puse pe mediul extern in ordinea data de parcurgerea in preordine a arborilor ceea ce usureaza determinarea informațiilor pentru cererile care se refera la descendenții unor noduri printr-un numar mic de accese la mediul extern.
4.3. Arbori B
Definiție
Un arbore B de ordin m este un arbore cu urmãtoarele proprietãți:
rãdãcina este o frunzã sau un nod cu 2 pâna la m descendenți;
toate nodurile interne (cu excepția rãdãcinii ) au între sup(m/2) (sup(x) este cel mai mic intreg mai mare ca x) și m descendenți;
toate frunzele sunt pe acelasi nivel.
Trebuie menționat cã mai existã si alte definitii ale arborilor B dar care diferã de aceasta în mod neesențial. Existã anumiti arbori B care sunt deja consacrați din punct de vedere al ordinului lor. Acesta este cazul arborelui de ordin 4, numit si arbore 2-3-4, precum și al arborelui de ordin 3 cunoscut și sub denumirea de arbore2-3. În cele ce urmeazã vom utiliza un arbore 2-3
Arbori B – exemplu
În figura este prezentat un arbore 2-3. În nodurile interne sunt memorați pointerii la subarborii corespunzãtori, precum și cheile minime din acesti subarbori. Liniuțele din noduri reprezintã absența celui de al treilea subarbore. Frunzele sunt reprezentate prin dreptunghiuri și conțin informația efectivã. Asa cum se poate observa, cheile din frunze sunt ordonate.
Proprietați
În arborii B informația este memoratã în frunze.
Nodurile interne conțin pointerii p1,p2, … , pm cãtre descendenți și valorile k1, k2, … ,km-1, reprezentând cheile cele mai mici din subarborii p1,p2, … , pm.
Pentru fiecare subarbore, cheile din p1 sunt mai mici decât cheile din p2 samd. Desigur, unii dintre acesti subarbori pot fi vizi, iar cheile ki vor fi în acest caz nedefinite.
Informația efectivã este memoratã în frunze direct sau prin pointeri la alte structuri ce o conțin. În cele de fața vom presupune prima alternativã, pentru usurința prezentãrii.
Operații de bazã asupra arborilor B
Cautarea unei chei intr-un arbore B
Inserarea unei chei intr-un arbore B
Eliminarea unei chei dintr-un arbore B
Arbori B – căutare cheie
Pentru a regãsi o cheie într-un arbore B, se porneste de la rãdãcinã și se alege o anumitã ramurã în funcție de relația în care se aflã cheia respectivã cu cheile din rãdãcinã. Procesul continuã în acelasi mod pe nivelurile urmãtoare, pânã se ajunge la o frunzã, în care se face o cãutare ordonatã.
Din descrierea strategiei de cãutare, ne așteptãm ca durata operației de cãutare sã fie proporționalã cu înãlțimea arborelui. Într-adevãr, înãlțimea unui arbore B de ordin m este , iar operația de selecție a ramurii pe care trebuie sã continue cãutarea dureazã O(log m) (în cazul cãutãrii binare). Deci în cazul cel mai defavorabil, cãutarea unei chei într-un arbore B dureazã
Arbori B – inserarea unei chei
Pentru a adãuga o cheie inexistentã într-un arbore B, facem o cãutare în arbore pentru a gãsi frunza în care cheia trebuie inseratã si dacã putem o inserãm. Ce înseamnã dacã putem? O frunzã nu poate conține mai mult de m chei. Dacã numãrul de chei din frunza în care trebuie adãugatã cheia este mai mic decât m, atunci cheia poate fi inseratã. Acesta este cazul din figura 1. în care este ilustratã inserararea cheii 28.
Fig.1. Inserarea într-un nod care nu este ocupat complet
Dar dacã dorim sã inserãm cheia 2. Urmând algoritmul anterior descris, inserarea cheii 2 ar trebui fãcutã în prima frunzã din stânga, care deja conține numãrul maxim de chei. Soluția acestei probleme constã în divizarea frunzei respective în douã frunze având câte douã chei fiecare si actualizarea informației din nodul pãrinte, asa numită EXPLOZIE, dupa cum este prezentat în figura urmãtoare.
Fig.2. Inserarea unei chei cu divizarea nodului
Ce se întâmplã însã dacã nodul pãrinte conține deja numãrul maxim de descendenți? De exemplu, dacã în arborele din figura 2. dorim sã inserãm cheia 90. Aceasta ar trebui inseratã în cea mai din dreapta frunzã. Cum aceastã frunzã conține deja numãrul maxim de chei, ea va trebui divizatã, iar nodul pãrinte ar trebui sã primeascã un nou fiu, ceea ce nu este posibil, pentru cã are deja numãrul maxim admisibil de subarbori. Asa cum se observã problema s-a mutat un nivel mai sus. Este logic ca si cu soluția sã se întâmple acelasi lucru. Intrebarea este, desigur, pânã când. Rãspunsul este de data aceasta imediat, respectiv pânã se ajunge la rãdãcinã, iar efectul este crearea unui nou nod rãdãcinã.
Soluția inserãrii cheii 90 în arborele din figura 2. este prezentatã în figura 3.
Fig.3. Divizarea nodului tatã
Dacã în acest din urmã arbore dorim sã inserãm cheia 29, explozia nodurilor se va propaga pânã la rãdãcinã, obținându-se arborele urmãtor:
Fig. 4. Propagarea fenomelui de explozie a nodurilor pã/nã la rãdãcinã
Trebuie remarcat cã atunci când este introdusã o cheie în arbore, singurele schimbãri ale nodurilor interne care pot apare sunt de a lungul cãii de acces. Aceasta înseamnã cã schimbãrile pot fi fãcute în timp proporțional cu lungimea cãii.
În general, în cazul arborilor de ordin m, atunci când se insereazã o cheie, problemele apar doar dacã aceasta trebuie inseratã într-un nod care are deja m chei. În acest caz numãrul de chei din nod devine m+1 , caz în care nodul respectiv este divizat în douã noduri având (m+1)/2 respectiv (m+1)/2 chei fiecare. Așa cum am arãtat deja, nodul pãrinte primește un nou fiu si trebuie verificat dacã nu este depãșit numãrul maxim admisibil de subarbori m, caz în care procesul de spargere a nodurilor continuã, pâna când se ajunge la un nod care poate accepta un nou fiu sau se creeazã o nouã rãdãcinã.
Înãltimea unui arbore B de grad m este cel mult . Pentru fiecare nod din cale, operația de determinare a cãii ce trebuie urmatã (utilizând cãutarea binarã) dureazã O(log m) . Operația de inserare a cheii în frunzã poate necesita O(m) . Deci în cazul cel mai defavorabil inserarea unei chei într-un arbore B poate dura
Arbori B – eliminare cheie
Pentru a elimina o cheie dintr-un arbore B, ea trebuie localizatã si apoi eliminatã. Dar dacã nodul conține deja numãrul minim de chei , în cazul nostru 2, eliminarea cheii respective va duce la un nod degenerat. Soluția constã în IMPLOZIE crearea unui singur nod format din nodul degenerat si fratele sãu, cu actualizarea informației din nodul pãrinte (dacã numãrul de chei din nodul nou format nu depãseste numãrul maxim admisibil de chei, în caz contrar se realizeazã de fapt o redistribuire a cheilor între cei doi frați). Însã nodul pãrinte pierde la rândul sãu un fiu, putând deveni un nod degenerat. Deci aceastã strategie trebuie propagatã în sus pânã se ajunge la un nod care nu degenereazã sau se ajunge la o rãdãcinã degeneratã care va fi eliminatã, arborele devenind mai mic cu un nivel.
Analiza de complexitate este identicã cu cea fãcutã în cazul operației de inserare, deci în cazul cel mai defavorabil complexitatea operației de eliminare este
Arbori B – utilizare
Arborii B au fost proiectați pentru a permite accesul la informația stocatã pe disc sau pe alte dispozitive de memorare auxiliare cu acces direct, într-un timp cât mai scurt. Este cunoscut faptul cã accesul informației memorate pe disc este cu câteva ordine de mãrime mai lent decât orice operatie realizatã în memoria principalã. Dacã utilizãm un arbore B de ordin m (memorat pe disc), pentru a regãsi informația pe disc, atunci numãrul de accese la disc va fi . Desi pentru fiecare acces la disc se consumã un timp proporțional cu O(log m) pentru a selecta ramura de urmat, acesta este nesemnificativ fațã de timpul necesar citirii / scrierii unui bloc de memorie. Chiar operația de actualizare a informației dintr-un nod, a cãrei complexitate este O(m), este si ea nesemnificativã fațã de operațiile de citire / scriere. Valoarea lui m este în general aleasã astfel încât sã fie valoarea maximã ce permite unui nod intern sã încapã într-un bloc de pe disc si este în mod tipic cuprinsã între 32<=m<=256 . Numãrul maxim de elemente care sunt memorate într-o frunzã este ales astfel încât si aceasta sã încapã într-un bloc pe disc. Aceasta înseamnã cã o informație poate fi regãsitã prin doar câteva accese la disc, ținând cont cã în general un arbore B are înãlțimea 2 sau 3, iar rãdãcina, eventual chiar primul nivel pot fi pãstrate în memoria principalã.
O analiza a gradului de umplere sugereazã cã arborele va fi plin în procent de ln2=69%. O utilizare mai bunã a spațiului poate fi obținutã dacã în loc de a diviza nodurile care depãșesc gradul de umplere, este cãutat un frate care poate primi un nod suplimentar, actualizând desigur informația corespunzãtoare.
4.4. Arbori B – probleme/exerciții/exemple C++
Arborii B sunt arbori de căutare (structuri de tip dicționar) al căror scop este de a minimiza numărul de noduri accesate în cadrul unei operații și nu timpul de execuție. Aceștia sunt utilizați pentru stocarea datelor pe medii de stocare secundare, cum sunt discurile magnetice folosite in calculatoare. Deoarece o citire sau o scriere de pe/pe disc este cu câteva ordine de mărime mai lentă decât o operație a microprocesorului, impactul cel mai mare asupra performanței este dat de numărul acceselor la datele de pe disc.
Arborii B sunt o extindere a arborilor binari de căutare prin faptul că în fiecare nod se pot afla mai multe chei și fiecare nod poate avea mai mulți fii. Consecințele acestor completări sunt mărirea spațiului ocupat de un nod în memorie și scăderea înălțimii arborelui (mai multe chei într-un nod înseamnă mai puține noduri, adică un arbore de înălțime mai mică).
Fiecare arbore B are un parametru T ≥ 2 numit gradul minim al arborelui. Fiecare nod în afară de rădăcină și de frunze trebuie să aibă minim T fii și maxim 2*T fii. De asemenea, dacă un nod are N fii atunci în nod sunt stocate N-1 chei sortate crescător; fiecare fiu al unui nod corespunde unui subarbore cu valori situate între 2 chei consecutive ale arborelui (sau mai mici decât cheia minimă sau mai mari decât cheia maximă). Frunzele sunt supuse restricției numărului de chei: fiecare frunză trebuie să aibă minim T-1 chei și maxim 2*T-1 chei. Notând prin x.ci cheia cu numărul i din nodul x și prin x.fi al i-lea fiu al lui x, putem scrie relația între chei astfel:
O proprietate importantă a arborelui este că toate frunzele trebuie să aibă aceeași adâncime. Operațiile pe care le vom implementa păstrează această proprietate.
Arborii pentru care T=2 se numesc arbori 2-3-4. Aceștia nu sunt utilizați în practică, dar se poate demonstra ușor că există o echivalență între arborii roșu-negru și arborii 2-3-4 (orice arbore roșu-negru are un arbore 2-3-4 echivalent cu aceleași chei și invers). Un exemplu de arbore 2-3-4 este prezentat încontinuare:
Implementarea operațiilor
Find
Operația Find(x,val) se implementează în mod similar cu căutarea de la BST. Parcurgem nodurile de la rădăcină spre frunze; dacă valoarea căutată se află în setul cheilor din nod, căutarea s-a terminat cu succes. Altfel, datorită proprietăților arborelui, există un singur fiu al nodului în care se poate afla cheia.
int Find( Nod *x, int val )
{
if( x == NULL )
return 0;
int i = 0;
while( i < (x->n – 1) && x->c[i] < val )
i++;
if( i < (x->n – 1) && x->c[i] == val )
return 1;
/* cauta in fiu */
return Find( x->f[i], val );
}
Am implementat căutarea lui val în lista de chei folosind un algoritm liniar de căutare; timpul de execuție al funcției poate fi îmbunătățit căutând binar valoarea.
Insert
Operația Insert(x,val) este mai complicată, deoarece trebuie să asigure păstrarea restricțiilor asupra numărului de chei dintr-un nod dupa inserarea unei valori. Operația se efectuează în doi pași: inserarea valorii cu un algoritm similar celui de la BST și apoi “tăierea” tuturor nodurilor care au prea multe chei (după inserarea unei singure valori, un nod poate avea 2*T chei; după efectuarea unei operații de ajustare, alt nod poate sa capete 2*T chei). Există 2 variante de implementare a funcției de inserare, în funcție de ordinea aplicării celor doi pași. În continuare, vom studia o implementare în care întâi "tăiem" nodurile cu prea mulți fii, apoi efectuăm inserarea.
Split
Definim in continuare operația ajutătoare Split(x,i) care primește un nod x din arborele și indicele unui fiu i al său și verifică dacă fiul respectiv are la rândul său 2*T-1 chei (vom numi un astfel de fiu plin). Dacă fiul y este plin, vom nota cu S cheia mediană din fiu (cheia cu indicele T-1, astfel încât în nod să existe T-1 chei mai mici și T-1 chei mai mari), îl înlocuim pe y cu 2 fii cu câte T-1 chei, primul conținând toate cheile mai mici decât S iar al doilea toate cheile mai mari decât S. Inserăm în x cheia S și actualizăm și lista fiilor să indice spre nodurile nou create. De exemplu, aplicarea operației Split(R,2) pe arborele de mai sus, unde R este rădăcina arborelui, produce arborele:
Aplicând apoi Split(X,1) obținem:
void Split(Nod * x, int i)
{
Nod *y = x->f[i];
if (y->n < 2 * T)
return;
Nod *z = allocNode();
z->n = y->n = T;
/* copiem cheile si fiii din y in z */
for (j = 0; j < T – 1; j++) {
z->c[j] = y->c[T + j];
z->f[j] = y->f[T + j];
}
z->f[T – 1] = y->f[2 * T – 1]; /* adaugam ultimul fiu */
/* facem loc in nodul parinte pentru noul fiu si noua cheie */
x->n++;
for (j = x->n – 1; j > i + 1; j–)
x->f[j] = x->f[j – 1];
for (j = x->n – 2; j > i; j–)
x->c[j] = x->c[j – 1];
/* adaugam cheia si fiul in parinte */
x->c[i] = y->c[T – 1]; /* mediana dintr-un nod e pe pozitia T-1 */
x->f[i + 1] = z;
}
Utilizarea split in insert
Folosind operația auxiliară descrisă mai sus, operația de adăugare a unui element efectuează "tăieri" pentru a asigura că nodul în care încercăm să inserăm nu este plin. Apare aici un caz particular: dacă rădăcina are 2*T fii, creăm o nouă rădăcină care să aibă ca unic fiu vechea rădăcină, apoi apelăm funcția Split pe noua rădăcină.
Void Insert(Nod ** rad, int val)
{
if ((*rad)->n == 2 * T) {
Nod *x = allocNode();
x->n = 1;
x->f[0] = *rad;
*rad = x;
Split(x, 0);
}
InsertRecursive(*rad, val);
}
void InsertRecursive(Nod * x, int val)
{
/* cauta pozitia valorii in nod */
i = 0;
while (i < (x->n – 1) && x->c[i] < val)
i++;
if (i < (x->n – 1) && x->c[i] == val)
return; /* cheia data exista deja */
if (x->f[i] == NULL) {
/* nodul e frunza, inseram cheia aici */
x->n++;
for (j = x->n – 2; j > i; j–)
x->c[j] = x->c[j – 1];
x->c[i] = val;
return;
}
Split(x, i);
if (i == (x->n – 1) || val < x->c[i])
InsertRecursive(x->f[i], val);
else
InsertRecursive(x->f[i + 1], val);
}
Enunțuri probleme cu arbori
1. Un arbore B* de ordin m este un arbore B pentru care fiecare nod interior are între 2m/3 si m descendenti. Sã se descrie o metodã de inserare a unei chei într-un arbore B*.
2. Sã se scrie o funcție de traversare a unui arbore B memorat prin legãturi cãtre primul fiu, si lista fraților. Care este complexitatea ei?
5.Căutarea cu dispersie (hashing)
5.1. Funcția hash
În sens matematic, funcțiile hash (clasă de funcții denumite în lucrări de specialitate și funcții de dispersie sau funcții de rezumat) sunt funcții definite pe o mulțime cu multe elemente (posibil infinită) cu valori într-o mulțime cu un număr fix și mai redus de elemente. Funcțiile hash nu sunt inversabile.[1] În informatică, funcțiile hash sunt folosite pentru a accelera căutările în tabele, cum este cazul în bazele de date mari sau comparările de date. Valoarea unei funcții hash este denumită rezumat, valoare hash, cod hash, sumă hashsau doar hash. De asemenea, pot fi folosite drept sume de control sau coduri corectoare de erori (deși nu trebuie confundate cu acestea două), sau, în criptografie, drept componente în schemele de semnătură digitală.
O funcție hash poate lega două sau mai multe chei de la aceeași valoare hash. În multe aplicații, este de dorit minimalizarea șansei apariției unor astfel de coliziuni, ceea ce înseamnă că funcția hash trebuie să lege cheile de valorile hash cât mai uniform posibil. De asemenea, în funcție de aplicație, alte proprietăți pot fi necesare. Deși ideea a fost concepută în anii 1950, proiectarea optimă a funcțiilor hash este încă un subiect activ de cercetare și discuție. Funcțiile hash sunt utilizate și ca sume de control sau funcții hash criptografice, dar nu trebuie confundate cu caracterele de verificare, amprentele numerice, funcțiile de randomizare, codurile de corectare a erorilor. Deși aceste concepte se suprapun într-o oarecare măsură, fiecare are propriile sale utilizări și cerințele și este proiectat și optimizat în mod diferit.
5.2. Tabele hash
În multe aplicații lucrăm cu structuri mari de date în care avem nevoie să facem căutări, inserări, modificări și ștergeri. Aceste structuri pot fi vectori, matrice, liste etc. În cazurile mai fericite ale vectorilor, aceștia pot fi sortați, caz în care localizarea unui element se face prin metoda înjumătățirii intervalului, adică în timp logaritmic. Chiar dacă nu avem voie să sortăm vectorul, tot se pot face anumite optimizări care reduc foarte mult timpul de căutare. De exemplu, probabil că mulți dintre cititori au idee despre ce înseamnă indexarea unei baze de date. Dacă avem o bază de date cu patru elemente de tip string, și anume
B = ("bac", "zugrav", "abac", "zarva")
putem construi un vector Ind care să ne indice ordinea în care s-ar cuveni să fie așezate cuvintele în vectorul sortat. Ordinea alfabetică (din cartea de telefon) a cuvintelor este: "abac", "bac", "zarva", "zugrav", deci vectorul Ind este:
Ind = (3, 1, 4, 2)
semnificând ca primul cuvaât din vectorul sortat ar trebui să fie al treilea din vectorul B, respectiv "abac", și așa mai departe. În felul acesta am obținut un vector sortat, care presupune o indirectare a elementelor. Vectorul sortat este
B' = (B(Ind(1)), B(Ind(2)), B(Ind(3)), B(Ind(4)).
Aceasta operație se numește indexare. Ce-i drept, construcția vectorului Ind nu se poate face într-un timp mai bun decat O(N log N), dar după ce acest lucru se face (o singură dată, la începutul programului), căutarile se pot face foarte repede. Dacă pe parcurs se fac adaugări sau ștergeri de elemente în/din baza de date, se va pierde câtva timp pentru menținerea indexului, dar în practică timpul acesta este mult mai mic decât timpul care s-ar pierde cu căutarea unor elemente în cazul în care vectorul ar fi neindexat. Nu vom intra în detalii despre indexare, deoarece nu acesta este obiectul articolului de față.
În unele situații nu se poate face nici indexarea structurii de date. Să considerăm cazul unui program care joacă sah. Numărul de poziții posibile ale pieselor pe tabla de sah este mult prea mare. Nu poate fi vorba nici măcar de reținerea tuturor, cu atât mai puțin de indexarea lor. În esența, modul de funcționare al acestui program se reduce la o rutină care primește o poziție pe tablă și o variabilă care indică dacă la mutare este albul sau negrul, rutina întorcând cea mai bună mutare care se poate efectua din acea poziție. Majoritatea programelor de șah încep să expandeze respectiva poziție, examinând tot felul de variante ce pot decurge din ea și alegând-o pe cea mai promițătoare, așa cum fac și jucătorii umani. Pozițiile analizate, fiind mult mai puține decât cele posibile, sunt stocate în memorie sub forma unei liste.
Să ne închipuim acum următoarea situație. Este posibil ca, prin expandarea unei configurații inițiale a tablei să se ajungă la aceeași configurație finală pe două căi diferite. Spre exemplu, dacă albul mută întâi calul la f3, apoi nebunul la c4, poziția rezultată va fi aceeași ca și când s-ar fi mutat întâi nebunul și apoi calul (considerând bineînțeles că negrul dă în ambele situații aceeași replică). Dacă configurația finală a fost deja analizată pentru prima variantă, este inutil să o mai analizăm și pentru cea de-a doua, pentru ca rezultatul (concluzia la care se va ajunge) va fi exact acelașii. Dar cum iși poate da programul seama dacă poziția pe care are de gând s-o analizeze a fost analizată deja sau nu?
Cea mai simplă metodă este o scanare a listei de configurații examinate din memorie. Dacă în aceasta listă se află poziția curentă de analizat, înseamnă că ea a fost deja analizată și vom renunța la ea. Dacă nu, o vom analiza acum. Ideea în mare a algoritmului este:
01.funcția Analizează(Poziție P)
02.caută P în lista de poziții deja analizate
03.dacă P nu există în listă
04.expandează P și află cea mai bună mutare M
05.adaugă P la lista de poziții analizate
06.întoarce M
07.altfel
08.întoarce valoarea M atașata poziției P găsite în listă
09.sfârșit
Nu vom insista asupra a cum se expandează o poziție și cum se calculează efectiv cea mai bună mutare. Noi ne vom interesa de un singur aspect, și anume căutarea unei poziții în listă. Tehnica cea mai "naturală" este o parcurgere a listei de la cap la coadă, comparând pe rând poziția căutată cu fiecare poziție din listă. Dacă lista are memorate N poziții, atunci în cazul unei căutari cu succes (poziția este găsită), numărul mediu de comparații făcute este N/2, iar numărul cel mai defavorabil ajunge până la N. În cazul unei căutări fără succes (poziția nu există în listă), numărul de comparații este întotdeauna N. De altfel, cazul căutării fără succes este mult mai frecvent pentru problema jocului de șah, unde numărul de poziții posibile crește exponențial cu numărul de mutări. Același număr de comparații îl presupune și ștergerea unei poziții din listă (care presupune întâi găsirea ei) și adăugarea (care presupune ca poziția de adăugat să nu existe deja în listă).
Pentru îmbunătățirea practică a acestui timp sunt folosite tabelele de dispersie sau tabelele hash (engl. hash = a toca, tocatura). Menționăm de la bun început că tabelele hash nu au nicio utilitate din punct de vedere teoretic. Dacă suntem rău intenționați, este posibil să găsim exemple pentru care căutarea într-o tabelă hash să dureze la fel de mult ca intr-o listă simplu înlantuită, respectiv O(N). Dar în practică timpul căutării și al adăugării de elemente într-o tabelă hash coboară uneori până la O(1), iar în medie scade foarte mult (de mii de ori).
5.3. Aplicații
Descrierea structurii de date
Să presupunem pentru început că în loc de poziții pe tabla de șah, lista noastră memorează numere între 0 și 999. În acest caz, tabela hash ar fi un simplu vector H cu 1000 de elemente booleene. Inițial, toate elementele lui H au valoarea False (sau 0). Dacă numărul 473 a fost găsit în listă, nu avem decât să setăm valoarea lui H(473) la True (sau 1). La o nouă apariție a lui 473 în listă, vom examina elementul H(473) și, deoarece el este True, înseamnă că acest număr a mai fost găsit. Dacă dorim ștergerea unui element din hash, vom reseta poziția corespunzătoare din H. Practic, avem de-a face cu un exemplu rudimentar de ceea ce se cheamă funcție de dispersie, adică h(x) = x. O proprietate foarte importantă a acestei funcții este injectivitatea; este imposibil ca la două numere distincte să corespundă aceeași intrare în tabelă. Să încercăm o reprezentare grafică a metodei:
Iată primul set de funcții de gestionare a unui hash.
01.const int M = 1000;
02.typedef int DataType;
03.typedef DataType Hash[M];
04.Hash H;
05.
06.void InitHash1(Hash H) {
07.for (int i = 0; i < M; H[i++] = 0);
08.}
09.
10.inline int h(DataType K) {
11.return K;
12.}
13.
14.int Search1(Hash H, DataType K) {
15.// Întoarce -1 dacă elementul nu există în hash
16.// sau indicele în hash dacă el există
17.return H[h(K)] ? h(K) : -1;
18.}
19.
20.void Add1(Hash H, DataType K) {
21.H[h(K)] = 1;
22.}
23.
24.void Delete1(Hash H, DataType K) {
25.H[h(K)] = 0;
26.}
Prin "număr de intrări" în tabelă se înțelege numărul de elemente ale vectorului H; în general, orice tabelă hash este un vector. Pentru ca funcțiile să fie cât mai generale, am dat tipului de date int un nou nume DataType. În principiu, tabelele hash se aplică oricărui tip de date. În realitate, fenomenul este tocmai cel invers: orice tip de date trebuie "convertit" printr-o metodă sau alta la tipul de date int, iar funcția de dispersie primește ca parametru un întreg. Funcțiile hash prezentate în viitor nu vor mai lucra decât cu variabile de tip întreg. Vom vorbi mai târziu despre cum se poate face conversia. Acum să generalizăm exemplul de mai sus.
Intr-adevăr, cazul anterior este mult prea simplu. Să ne închipuim de pildă că în loc de numere mai mici ca 1.000, avem numere de pana la 2.000.000.000. În această situație posibilitatea de a reprezenta tabela ca un vector caracteristic iese din discuție. Numărul de intrări în tabela este de ordinul miilor, cel mult al zecilor de mii, deci cu mult mai mic decat numărul total de chei (numere) posibile. Ce avem de făcut? Am putea încerca să adăugăm un număr K într-o tabelă cu M intrări (numerotate de la 0 la M-1) pe poziția K mod M, adică h(K) = K mod M. Care va fi însă rezultatul? Funcția h își va pierde proprietatea de injectivitate, deoarece mai multor chei le poate corespunde aceeași intrare în tabelă, cum ar fi cazul numerelor 1.234 si 2.001.234, ambele daâd același rest la împărțirea prin M = 1.000. Nu putem avea însă speranța de a găsi o funcție injectivă, pentru că atunci numărul de intrări în tabelă ar trebui să fie cel puțin egal cu numărul de chei distincte. Vrând-nevrând, trebuie să rezolvăm coliziunile (sau conflictele) care apar, adică situațiile când mai multe chei distincte sunt repartizate la aceeași intrare.
Vom reveni ulterior la oportunitatea alegerii funcției modul și a numărului de 1.000 de intrări în tabelă. Deocamdată vom folosi aceste date pentru a explica modul de funcționare a tabelei hash pentru funcții neinjective. Să presupunem că avem două chei K1 si K2 care sunt repartizate de funcția h la aceeași intrare X, adicah(K1) = h(K2) = X. Soluția cea mai comodă este că H(X) să nu mai fie un număr, ci o listă liniară simplu înlanțuită care să conțină toate cheile găsite până acum și repartizate la aceeași intrare X. Prin urmare vectorul H va fi un vector de liste:
Să analizăm acum complexitatea noilor funcții de căutare, adăugare și ștergere. Căutarea nu se va mai face în toată lista, ci numai în lista corespunzatoare din H. Altfel spus, o cheie K se va căuta numai în lista H(h(K)), deoarece dacă cheia K a mai apărut, ea a fost în mod sigur repartizată la intrarea H(h(K)). De aceea, căutarea poate ajunge, în cazul cel mai defavorabil când toate cheile din listă se repartizează la aceeași intrare în hash, la o complexitate O(N). Dacă reușim însă să gasim o funcție care să distribuie cheile cât mai aleator, timpul de intrare se va reduce de M ori. Avantajele sunt indiscutabile pentru M = 10.000 de exemplu.
Întrucât operațiile cu liste liniare sunt în general cunoscute, nu vom insista asupra lor. Prezentăm aici numai adăugarea și căutarea.
01.#include <stdio.h>
02.#include <stdlib.h>
03.
04.const int M = 1000;
05.typedef struct List_ {
06.long P;
07.struct List_ *Next;
08.} List;
09.typedef List* Hash[M];
10.Hash H;
11.
12.void InitHash2(Hash H){
13.for (int i = 0; i < M; H[i++] = NULL);
14.}
15.
16.int h2(int K) {
17.return K % M;
18.}
19.
20.int Search2(Hash H, int K) {
21.// Întoarce 0 dacă elementul nu există in hash
22.// sau 1 dacă el există
23.List *L;
24.for (L = H[h2(K)]; L && (L->P != K); L = L->Next);
25.return L != NULL;
26.}
27.
28.void Add2(Hash H, int K) {
29.List *L = (List *) malloc(sizeof(List));
30.L->P = K;
31.L->Next = H[h2(K)];
32.H[h2(K)] = L;
33.}
Am spus că funcțiile de dispersie sunt concepute să lucreze numai pe date de tip întreg; celelalte tipuri de date trebuie convertite în prealabil la tipuri de date întregi. Iată câteva exemple:
Variabilele de tip string pot fi transformate în numere în baza 256 prin înlocuirea fiecărui caracter cu codul sau ASCII. De exemplu, șirul "abac" poate fi privit ca un număr de 4 cifre în baza 256, și anume numărul (97 98 97 99). Conversia lui în baza 10 se face astfel:
X = ((97 * 256 + 98) * 256 + 97) * 256 + 99 = 1.633.837.411
Pentru stringuri mai lungi, rezultă numere mai mari. Uneori, ele nici nu mai pot fi reprezentate cu tipurile de date ordinare. Totuși, acest dezavantaj nu este supărător, deoarece majoritatea funcțiilor de dispersie presupun o împărțire cu rest, care, indiferent de mărimea numărului de la intrare, produce un număr controlabil.
Variabilele de tip dată se pot converti la întreg prin formula:
X = A * 366 + L * 31 + Z
unde A, L si Z sunt respectiv anul, luna si ziua datei considerate. De fapt, această funcție aproximează numărul de zile scurse de la începutul secolului I. Ea nu are pretenții de exactitate (ca dovadă, toți anii sunt considerați a fi bisecți și toate lunile a avea 31 de zile), deoarece s-ar consuma timp inutil cu calcule mai sofisticate, fără ca dispersia însăși să fie îmbunătățită cu ceva. Condiția care trebuie neapărat respectată este ca funcția de conversie dată întreg să fie injectivă, adică să nu se întample ca la două date D1 si D2 să li se atașeze acelașii întreg X; dacă acest lucru se întamplă, pot apărea erori la căutarea în tabela (de exemplu, se poate raporta găsirea datei D1 când de fapt a fost găsită data D2). Pentru a respecta injectivitatea, s-au considerat coeficienții 366 și 31 în loc de 365 și 30. Dacă numărul de zile scurse de la 1 ianuarie anul 1 d.H. ar fi fost calculat cu exactitate, funcția de conversie ar fi fost și surjectivă, dar, după cum am mai spus, acest fapt nu prezintă interes.
Analog, variabilele de tip oră se pot converti la întreg cu formula:
X = (H * 60 + M) * 60 + S
unde H, M si S sunt respectiv ora, minutul și secunda considerate, sau cu formula
X = ((H * 60 + M) * 60 + S) * 100
dacă se ține cont și de sutimile de secundă. De data aceasta, funcția este surjectivă (oricărui număr întreg din întervalul 0 – 8.639.999 îi corespunde în mod unic o oră).
În majoritatea cazurilor, datele sunt structuri care conțin numere și stringuri. O bună metodă de conversie constă în alipirea tuturor acestor date și în convertirea la baza 256. Caracterele se convertesc prin simplă înlocuire cu codul ASCII corespunzător, iar numerele prin convertirea în baza 2 și tăierea în "bucăți" de câte opt biți. Rezultă numere cu multe cifre (prea multe chiar și pentru tipul long long), care sunt supuse unei operații de împarțire cu rest. Funcția de conversie trebuie să fie injectivă. De exemplu, în cazul tablei de șah despre care am amintit mai înainte, ea poate fi transformată intr-un vector cu 64 de cifre în baza 16, cifra 0 semnificând un pătrat gol, cifrele 1-6 semnificând piesele albe (pion, cal, nebun, turn, regină, rege), iar cifrele 7-12 semnificând piesele negre. Prin trecerea acestui vector în baza 256, rezultă un număr cu 32 de cifre. La acesta se mai pot adăuga alte cifre, respectiv partea la mutare ($0$ pentru alb, 1 pentru negru), posibilitatea de a efectua rocada mica/mare de către alb/negru, numărul de mutări scurse de la începutul partidei și așa mai departe.
Vom termina prin a prezenta două funcții de dispersie foarte des folosite.
Metoda împărțirii cu rest
Funcția hash este: h(x) = x mod M unde M este numărul de intrări în tabelă. Problema care se pune este să-l alegem pe Mcat mai bine, astfel încat numărul de coliziuni pentru oricare din intrări să fie cât mai mic. De asemenea, trebuie ca M să fie cât mai mare, pentru ca media numărului de chei repartizate la aceeași intrare să fie cât mai mică. Totuși, experiența arată că nu orice valoare a lui M este bună.
De exemplu, la prima vedere s-ar putea spune că o bună valoare pentru M este o putere a lui 2, cum ar fi 1024, pentru ca operația de împarțire cu rest se poate face foarte ușor în această situație. Totuși, funcția h(x) = x mod 1024 are un mare defect: ea nu ține cont decât de ultimii 10 biți ai numărului x. Dacă datele de intrare sunt numere în mare majoritate pare, ele vor fi repartizate în aceeași proporție la intrările cu număr ,de ordine par, pentru că funcția h păstrează paritatea. Din aceleași motive, alegerea unei valori ca 1000 sau 2000 nu este prea inspirată, deoarece ține cont numai de ultimele 3-4 cifre ale reprezentării zecimale. Multe valori pot da același rest la împărțirea prin 1000. De exemplu, dacă datele de intrare sunt anii de naștere ai unor persoane dintr-o agendă telefonică, iar funcția h(x) = x mod 1000, atunci majoritatea cheilor se vor îngrămădi (termenul este sugestiv) între intrările 920 și 990, restul rămânând nefolosite.
Practic, trebuie ca M să nu fie un număr rotund în nicio bază aritmetică, sau cel puțin nu în bazele 2 și 10. O bună alegere pentru M sunt numerele prime care să nu fie apropiate de nicio putere a lui 2. De exemplu, în locul unei tabele cu M = 10.000 de intrări, care s-ar comporta dezastruos, putem folosi una cu 9973 de intrări. Chiar și această alegere poate fi îmbunătățită; între puterile lui 2 vecine, respectiv 8192 și 16384, se poate alege un număr prim din zona 11.000 – 12.000. Risipa de memorie de circa 1.000 – 2.000 de intrări în tabela va fi pe deplin compensată de îmbunătățirea căutării.
Metoda înmulțirii
Pentru această metodă funcția hash este h(x) = [M * {x*A}]. Aici A este un număr pozitiv subunitar, 0 < A < 1, iar prin {x*A} se ințelege partea fracționară a luix*A, adică x*A – [x*A]. De exemplu, dacă alegem M = 1234 si A = 0.3, iar x = 1997, atunci avem h(x) = [1234 * {599.1}] = [1234 * 0.1] = 123. Se observă că funcția h produce numere între 0 și M-1. Într-adevăr 0 ≤ {x*A} < 1 0 ≤ M * {x*A} < M.
În acest caz, valoarea lui M nu mai are o mare importanță. O putem deci alege cât de mare ne convine, eventual o putere a lui 2. În practică, s-a observat că dispersia este mai bună pentru unele valori ale lui A și mai proastă pentru altele. Donald Knuth propune valoarea .
Ca o ultimă precizare necesară la acest articol, menționăm că funcția de căutare e bine să nu întoarcă pur și simplu 0 sau 1, după cum cheia căutată a mai apărut sau nu înainte între datele de intrare. E recomandabil ca funcția să întoarcă un pointer la zona de memorie în care se află prima apariție a cheii căutate. Vom da acum un exemplu în care această valoare returnată este utilă. Dacă, în cazul prezentat mai sus al unui program de șah, se ajunge la o anumită poziție P după ce albul a pierdut dreptul de a face rocada, această poziție va fi reținută în hash. Reținerea nu se va face nicidecum efectiv (toată tabla), pentru că s-ar ocupa foarte multă memorie. Se va memora în loc numai un pointer la poziția respectivă din lista de poziții analizate. Pe lângă economia de memorie în cazul cheilor de mari dimensiuni, mai există și alt avantaj. Să ne închipuim că, analizând în continuare tabla, programul va ajunge la aceeași poziție P, dar în care albul are încă dreptul de a face rocada. E limpede că această variantă este mai promițătoare decât precedentă, deoarece albul are o libertate mai mare de mișcare. Se impune deci fie ștergerea vechii poziții P din listă și adăugarea noii poziții, fie modificarea celei vechi prin setarea unei variabile suplimentare care indică dreptul albului de a face rocada. Această modificare este ușor de făcut, întrucât căutarea în hash va returna chiar un pointer la poziția care trebuie modificată. Bineînțeles, în cazul în care poziția căutată nu se află în hash, funcția de căutare trebuie să întoarcă NULL.
Vom prezenta un exemplu de funcție de dispersie pentru cazul tablei de șah.
01.const int M = 9973; // Numărul de "intrări".
02.typedef struct {
03.// Tabla de joc, cu 0 <= T[i][j] <= 12.
04.char b_T[8][8];
05.
06.// Ultimii doi biti ai lui b_CastleW indica daca albul are dreptul de a
07.// efectua rocada mare, respectiv pe cea mica. Analog pentru b_CastleB.
08.char b_CastleW, b_CastleB;
09.
10.// 0 sau 1, dupa cum la mutare este albul sau negrul.
11.char b_Side;
12.
13.
14.// 0..8, indicand coloana (0..7) pe care partea la mutare poate efectua o
15.// captura "en passant". 8 indică că nu există această posibilitate.
16.char b_EP;
17.
18.// Numarul de mutari efectuate.
19.int b_NMoves;
20.} Board;
21.Board B;
22.
23.int h3(Board *B) {
24.int i, j;
25.
26.// Valoarea inițială a lui S este un număr pe 17 biți care
27.// înglobează toate variabilele suplimentare pe lângă T.
28.// S se va lua apoi modulo M.
29.long S = (B->b_NMoves // 8 biti
30.+(B->b_CastleW << 8) // 2 biti
31.+(B->b_CastleB << 10) // 2 biti
32.+(B->b_Side << 12) // 1 bit
33.+(B->b_EP << 13)) % M; // 4 biti
34.
35.for (i = 0; i <= 7; i++)
36.for (j = 0; j <= 7; j++) {
37.S = (16 * S + B->b_T[i][j]) % M;
38.}
39.
40.return S;
41.}
6. Metode de căutare în fișiere mari
6.1. Fișiere cu indecși secundari
Nu toate căutările din bazele de date se fac după cheia principală. Dacă un atribut sau un grup de atribute apar des în cereri atunci pentru acel atribut sau grup de atribute se construiește un index numit index secundar ce permite accesul rapid la înregistrările corespunzătoare valorilor date. Un fișier cu un index secundar corespunzător unui atribut sau grup de atribute F se spune că este fișier inversat în raport cu F. În indexul secundar înregistrările sunt indicate fie prin pointeri la ele fie prin valorile cheilor principale corespunzătoare lor.
Referirea la înregistrări prin pointeri are avantajul accesului mai rapid la informație dar produce constrângeri din cauza fixării înregistrărilor pe locul pe care au fost introduse sau la nivel de bloc sau la nivel de clasă. Referirea prin cheia principală asociată are dezavantajul unui acces mai lent dar nu mai fixează înregistrările.
6.2. Indicarea parțială a cheii de căutare
Dacă ne interesează înregistrările care au valorile a1,a2,…,ak pentru atributele A1,A2,…,Ak care nu constituie o cheie această revine la determinarea intersecției mulțimilor S1,S2,…,Sk unde Si este mulțimea tuturor înregistrărilor care au valoarea ai corespunzătoare atributului Ai.
O metodă utilizată în acest caz este metoda indexilor secondari multiplii. Din indexii asociați atributelor A1,A2,…,Ak se determină mulțimile de pointeri P1,P2,…,Pk ale pointerilor către înregistrările mulțimilor S1,S2,…,Sk și dacă acestea nu au prea multe elemente se face intersecția lor în memoria principală. O variantă este alegerea unui indice i pentru care mulțimea Si are cele mai puține elemente (de obicei se ia mulțimea pentru care atributul poate lua cele mai multe valori) și apoi se verifică pentru aceste elemente dacă îndeplinesc și celelalte condiții. Dacă pointerii sunt la nivel de bloc, metoda intersecției mulțimilor de pointeri poate să producă și elemente false și se fac verificări suplimentare.
A doua metodă utilizată în acest caz este o generalizare a fișierelor cu dispersie ce folosesc funcții de dispersie partiționate. În această metodă la calculul clasei unui element contribuie toate câmpurile înregistrării. Cu funcții de dispersie bine construite se poate limita numărul de clase în care se poate afla o înregistrare pentru care cunoaștem numai o parte dintre câmpuri. Aceasta se obține împărțind biții unui număr de clasă în mai multe părți componente și atribuid fiecărui atribut posibilitatea de a determina o anumită parte asociată din adresă.
Să presupunem de exemplu că numărul de clase este o putere a lui 2 și anume 2**B, deci adresa unei clase este un șir de B biti. Vom împărți cei B biți în grupe, câte o grupă pentru fiecare atribut (eventual unele grupe nu au nici-un bit). Dacă atributele sunt A1,A2,…,Ak și atributului Ai îi sunt atribuiți bi biți, determinăm clasa înregistrării (a1,a2,…,ak) calculând hi(ai) pentru i=1,…,k unde hi este o funcție de dispersie pentru atributul Ai cu valori intre 0 si 2**bi-1 iar numărul clasei înregistrării se obține prin concatenarea acestor adrese deci este șirul de B biți h1(a1)h2(a2)…hk(ak).
Pentru căutare se construiesc numere de clase cu valori fixate obținute aplicând funcția de dispersie unei valori cunoscute pentru atributele pentru care se cunosc valorile si luând toate posibilitățile pentru grupele asociate atributelor pentru care nu se cunosc valorile.
Dacă se cunosc probabilitațile cu care atributele apar într-o cerere atunci se pot stabili proprietați interesante după cum urmează.
Teorema 6.1. Dacă valorile unui atribut sunt egal probabile când se specifică o valoare pentru acest atribut, atunci se obține în medie un număr minim de clase de examinat pentru a obține răspunsul la o cerere dacă pentru anumite numere n1,n2,…,nk al căror produs este numărul de clase, adresa clasei asociate înregistrării (a1,a2,…,ak) se exprimă cu formula
hk(ak)+nk(h[k-1](a[k-1])+n[k-1](h[k-2](a[k-2])+…+n2h1(a1)…))
unde funcția de dispersie hi(ai) ia valori între 0 și ni.
O demonstrație a acestei teoreme este dată în Bolour [1979]. Din această teoremă se deduce ca alegând fiecare ni ca o putere a lui 2 putem să obținem o aproximație a unei soluții optime. Alegerea puterilor lui 2 este o altă problemă care a fost rezolvată numai în cazuri particulare. Dacă în cereri se consideră valoarea unui singur atribut atunci valorile b1,b2,…,bk se aleg după cum urmează din teoremă:
Teorema 6.2. Dacă toate cererile specifică doar câte un atribut și pi este probabilitatea ca Ai să fie atributul specificat, atunci, presupunând că nici-un bi nu este mai mic decât 0 sau mai mare ca B, numărul mediu de clase cercetate este minim dacă
bi=(B – (log p1 + log p2 +…+ log pk))/k + log pi
unde k este numărul de atribute, 2**B este numărul de clase și logaritmii sunt în baza 2.
Demonstrația acestei teoreme se face utilizând metoda multiplicatorilor lui Lagrange și poate fi gasită în Ullman [1982]. Formula din teoremă permite aflarea valorilor elementelor bi aplicând urmatoarele reguli:
– dacă un bi este mai mare decât B se face acel bi egal cu B și se fac 0
celelalte valori;
– dacă o valoare bi este negativă se elimină atributul corespunzător din
calcule și se reaplică teorema;
– se trunchiază valorile bi (luându-se partea întreagă a lor) și
eventualele unitați rămase se adaugă la valorile acelor bi care au
partea zecimală cea mai mare.
Exemplul 1. Să considerăm un fișier corespunzător entitații STUDENT având atributele MATRICOLA, NUME si DATA_NASTERE care sunt cerute cu probabilitățile 0.24, 0.75 și respectiv 0.01. Presupunem că formăm 512 clase, deci B=9 și aplicând formula din teoremă obținem bi=6.03 + log pi de unde rezultă b1=3.98, b2=5.62 si b3=-0.61. Deoarece b3 este negativ se ia b3=0 și se refac calculele numai pentru primele două câmpuri cu probabilitățile p1=0.24/(1-0.01)=0.242 și respectiv p2=0.75/(1-0.01)=0.758 de unde se obține bi=5.72+log pi rezultând b1=3.68 și b2=5.32 apoi prin trunchiere la 3 și respectiv 5 se obține disponibil o unitate care se adaugă lui b1 care are partea fractionară cea mai mare obtinând în final b1=4, b2=5 și b3=0.
Un alt caz în care se pot specifica valorile optime pentru bi este cel în care se cunosc probabilitățile cu care câmpurile sunt menționate în cereri aceste probabilități fiind independente de menționarea altor câmpuri în aceeași cerere. Formulele de calcul pentru bi sunt date de teorema următoare:
Teorema 6.3. Dacă pi este probabilitatea cu care se specifică valoarea atributului Ai într-o cerere independent de celelalte valori specificate, atunci, presupunând ca bi nu sunt negativi sau mai mari decat B, numărul mediu de clase de căutat este minim dacă se ia
bi=(B – (log q1 + log q2 +…+ log qk))/k + log qi
unde qi=pi/(1-pi), i=1,2,…,k, restul condițiilor fiind ca la teorema 6.2.
Demostrația acestei teoreme este asemănătoare cu demonstrația teoremei precedente. Algoritmul de calcul al valorilor bi, i=1,…,k este la fel ca în cazul precedent doar că în loc de pi se ia pi/(1-pi) în calcule.
Exemplul 2. Să considerăm fișierul corespunzător entității COMENZI care are atributele NUME, MARFA, CANTITATE si DATA specificate cu probabilitățile p1=0.8, p2=0.5, p3=0.01 si p4=0.2 și numărul de clase este 512, deci B=9. Făcând calculele se obține b1=5.91, b2=3.91, b3=-2.73 si b4=1.91. Cum b3 este negativ se elimină atributul CANTITATE din calcule și se face b3=0. Refăcând calculele se obține b1=5, b2=3, b3=0 și b4=1 și nu mai sunt necesare reajustări. Numărul de clase cercetate la o cerere este în acest caz de 58.3 în medie.
6.3. Cazuri speciale de căutare
În cereri pot să intervină și alte tipuri de condiții pentru determinarea unei înregistrări sau unei mulțimi de înregistrări decât cele prezentate până acum. Un astfel de caz îl constituie indicarea limitelor între care trebuie să se afle valorile corespunzătoare unor câmpuri pentru a selecționa înregistrările. Acest tip de cereri le vom numi cereri după mărime.
Pentru cererile după mărime se pot aplica metodele anterioare cu o alegere corespunzătoare a tehnicilor de lucru. De exemplu se poate adapta tehnica de dispersie partitionată alegând funcțiile de dispersie în asa fel încât elementele din clase diferite să fie în aceeași relație de ordine ca și adresele lor. Un exemplu de astfel de funcție este urmatorul. Dacă numărul de clase este M (deci adresele claselor sunt de la 0 la M-1) și valorile unui câmp sunt relativ uniform distribuite pe intervalul [a,b) se ia drept clasă pentru valoarea v numarul [(v-a)/(b-a)*M] unde prin [] am notat partea intreagă a numarului respectiv. Pentru distribuții neuniforme sau nespecificarea intervalului de variație a valorilor campurilor se pot defini alte funcții de dispersie mai bune (eventual tabelate).
O alternativa de rezolvare este si folosirea B-arborilor construind cate un B-arbore pentru fiecare atribut in parte, selecționând din ei pointeri catre inregistrarile care au valori cuprinse intre limitele precizate si apoi facând intersecția acestor mulțimi pentru a identifica toate inregistrarile care indeplinesc toate condițiile specificate.
O clasa de metode cu performanțe foarte bune în rezolvarea cererilor de cautare a unor
informații în masive mari de date este formată din metodele de indexare multidimensionale.
În acest caz înregistrările bazei de date sunt asimilate cu puncte într-un spațiu de date
multidimensional. Acesta este divizat în mod repetat. Diviziunea spațială poate fi efectuată
în raport cu valorile atributelor înregistrărilor bazei de date sau, “hiperplanele de diviziune”
ar putea fi alese independent de valorile atributelor. În acest din urmă caz, implementarea este mai simpla, dar structurile arborescente de indexare ar putea fi foarte dezechilibrate (în cazul unor înregistrări neuniform distribuite în spațiul datelor).
Similitudinea dintre tuplele unei relații si punctele unui spațiu de date multidimensional poate sta la baza multor metode de indexare spațială, multidimensională. Structurile de indexare multidimensionale pot fi utilizate în cazul unor volume de date mai mici (caz în care structura index este stocată în întregime în memoria internă) sau în cazul unor volume de date foarte mari (de data aceasta structurile sunt stocate în întregime sau numai parțial în memoria externa).
Metode de indexare în spatii multidimensionale Arborii k-d.
Aceste structuri de date sunt asemănătoare arborilor binari de căutare dar cheia de căutare este dependentă de nivelul la care se afla nodurile arborelui. Principiul de descompunere spațială care stă la baza construirii arborilor k-d este preluat de numeroase metode de indexare a informației dintr-un spațiu multidimensional. Spre exemplu în cazul codificării printr-un arbore 2-d a unei mulțimi de puncte din spațiul bidimensional (k=2) daca procesul de căutare ajunge la un nod situat pe un nivel de rang par (radacina arborelui se consideră pe nivelul 0) cheia arborelui de căutare va fi coordonată x iar în cazul unui nod situat pe un nivel de rang impar cheia de căutare în arbore va fi coordonată y.
Un nod (N) al unui arbore k-d va fi reprezentat printr-o înregistrare cu k+4 câmpuri. Un câmp conține informaăția propriu-zisa a nodului (info), un altul indică numarul (numele) coordonatei în funcție de care se face decizia de căutare în acel nod, două câmpuri conțin referințe la fiii nodului curent iar celelalte k câmpuri reprezinta coordonatele punctului asociat nodului (N). P1
P2 P3
P4 P5 P6 P7
P8 P9 P10 P11 P12 P13 P14 P15 Arborele k-d (k=2)
Convenția de plasare a punctelor în nodurile unui arbore k-d (A) este ca în subarborele stâng al unui nod arbitrar (N) al lui (A) (având câmpul de decizie cea de-a j-a coordonată a spațiului k-dimensional) sunt plasate toate punctele având valoarea celei de-a j-a coordonate strict mai mică decât aceeasi coordonată a punctului de date asociat lui (N). In subarborele drept vor fi plasate câmpurile cu coordonata a j-a mai mare sau egală decât coordonata corespunzatoare a punctului de date al nodului (N).
În reprezentarea înfațisată mai sus se consideră ca punctele colectiei sunt disjuncte. Dacă se permite ca punctele de date sa nu fie unice, fiecare nod (N) al arborelui va trebui sacontină un câmp "lista de coliziuni" în care să fie retinuțe informațiile referitoare la toatepunctele mulțimii de date care au aceleasi coordonate cu punctul asociat lui (N).
Bentley a demonstrat că în cazul inserției unui punct într-un arbore k-d cu N noduri sunt efectuate O(log2N) operații elementare (comparatii) [Bent 75]. Ca si în cazul arborilor binari de căutare forma arborelui k-d depinde de ordinea în care sunt efectuate inserările de puncte în arbore.
O soluție performantă de indexare care prezintă caracteristici comune atât cu metodele ierarhice cât și cu cele bazate pe fisiere grilă este arborele BD cunoscut si sub numele de fisier BANG (Balanced and Nested Grid File). Arborele BD este un arbore binar asemănător arborelui k-d, căruia i se aplică o tehnicĂ de comprimare a căilor. El prezintă asemanări importante si cu tehnica de cautare patriciană într-un arbore binar, fara a memora cheile în noduri. Tehnica Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) a fost elaborată de D.E. Morisson
BIBLIOGRAFIE
Ionel Jian, Liliana Jian, Baze de date , Editura MIRTON, Timisoara, 1998
Sikha Bagui,Achievements and Weaknesses of Object -Oriented Database,Journal of Object Technology, Vol.2, Nr.4,Iulie-August 2003
Henderson, K. "Proceduri stocate în SQL Server. XML, HTML", Teora 2003
Peterson J. "Baze de date pentru începători", Ed. All, 2003
Popa Gh. și alții "Baze de date ACCESS", Ed. Cison, 2003
Cicortaș, Al. "Initiere în Access și SQL", Ed. UVVG, 2002
Boian F.M. "Programarea distribuită în Internet", Ed. Albastră, Cluj-Napoca, 1999.
Conolly T., Begg C., Strachan A., "Baze de date – Proiectare, Implementare, Gestionare", Ed. ?
Dollinger R., "Baze de Date", Universitatea Tehnică Cluj-Napoca, 1994
Dollinger R., "Baze de Date", Microinformatica, Cluj-Napoca, 1996
Forta, B. "SQL pentru Începători", (SAMS) Teora, 2002 (traducere Daniel Cihodaru)
M.Velicanu, I.Lungu, M.Muntean, “Sisteme de baze de date-teorie și practică”,editura Petrion, 2003.
M.Velicanu – “Dicționar explicativ al sistemelor de baze de date“, editura Economică, 2005
http://en.wikipedia.org/wiki/Adobe_Flex, 2008
http://en.wikipedia.org/wiki/Multitier_architecture, 2008
BIBLIOGRAFIE
Ionel Jian, Liliana Jian, Baze de date , Editura MIRTON, Timisoara, 1998
Sikha Bagui,Achievements and Weaknesses of Object -Oriented Database,Journal of Object Technology, Vol.2, Nr.4,Iulie-August 2003
Henderson, K. "Proceduri stocate în SQL Server. XML, HTML", Teora 2003
Peterson J. "Baze de date pentru începători", Ed. All, 2003
Popa Gh. și alții "Baze de date ACCESS", Ed. Cison, 2003
Cicortaș, Al. "Initiere în Access și SQL", Ed. UVVG, 2002
Boian F.M. "Programarea distribuită în Internet", Ed. Albastră, Cluj-Napoca, 1999.
Conolly T., Begg C., Strachan A., "Baze de date – Proiectare, Implementare, Gestionare", Ed. ?
Dollinger R., "Baze de Date", Universitatea Tehnică Cluj-Napoca, 1994
Dollinger R., "Baze de Date", Microinformatica, Cluj-Napoca, 1996
Forta, B. "SQL pentru Începători", (SAMS) Teora, 2002 (traducere Daniel Cihodaru)
M.Velicanu, I.Lungu, M.Muntean, “Sisteme de baze de date-teorie și practică”,editura Petrion, 2003.
M.Velicanu – “Dicționar explicativ al sistemelor de baze de date“, editura Economică, 2005
http://en.wikipedia.org/wiki/Adobe_Flex, 2008
http://en.wikipedia.org/wiki/Multitier_architecture, 2008
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Complexitatea Algoritmilor de Cautare In Baze de Date (ID: 149627)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.