Globalni su mačevi blaga za pohranjivanje podataka. Drveće. Dio 1

Pravi mačevi baze podataka - globali - odavno su poznati, ali još malo njih zna kako ih efikasno koristiti ili uopće ne posjeduje ovo superoružje.

Ako koristite globalne metode u rješavanju onih problema u kojima su oni zaista dobri, možete postići izvanredne rezultate. Bilo u produktivnosti ili u pojednostavljivanju rješenja problema (1, 2).

Globalne vrijednosti su poseban način pohranjivanja i obrade podataka, potpuno drugačiji od tabela u SQL-u. Pojavili su se 1966. na jeziku M(UMPS) (evolucijski razvoj - Cache ObjectScript, u daljem tekstu COS) u medicinskoj bazi podataka i još uvijek postoji aktivno koriste, a prodro i u neka druga područja gdje se zahtijevaju pouzdanost i visoke performanse: finansije, trgovina itd.

Globalni elementi u modernim DBMS-ovima podržavaju transakcije, evidentiranje, replikaciju i particioniranje. One. mogu se koristiti za izgradnju modernih, pouzdanih, distribuiranih i brzih sistema.

Globalne vrednosti vas ne ograničavaju na relacioni model. Oni vam daju slobodu da razvijete strukture podataka koje su optimizovane za specifične zadatke. Za mnoge aplikacije, pametna upotreba globala zaista može biti tajno oružje, pružajući performanse o kojima programeri relacijskih aplikacija mogu samo sanjati.

Globalne vrijednosti kao način pohranjivanja podataka mogu se koristiti u mnogim modernim programskim jezicima, i visokog i niskog nivoa. Stoga ću se u ovom članku posebno fokusirati na globale, a ne na jezik iz kojeg su nekada dolazili.

2. Kako funkcionišu globali

Hajde da prvo shvatimo kako funkcionišu globali i koje su njihove prednosti. Globalnosti se mogu posmatrati iz različitih uglova. U ovom dijelu članka ćemo ih posmatrati kao drveće. Ili poput hijerarhijskih skladišta podataka.

Pojednostavljeno rečeno, global je trajni niz. Niz koji se automatski pohranjuje na disk.
Teško je zamisliti nešto jednostavnije za pohranjivanje podataka. U kodu (na COS/M jezicima) razlikuje se od regularnog asocijativnog niza samo po simbolu ^ prije imena.

Da biste sačuvali podatke u globalu, ne morate učiti jezik SQL upita; naredbe za rad s njima su vrlo jednostavne. Mogu se naučiti za sat vremena.

Počnimo s najjednostavnijim primjerom. Jednoetažno drvo sa 2 grane. Primjeri su napisani u COS-u.

Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"

Prilikom umetanja informacija u globalnu (Set komanda), automatski se dešavaju 3 stvari:

1. Pohranjivanje podataka na disk.
2. Indeksiranje. Ono što je u zagradi je ključ (u engleskoj literaturi - “subscript”), a desno od jednakih je vrijednost („vrijednost čvora”).
3. Sortiraj. Podaci su sortirani po ključu. U budućnosti, prilikom prelaska niza, prvi element će biti „Sergey Smith“, a drugi „John Sidorov“. Prilikom primanja liste korisnika iz globala, baza podataka ne gubi vrijeme na sortiranje. Štaviše, možete zatražiti izlaz sortirane liste, počevši od bilo kojeg ključa, čak i nepostojećeg (izlaz će početi od prvog pravog ključa, koji dolazi nakon nepostojećeg).

Sve ove operacije se dešavaju neverovatno brzo. Na svom kućnom računaru dobijao sam vrednosti do 750 umetanja u sekundi u jednom procesu. Na višejezgrenim procesorima vrijednosti mogu doseći desetine miliona umetci/sek.

Naravno, sama brzina umetanja ne govori mnogo. Možete, na primjer, vrlo brzo upisati informacije u tekstualne datoteke - ovako glasine Obrada vize radi. Ali u slučaju globalnih jedinica, kao rezultat dobijamo strukturirano indeksirano skladište, s kojim se može lako i brzo raditi u budućnosti.

• Najveća snaga globala je brzina kojom se novi čvorovi mogu umetnuti.
• Podaci u globalu su uvijek indeksirani. Prelazak kroz njih, kako na jednom nivou tako i duboko u drvo, uvijek je brz.

Dodajmo još nekoliko grana drugog i trećeg nivoa globalnom.

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čigledno je da se stabla na više nivoa mogu izgraditi na osnovu globala. Štaviše, pristup bilo kom čvoru je skoro trenutan zbog automatskog indeksiranja tokom umetanja. I na bilo kojem nivou stabla, sve grane su sortirane po ključu.

Kao što vidite, informacije se mogu pohraniti i u ključu i u vrijednosti. Ukupna dužina ključa (zbir dužina svih indeksa) može doseći 511 bajtova, i vrijednosti 3.6 MB za Cache. Broj nivoa u stablu (broj dimenzija) je 31.

Još jedna zanimljiva tačka. Možete izgraditi stablo bez navođenja vrijednosti čvorova gornjih nivoa.

Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3

Prazni krugovi su čvorovi kojima nije dodijeljena vrijednost.

Da bismo bolje razumeli globalne vrednosti, uporedimo ih sa drugim stablima: baštenskim drvećem i stablima imena sistema datoteka.

Hajde da uporedimo drveće na globalima sa nama najpoznatijim hijerarhijskim strukturama: sa običnim drvećem koje raste u baštama i poljima, kao i sa sistemima datoteka.

Kao što vidimo kod vrtnog drveća, lišće i plodovi se nalaze samo na krajevima grana.
Sistemi datoteka – informacije se pohranjuju samo na krajevima grana, koji su potpuno kvalificirani nazivi datoteka.

A evo i globalne strukture podataka.

Razlike:

1. Unutrašnji čvorovi: informacije u globalu mogu biti pohranjene u svakom čvoru, ne samo na krajevima grana.
2. Vanjski čvorovi: Global mora imati definirane vrijednosti na krajevima grana, dok FS i vrtna stabla nemaju.

Što se tiče unutrašnjih čvorova, možemo reći da je globalna struktura nadskup strukture stabala imena u sistemima datoteka i vrtnim stablima. One. fleksibilniji.

Generalno, globalno jeste uređeno stablo sa mogućnošću pohranjivanja podataka u svaki čvor.

Da biste bolje razumjeli rad globala, zamislite šta bi se dogodilo kada bi kreatori sistema datoteka koristili pristup sličan globalima za pohranjivanje informacija?

1. Brisanjem jedne datoteke u direktoriju bi se automatski izbrisao direktorij, kao i svi gornji direktoriji koji sadrže samo jedan direktorij koji je upravo obrisan.
2. Ne bi bilo potrebe za imenicima. Jednostavno bi postojali fajlovi sa poddatotekama i fajlovi bez poddatoteka. Ako se uporedi sa običnim drvetom, onda bi svaka grana postala plod.

   
   

3. Stvari kao što su README.txt datoteke možda neće biti potrebne. Sve što je trebalo reći o sadržaju direktorija moglo bi se zapisati u samu datoteku direktorija. U prostoru putanja, ime datoteke se ne razlikuje od imena direktorija, tako da je bilo moguće proći samo sa datotekama.
4. Brzina brisanja direktorija s ugniježđenim poddirektorijumima i datotekama bi se dramatično povećala. Mnogo puta na Habréu je bilo članaka o tome koliko je dugo i teško izbrisati milione malih fajlova (1, 2). Međutim, ako napravite pseudo-datotečni sistem na globalnom nivou, to će potrajati sekunde ili djelići toga. Kada sam testirao brisanje podstabala na kućnom računaru, uklonio je 1-96 milion čvorova sa dvoslojnog stabla na HDD-u (ne SSD-u) za 341 sekundu. Štaviše, govorimo o brisanju dijela stabla, a ne samo cijelog fajla sa globalima.

Uklanjanje podstabala je još jedna jača strana globala. Za ovo vam nije potrebna rekurzija. Ovo se dešava neverovatno brzo.

U našem stablu to se može uraditi pomoću komande Ubiti.

Kill ^a("+7926X")

Za bolje razumijevanje koje su nam akcije dostupne preko globala, dat ću kratku tabelu.

Osnovne naredbe i funkcije za rad s globalima u COS-u

Set
Postavljanje grana na čvor (ako još nije definiran) i vrijednosti čvora

Spoji se
Kopiranje podstabla

Ubiti
Uklanjanje podstabla

ZKill
Brisanje vrijednosti određenog čvora. Podstablo koje izlazi iz čvora se ne dira

$Query
Potpuni obilazak drveta, ulazak duboko u drvo

$Order
Prelazak grana određenog čvora

$Data
Provjera da li je čvor definiran

$Increment
Atomsko povećavanje vrijednosti čvora. Za izbjegavanje čitanja i pisanja, za ACID. Nedavno je preporučeno da se promijeni na $Sequence

Hvala vam na pažnji, spremni smo odgovoriti na vaša pitanja.

odricanje: Ovaj članak i moji komentari na njega su moje mišljenje i nemaju nikakve veze sa zvaničnim stavom InterSystems Corporation.

Nastavak Globalni su mačevi blaga za pohranjivanje podataka. Drveće. Dio 2. Naučit ćete koje vrste podataka mogu biti prikazane na globalima i na kojim zadacima pružaju maksimalnu korist.

izvor: www.habr.com