ProHoster > Blog > Uprava > Globali so zakladni meči za shranjevanje podatkov. Drevesa. 1. del
Globali so zakladni meči za shranjevanje podatkov. Drevesa. 1. del
Pravi podatkovni meči - globali - so že dolgo znani, vendar jih še vedno le redki znajo učinkovito uporabljati ali pa tega superorožja sploh ne posedujejo.
Če uporabljate globale pri reševanju tistih problemov, v katerih so res dobri, lahko dosežete izjemne rezultate. Bodisi v produktivnosti bodisi v poenostavitvi rešitve problema (1, 2).
Globali so poseben način shranjevanja in obdelave podatkov, popolnoma drugačen od tabel v SQL. Pojavili so se leta 1966 v jeziku M (UMPS) (evolucijski razvoj - Predpomnite ObjectScript, v nadaljevanju COS) v zdravstveni bazi in je še vedno tam aktivno uporablja, prodrl pa je tudi na nekatera druga področja, kjer se zahtevata zanesljivost in visoka zmogljivost: finance, trgovanje itd.
Globali v sodobnih DBMS podpirajo transakcije, beleženje, replikacijo in particioniranje. Tisti. z njimi lahko gradimo sodobne, zanesljive, distribuirane in hitre sisteme.
Globali vas ne omejujejo na relacijski model. Omogočajo vam svobodo pri razvoju podatkovnih struktur, optimiziranih za posebne naloge. Za številne aplikacije je lahko pametna uporaba globalov resnično skrivno orožje, ki zagotavlja zmogljivost, o kateri lahko razvijalci relacijskih aplikacij samo sanjajo.
Globale kot način shranjevanja podatkov je mogoče uporabiti v številnih sodobnih programskih jezikih, tako na visoki kot na nizki ravni. Zato se bom v tem članku osredotočil prav na globale in ne na jezik, iz katerega so nekoč izhajali.
2. Kako delujejo globali
Najprej razumemo, kako globali delujejo in kakšne so njihove prednosti. Na globale je mogoče gledati z različnih zornih kotov. V tem delu članka jih bomo obravnavali kot drevesa. Ali kot hierarhična podatkovna skladišča.
Preprosto povedano, global je obstojen niz. Niz, ki se samodejno shrani na disk.
Težko si je zamisliti kaj preprostejšega za shranjevanje podatkov. V kodi (v jezikih COS/M) se od navadnega asociativnega niza razlikuje le po simbolu ^ pred imenom.
Če želite shraniti podatke v global, se vam ni treba naučiti jezika poizvedb SQL, ukazi za delo z njimi so zelo preprosti. Lahko se jih naučijo v eni uri.
Začnimo z najpreprostejšim primerom. Enostopenjsko drevo z 2 vejama. Primeri so napisani v COS.
Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"
Pri vstavljanju informacij v global (ukaz Set) se samodejno zgodijo 3 stvari:
Shranjevanje podatkov na disk.
Indeksiranje. Kar je v oklepaju, je ključ (v angleški literaturi - "subscript"), desno od enakega pa je vrednost ("node value").
Razvrsti. Podatki so razvrščeni po ključu. V prihodnosti bo pri prečkanju matrike prvi element »Sergey Smith«, drugi pa »John Sidorov«. Ko prejme seznam uporabnikov iz globala, baza ne izgublja časa z razvrščanjem. Poleg tega lahko zahtevate izpis razvrščenega seznama, začenši s katerim koli ključem, tudi neobstoječim (izhod se bo začel s prvim pravim ključem, ki sledi neobstoječemu).
Vse te operacije se zgodijo neverjetno hitro. Na domačem računalniku sem dobival vrednosti do 750 vstavkov/s v enem samem procesu. Na večjedrnih procesorjih lahko vrednosti dosežejo desetine milijonov vložkov/sek.
Seveda sama hitrost vstavljanja ne pove veliko. Informacije lahko na primer zelo hitro zapišete v besedilne datoteke – takole po govoricah Obdelava vizumov deluje. Toda v primeru globalov dobimo kot rezultat strukturirano indeksirano shrambo, s katero lahko enostavno in hitro delamo v prihodnosti.
Največja prednost globalov je hitrost, s katero je mogoče vstaviti nova vozlišča.
Podatki v globalu so vedno indeksirani. Prečenje po njih, tako na eni ravni kot globoko v drevo, je vedno hitro.
V global dodamo še nekaj vej druge in tretje ravni.
Set ^a("+7926X", "city") = "Moscow"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36
Očitno je, da je večnivojska drevesa mogoče zgraditi na podlagi globalov. Poleg tega je dostop do katerega koli vozlišča skoraj takojšen zaradi samodejnega indeksiranja med vstavljanjem. In na kateri koli ravni drevesa so vse veje razvrščene po ključu.
Kot lahko vidite, lahko informacije shranite tako v ključu kot v vrednosti. Skupna dolžina ključa (vsota dolžin vseh indeksov) lahko doseže Bajt 511, in vrednosti 3.6 MB za predpomnilnik. Število ravni v drevesu (število dimenzij) je 31.
Še ena zanimiva točka. Drevo lahko zgradite, ne da bi določili vrednosti vozlišč zgornjih ravni.
Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3
Prazni krogi so vozlišča, ki nimajo dodeljene vrednosti.
Da bi bolje razumeli globale, jih primerjajmo z drugimi drevesi: vrtnimi drevesi in drevesi imen datotečnega sistema.
Primerjajmo drevesa na globalih z nam najbolj znanimi hierarhičnimi strukturami: z običajnimi drevesi, ki rastejo na vrtovih in poljih, pa tudi z datotečnimi sistemi.
Kot vidimo pri vrtnih drevesih, so listi in plodovi le na koncih vej.
Datotečni sistemi – informacije so shranjene le na koncih vej, ki so polno kvalificirana imena datotek.
In tukaj je globalna struktura podatkov.
Razlike:
Notranja vozlišča: informacije v globalu so lahko shranjene v vsakem vozlišču, ne samo na koncih vej.
Zunanja vozlišča: Global mora imeti definirane vrednosti na koncih vej, medtem ko FS in vrtna drevesa nimajo.
Kar zadeva notranja vozlišča, lahko rečemo, da je struktura globala nadmnožica strukture imenskih dreves v datotečnih sistemih in vrtnih drevesih. Tisti. bolj prilagodljiv.
Na splošno je globalno urejeno drevo z možnostjo shranjevanja podatkov v vsakem vozlišču.
Da bi bolje razumeli delo globalov, si predstavljajte, kaj bi se zgodilo, če bi ustvarjalci datotečnih sistemov za shranjevanje informacij uporabili pristop, podoben globalom?
Če izbrišete posamezno datoteko v imeniku, bi samodejno izbrisali imenik, pa tudi vse prekrivne imenike, ki vsebujejo samo en pravkar izbrisani imenik.
Ne bi bilo potrebe po imenikih. Obstajale bi preprosto datoteke s poddatotekami in datoteke brez poddatotek. Če bi ga primerjali z navadnim drevesom, bi vsaka veja postala sadež.
Stvari, kot so datoteke README.txt, morda ne bodo potrebne. Vse, kar je bilo treba povedati o vsebini imenika, je bilo mogoče zapisati v samo datoteko imenika. V prostoru poti se ime datoteke ne razlikuje od imena imenika, tako da je bilo mogoče preživeti samo z datotekami.
Hitrost brisanja imenikov z ugnezdenimi podimeniki in datotekami bi se močno povečala. Na Habréju so bili večkrat članki o tem, kako dolgo in težko je izbrisati milijone majhnih datotek (1, 2). Vendar, če ustvarite psevdodatotečni sistem na globalni ravni, bo trajalo nekaj sekund ali le delčkov. Ko sem preizkusil brisanje poddreves na domačem računalniku, je odstranilo 1–96 milijonov vozlišč iz dvonivojskega drevesa na trdem disku (ne SSD) v 341 sekundi. Poleg tega govorimo o brisanju dela drevesa in ne le celotne datoteke z globali.
Odstranjevanje poddreves je še ena močna točka globalov. Za to ne potrebujete rekurzije. To se zgodi neverjetno hitro.
V našem drevesu je to mogoče narediti z ukazom Kill.
Kill ^a("+7926X")
Za boljše razumevanje, katera dejanja so nam na voljo prek globalov, bom podal kratko tabelo.
Osnovni ukazi in funkcije za delo z globali v COS
Kompleti
Nastavitev vej na vozlišče (če še ni definirano) in vrednosti vozlišča