Organizarea indicii în formă de copaci în

Construirea unui B-arbore este asociat cu o idee simplă de a crea un index al deja construit indicele. De exemplu, în construcția unei zone indexate secvențial fișier index în sine poate fi considerat ca fișierul principal, pe care se poate construi un index în vrac, și așa mai departe, până când zona de index nu va reprezenta doar o singură unitate.

În cazul general, acesta poate fi construit într-un copac, fiecare unitate părinte care este conectat cu același număr de unități subordonate egal cu numărul de înregistrări index adăpostite în unitatea de bază. Numărul de pași în acest caz, pentru a găsi orice înregistrare a fișierului de master este identic și egal cu numărul de niveluri în copac.

Astfel de arbori sunt numite echilibrate (calea de la rădăcină la fiecare frunză același) Astfel, termenul este derivat din B -tree echilibru englezesc (echilibru). Exemplu de B-arborele este prezentată în figura 30.

Folosind tehnica B-copac este acum probabil să fie cea mai populară abordare pentru organizarea indicilor în baza de date. Din punct de vedere al reprezentării logice externe, B-tree - un arbore echilibrat, extrem de ramificat în memoria externă. copac verde - un copac fiecare proprietate nod pentru a se referi la un număr mare de noduri copil. Din punct de vedere al organizării fizice. Structura B-arbore este reprezentat ca paginile multispisochnaya de memorie externă, adică, fiecare nod al arborelui corespunde unui bloc de memorie externă (pagina. Cm. P.7.3.2.). pagini interne și frunze au, în general, o structură diferită.

Caută în B-copac - un pasaj de la rădăcină la o frunză, în conformitate cu o valoare-cheie dată.

fișier Inverted (acces prin atribute non-core)

Metodele de mai sus de intrări din lista de acces este realizată prin valoarea cheii primare. Cu toate acestea, tipul de operațiune pentru a obține o anumită indicație a unui criteriu de selecție implică înregistrări copii ale valorilor unuia sau mai multor atribute non-cheie (adesea numit secundar și chei) .Zametim că corespunzătoare limbaj de interogare SQL include o clauza WHERE.

O cheie pentru organizarea de căutare pentru valori de atribut non-cheie este inversarea fișierului.

fișier Inverted - un fișier care este susținută de un dens valori ale indicelui secundare pentru un câmp care conține intrări. Fișierul inversat constă dintr-un indice de mai multe niveluri și un set de liste de acces de indicii. oferind acces la înregistrările de date.

Lista de acces este indicatorul fizic listă secvențială de indicii pentru înregistrări care conțin valori identice ale atributului corespunzător.

În cea mai comună de realizare, un index cu două niveluri. Organigrama fișierului inversat este prezentată în figura 31.

Parțial inversat fișier inversat pe un număr selectiv de atribute non-cheie.

Complet inversat fișier inversat pentru fiecare atribut non-cheie, care este, este un fișier care este susținută de un dens valori ale indicelui secundare pentru fiecare domeniu pe care le conține înregistrări, nu cheia primară.

Construcția de mai sus discutat de atribute index unice (tipuri de elemente de date). Evident, este posibil să se utilizeze indici compozit. ale cărui elemente corespund oricărui tip de elemente concatenate.