Cuprins.
Modificări în versiunea.
Versiunea completă a acestei secțiuni este definită ca: versiya.podversiya.vypusk.
Baza de date pentru aplicații embedded.
Accesul la înregistrările bazei de date se realizează cu ajutorul unei chei. Cheia este o colecție de câmpuri individuale ale înregistrării, cu valoarea care este produsă și toate operațiunile de căutare: pentru înregistrare, plus sale, ștergere și altele. O bază de date poate avea mai mult de o cheie, care permite accesul la diferite căi logice. Unele baze de date de sprijin posibilitatea de chei duplicat, atunci când unele înregistrări au valori identice pentru toate domeniile-cheie. Cu toate acestea, lucrul cu astfel de date destul de incomode și ar trebui să fie încurajați să utilizeze numai chei unice. În cazul în care câmpul actual nu este suficient pentru a forma o astfel de cheie, este recomandabil să adăugați un câmp care va oferi o cheie unică.
Vom lua în considerare căutarea de intrare-cheie, adăugând o nouă intrare, eliminarea acestuia și transferul către ulterioară sau cea precedentă în cadrul procedurii de intrare-cheie ca operațiunile de bază de date. Pentru a caracteriza timpul de executare a operațiilor de bază utilizate parametru O (O este mare), care caracterizează ordinea relativă a numărului necesar de operații elementare de mașini în funcție de numărul de intrări de baze de date (dimensiunea sa). Astfel, O (N) indică faptul că executarea operațiilor de bază în raport cu baza, și O (LOGN) indică faptul că creșterile de funcționare numai proporțional cu logaritmul numărului de intrări de baze de date.
lista neordonată.
Într-o listă neordonată datele sunt stocate după primirea fără nici un fel de sortare. În cazul ștergerii unei înregistrări în locul său o nouă intrare cu o valoare-cheie arbitrară poate fi plasat.
caracteristicile și algoritmi de o listă neordonată operațiuni: temporale
Astfel, toate operațiunile de bază ale datelor introduse într-o listă neordonată, suficient de grele - numărul operațiilor elementare necesare crește proporțional cu mărimea bazei. Cu toate acestea, simplitatea implementării software-ului unei astfel de liste justifică utilizarea acesteia, în cazul în care numărul de înregistrări de baze de date să nu depășească aproximativ o sută. Trebuie remarcat faptul că lucrul cu lista neordonată algoritmic similară cu utilizarea declarațiilor condiționate, în cazul în cazul în care, altfel accesul selectiv la date comune.
O matrice comandat cu un interval limitat de valori.
Caracteristicile temporale și algoritmi comandat operațiunile de matrice cu o gamă limitată de valori:
Ordinea relativă a timpului de execuție
Algoritmul de execuție operațiune de bază
O serie ordonată de date.
O matrice comandat este una din baza de date clasice pentru acest lucru și nu impune constrângeri asupra gamei audio de valori-cheie sau numărul de chei diferite. Există două implementări ale unei baze de date într-o astfel de matrice din perspectiva de domenii-cheie. Prima metodă presupune simplificarea întregii baze de date pe cheia primară, care este folosit ca unul sau mai multe câmpuri de date.
O altă implementare prevede separarea unei baze de date pe corpul neordonate și unul sau mai multe matrice cheie comandate. Această abordare face posibilă pentru a forma un număr de chei diferite. În plus, costurile reduse pentru a adăuga intrări, în cazul în care dimensiunea nu este suficient de date cheie de mari. Dezavantajul acestei soluții este necesitatea de a completa fiecare indicator cheie de intrare și duplicarea câmpurilor cheie din setul de date. În cazul în care această dublare nu este efectuată, atunci ansamblul de înregistrare cuprinzătoare necesită introducerea unor indicii inverse din datele de pe tastele de intrare corespunzătoare.
caracteristicile și algoritmi de operații set de date ordonate: temporale
probă de înregistrare directă.
Căutați elementul dorit în baza de date este realizată de matrice cheie sau baza de date de împărțire în două în sine, în cazul în care are o cheie primară (algoritmul de căutare binară). Vă rugăm să rețineți că timpul de rezidență a oricărei înregistrări de baze de date a garantat dependența logaritmică de mărimea O (LOGN). Acest lucru face posibil pentru a prezice timpul de acces maxim la înregistrări, ceea ce reprezintă un avantaj semnificativ pentru aplicații embedded. Nu este un accident binar algoritm de căutare inclus în standard, de multe bibliotecă limbaj de programare.
Cu toate acestea, funcționarea adăugarea și ștergerea intrărilor sunt asociate cu razdvizhki nevoie sau pensarea matrice, și, prin urmare, destul de grele. Limita practică de dimensiunea bazei de date, realizată într-o serie ordonată, de ordinul a zece mii de intrări, care este suficient pentru majoritatea aplicațiilor încorporate. În aceste cazuri, atunci când se determină economiile de costuri, devine cu privire la funcționarea plus / îndepărtare, este recomandabil să se ia în considerare utilizarea de tabele de decizie bazate pe hash, structuri de date, cum ar fi copaci sau liste specializate.
Implementarea software a unei liste neordonate.
Programul prezintă o implementare universală a trei operațiuni de bază: căutare, adăugați și șterge înregistrări. Ca o lista neordonata este un mod minimalist de a organiza o bază de date pentru a stoca este recomandabil să se utilizeze o serie de lungime fixă. În plus, algoritmii înșiși sunt adesea puse în aplicare un mod de specialitate. Astfel, în valoarea cheie selectată și controlul suprapunerii sale este adesea folosit ca un element liber al șirului și steagul nu poate fi efectuată.
Unele compilatoare interpretează tipurile care nu conțin cuvinte cheie semnat ca un semn gratuit. Este sentimente amestecate, ci pentru că de fapt este cazul, este recomandabil să se aplice o definiție clară a semnului (semnate sau nesemnate).
Funcția search_object (obj) caută înregistrarea bazei de date de valoare-cheie. Algoritmul de căutare - scanare cuprinzătoare [so_4]. Pentru fiecare intrare activă (ocupată) [so_5] compară cheia sa [so_6], care funcționează în coincidență nu pozvraschaet un număr negativ, determinând matricea elementului de scriere. minus 1 [so_9] returnează o căutare fără succes este finalizată.
Funcția add_object (obj) adaugă o intrare în baza de date. Tastele de control sunt forțe unice pentru a produce scanare cuprinzătoare [ao_5]. La detectarea unuia dintre înregistrările active, potrivite valoare-cheie este returnat eroare duplicarea [ao_9]. Pentru a intra în primul spațiu de detecție este fixat într-o nouă înregistrare de date [ao_6, ao_7]. În cazul în care un astfel nu a fost în baza de date returnează o eroare de depășire [ao_12]. Altfel, o nouă intrare [ao_13, ao_14] este plasat pe spațiul detectat.
Funcția delete_object (obj) marchează înregistrarea corespunzătoare a bazei de date cheie [do_6] ca liber [do_7]. În cazul în care intrarea necesară în rândul activă [do_5] nu este găsit, returnează „înregistrare nu a fost găsit“ [do_12] cod de eroare.
marcate ca active (gratuit) Când inițializarea baza de date toate înregistrările [id_4].
O serie ordonată de chei primare.
Implementarea noastră, un terminal de înregistrări de date a complementului care conțin valorile maxime și minime din toate domeniile-cheie, și sunt respectiv primele și ultimele elemente ale unei baze de matrice ordonate. Acest lucru vă permite de a simplifica și de a optimiza de lucru algoritm criptografic de scanare, păstrarea ei înșiși înregistrările finale inaccesibile. Mai mult decât atât, este posibil să se adauge la baza de listări de locuri de muncă conțin, de asemenea, valori limită pentru câmpurile cheie. Toate algoritmii lucra cu baza de date necesită prezența obligatorie a înregistrărilor terminale. Decizie furnizarea de astfel de înregistrări, poate fi foarte util atunci când se utilizează bazele de date clasice.
Programul se referă la funcțiile standard biblioteca C Due
Unele compilatoare interpretează tipurile care nu conțin cuvinte cheie semnat ca un semn gratuit. Este sentimente amestecate, ci pentru că de fapt este cazul, este recomandabil să se aplice o definiție clară a semnului (semnate sau nesemnate).
Funcția key_object (obj1, obj2) definește raportul dintre cele două înregistrări de bază cheie. În primul rând a comparat primul câmp cheie [ko_2, ko_3], având o prioritate mai mare. Dacă acest câmp este aceeași pentru ambele chei, compară al doilea câmp [ko_4, ko_5]. Rezultatele acestor comparații, se ia o decizie cu privire la relația dintre chei (mai mult, mai puțin, egală), cele două înregistrări de baze de date.
Funcția search_object (obj) efectuează o căutare binară pe valoarea cheii de intrare de bază conținută în obj. care este un pointer la parametrul de intrare al funcției. Dacă găsiți baza înregistrării datelor solicitate returnează un număr non-negativ - poziția (offset) în ceea ce privește baza de date a înregistrărilor [so_12]. Dacă un astfel nu este găsit, funcția returnează minus 1 [so_14].
Funcția insert_object (obj, poz) introduce un nou record, a cărui poziție (offset de bază) este specificată de pos. Pentru aceasta, baza extensibil: incrementarea numărului de înregistrare maxim [io_4] și ciclul până la baza șirului [io_5. io_7]. Apoi, pentru poziția vacantă a noului intrare este introdusă [io_8]. Este nevoia de a adăuga înregistrarea razdvizhki determină o relație proporțională O (N) numărul relativ al operațiilor de mărimea de bază.
Funcția add_object (obj) oferă un set de operații pentru adăugarea de intrări în baza de date. În cazul în care matricea de memorie selectată anterior este deja plin [ao_6]. cerere luată memorie suplimentară [ao_8. ao_10]. INC_OBJECTS parametru. specificând incrementarea bazei, deoarece dimensiunea umplută este ales pentru a face apel la funcția de alocare a memoriei [ao_10] nu a fost prea frecventă (aceasta este o operațiune foarte costisitoare), iar pe de altă parte, baza nu ar fi avut prea multe înregistrări goale (numărul s-a putut ajunge la INC_OBJECTS-1). Eroare de memorie Adăugarea poate apărea ca în finalizarea fără succes a cererii [ao_10], iar în cazul depășirii dimensiunii maxime a bazei (nu condiționa [ao_9] este îndeplinită).
În cazul în care toate operațiunile necesare pentru a aloca memorie suplimentară este finalizată cu succes, a produs spațiu binar de căutare [ao_18. ao_26], în cazul în care urmează să fie introdus un nou record. In acest posibila dublare controlată a cheii și [ao_25] codul de eroare este returnat atunci când o astfel de detecție. Daca va avea succes, găsirea unei noi poziții de înregistrare a făcut introducerea acestuia [ao_27]. Ca o funcție a înregistrărilor de căutare în funcție de cheie, algoritmul este adaptat pentru cazul în care baza de date conține sfârșitul de înregistrare, iar prezența lor este o necesitate.
Funcția delete_object (obj) elimină din înregistrarea de bază de date cu valoarea cheie conținută în obj. un pointer care este trecut ca parametru de intrare. Dacă intrarea dorită este găsită, făcută de bază schimbare ușoară, șterge acest post [ciclu do_6], iar numărul maxim de intrări este scăzut cu o [do_9].
O serie ordonată de chei străine.
Implementarea noastră, tastele externe bazei de date utilizate matrici de adiție se încheie înregistrările care conțin valorile maxime și minime din toate domeniile, fiind primul și ultimele elemente ale unei chei de matrice ordonate. Acest lucru vă permite de a simplifica și de a optimiza pentru căutare algoritmul de criptare cheie, menținându-se încheie înregistrările inaccesibile. Mai mult decât atât, este posibil să se adauge la baza de listări de locuri de muncă conțin, de asemenea, valori limită pentru câmpurile cheie. Toate algoritmii lucra cu baza de date necesită prezența obligatorie a înregistrărilor terminale. Decizie furnizarea de astfel de înregistrări, poate fi foarte util atunci când se utilizează bazele de date clasice.
Programul se referă la funcțiile standard biblioteca C Due
Unele compilatoare interpretează tipurile care nu conțin cuvinte cheie semnat ca un semn gratuit. Este sentimente amestecate, ci pentru că de fapt este cazul, este recomandabil să se aplice o definiție clară a semnului (semnate sau nesemnate).
Funcția key_1_compare (k1, k2) definește raportul dintre cheile primei baze. În primul rând a comparat primul câmp cheie [k1c_2, k1c_3], având o prioritate mai mare. Dacă acest câmp este aceeași pentru ambele chei, compară al doilea câmp [k1c_4, k1c_5]. Rezultatele acestor comparații, se ia o decizie cu privire la relația dintre chei (mai mult, mai puțin egale).
Funcția search_object_k1 (cheie) efectuează o binare de înregistrări de căutare prin valoarea cheie a primei chei. care este un pointer la parametrul de intrare al funcției. La detectarea unui număr nenegativ este returnat la baza cheilor de scriere - poziția (offset) corespunzătoare a corpului de bază cu privire la înregistrarea ei începe să [so1_12]. Dacă o înregistrare cheie adecvată nu este găsit, funcția returnează minus 1 [so1_14].
Funcția search_object_k2 (cheie) efectuează o binare de înregistrări de căutare prin valoarea cheie a doua cheie. care este un pointer la parametrul de intrare al funcției. La detectarea unui număr nenegativ este returnat la baza cheilor de scriere - poziția (offset) corespunzătoare a corpului de bază cu privire la înregistrarea ei începe să [so2_10]. Dacă o înregistrare cheie adecvată nu este găsit, funcția returnează minus 1 [so2_12]. Așa cum nu se utilizează a doua cheie compozit compara direct operațiunile de valorile câmpurilor cheie [so2_8, so2_9].
Funcția add_object (obj) oferă un set de operații pentru adăugarea de intrări în baza de date. Dacă memoria alocată matrice umplute anterior ([ao_8] pentru corpul de bază, [ao_20] matrice cheie). cerere luată memorie suplimentară [ao_10. ao_12] pentru corpul de bază și [ao_23. ao_26] cheie. INC_OBJECTS parametru. Specifică dimensiunea incrementului de matrice de bază ca și completarea acesteia, este ales pentru a face apel la o funcție de alocare de memorie [ao_12, ao_25, ao_26] nu au fost prea frecvente (aceasta este o operațiune foarte costisitoare), iar pe de altă parte, baza de date nu rămâne prea mult intrările goale (numărul poate ajunge la INC_OBJECTS-1). Eroare memorie adăugare poate să apară ca și în cererile nereușite de finalizare, iar dacă aceasta depășește dimensiunea maximă a bazei (nu condițiile [ao_11, ao_24]).
În cazul în care toate operațiunile necesare pentru a aloca memorie suplimentară este finalizată cu succes, o căutare binară se realizează inserții înregistrări cheie: [ao_35. ao_45] pentru prima cheie și [ao_46. ao_54] pentru al doilea. În același timp, controlat de posibila dublare a fiecărei chei și codul de eroare este returnat atunci când o astfel de detecție [ao_44] - prima cheie, [ao_53] secundă. După finalizarea cu succes a tuturor inspecțiilor se introduce o nouă intrare de la sfârșitul corpului de bază [ao_56] și în stabilirea indicii corespunzătoare în cheile [ao_57, ao_58]. Apoi, o bază de date de chei extensibil [ao_60, ao_64] și sunt aduse pentru pozițiile lor specifice [ao_63, ao_67]. Ca o funcție a înregistrărilor de căutare în funcție de cheie, algoritmul este adaptat pentru cazul în care baza de date conține sfârșitul de înregistrare, iar prezența lor este o necesitate.
Funcția delete_object (obj) elimină din înregistrarea de bază de date cu valorile-cheie conținute în obj. un pointer care este trecut ca parametru de intrare. Căutând intrare este solicitată în mod independent de fiecare cheie [do_12, do_26]. În cazul în care se găsește în ambele taste matrici, a făcut o ușoară schimbare a acestora: ciclul [do_37] șterge prima cheie, iar [do_40] secundă. Prin urmare, numărul maxim de intrare-cheie bazei de date este decrementat cu o [do_43].
Pe că ar fi posibil să se finalizeze eliminarea - intrarea corespunzătoare este acum disponibilă când căutați orice tastă. Dar, în acest caz, corpul de bază se va acumula nu note de lucru, asa ca are sens să-l ștergeți, de asemenea, le. Aceasta este o operație destul de consumatoare de timp. Mai întâi deplasarea bazei [do_44] corp (locația înregistrării ștearsă a fost înregistrată în [do_36]). Apoi, pentru a menține coerența referințelor cheie, pentru a implementa o ajustare corespunzătoare (decrement) de indicii referitoare la notele de bază ale corpului care au fost introduse după telecomandă [do_48]. Astfel, severitatea îndepărtarea completă a înregistrării este foarte mare. Cu toate acestea, în cerere, această operație este, de obicei, cele mai rare și cu o cantitate mai mare de efort de calcul este destul de posibil să se împace.