🥇Globali — miecze-kładency dla przechowywania danych. Drzewa. Część 2

3. Opcje struktury przy użyciu globali

Taka struktura jak uporządkowane drzewo ma różne przypadki szczególne. Rozważmy te, które mają praktyczne znaczenie przy pracy z globalami.

3.1 Przypadek szczególny 1. Jeden węzeł bez gałęzi

Globals can be used not only like an array, but also as regular variables. For example, as a counter:

Set ^counter = 0  ; ustawienie licznika
Set id=$Increment(^counter) ;  atomowe inkrementowanie

Przy tym global, oprócz wartości, może mieć także gałęzie. Jedno nie wyklucza drugiego.

3.2 Przypadek szczególny 2. Jeden szczyt i wiele gałęzi

Ogólnie — jest to klasyczna baza key-value. A jeśli jako wartość będziemy przechowywać krotkę wartości, to otrzymamy zwykłą tabelę z kluczem głównym.

Aby zrealizować tabelę na globalach, będziemy musieli sami formować ciągi z wartości kolumn, a następnie zapisywać je w globalu według klucza głównego. Aby przy odczycie można było ponownie rozdzielić ciąg na kolumny, można użyć:

symboli separatorów.

Set ^t(id1) = "col11/col21/col31"
Set ^t(id2) = "col12/col22/col32"

sztywnej schemy, w której każde pole zajmuje wcześniej określoną liczbę bajtów. Tak jak to się robi w relacyjnych bazach danych.

specjalnej funkcji $LB (jest w Cache), która tworzy ciąg z wartości.

Set ^t(id1) = $LB("col11", "col21", "col31")
Set ^t(id2) = $LB("col12", "col22", "col32")

Co ciekawe, nie stanowi to trudności na globalach, aby zrobić coś podobnego do indeksów drugorzędnych w relacyjnych bazach danych. Nazwijmy takie struktury indeksowymi globalami. Indeksowy global to pomocnicze drzewo do szybkiego wyszukiwania według pól, które nie są składnikami klucza głównego głównego globalu. Aby go wypełnić i używać, trzeba napisać dodatkowy kod.

Stwórzmy indeksowy global według pierwszej kolumny.

Set ^i("col11", id1) = 1
Set ^i("col12", id2) = 1

Teraz, aby szybko znaleźć informacje w pierwszej kolumnie, musimy zajrzeć do globalu ^i i znaleźć klucze główne (id) odpowiadające poszukiwanemu wartości w pierwszej kolumnie.

Przy wstawianiu wartości możemy od razu tworzyć zarówno wartość, jak i indeksowe globaly według potrzebnych pól. A dla pewności wszystko to umieścimy w transakcji.

TSTART
Set ^t(id1) = $LB("col11", "col21", "col31")
Set ^i("col11", id1) = 1
TCOMMIT

Szczegóły jak zrobić na M tabele na globalach, emulację drugorzędnych indeksów.

Tego typu tabele będą działać tak szybko, jak tradycyjne bazy danych (a nawet szybciej), jeśli funkcje wstawiania/aktualizacji/usuwania wierszy zostaną napisane w COS/M i skompilowane.To twierdzenie sprawdziłem testami masowych INSERT i SELECT w jednej dwu kolumnowej tabeli, w tym z użyciem poleceń TSTART i TCOMMIT (transakcji).

Nie testowałem bardziej złożonych scenariuszy z równoczesnym dostępem i równoległymi transakcjami.

Bez użycia transakcji prędkość wstawiania wyniosła przy milionie wartości 778 361 wstawek/sekundę.
Przy 300 milionach wartości — 422 141 wstawek/sekundę.

Przy użyciu transakcji — 572 082 wstawek/sekundę przy 50M wstawkach. Wszystkie operacje wykonywane były z skompilowanego kodu M.
Dyski twarde to zwykłe, nie SSD. RAID5 z Write-back. Procesor Phenom II 1100T.

Aby przeprowadzić podobne testy w bazie SQL, trzeba napisać procedurę składowaną, która w pętli będzie wykonywać wstawienia. Podczas testowania MySQL 5.5 (magazyn InnoDB) w tej metodologii uzyskałem liczby nieprzekraczające 11K wstawek na sekundę.
Tak, implementacja tabel na globalach wydaje się bardziej skomplikowana niż w relacyjnych bazach danych. Dlatego przemysłowe bazy danych na globalach mają dostęp SQL, aby uprościć pracę z danymi tabelarycznymi.

Jeśli ogólnie schemat danych nie będzie się często zmieniać, prędkość wstawiania nie jest krytyczna, a całą bazę można łatwo przedstawić w postaci znormalizowanych tabel, to łatwiej pracować właśnie z SQL, ponieważ zapewnia on wyższy poziom abstrakcji.

W tym szczególnym przypadku chciałem pokazać, że globalne mogą działać jako konstruktor do tworzenia innych baz danych. Jak asembler, na którym można pisać inne języki. A oto przykłady, jak można stworzyć na globalach odpowiedniki key-value, list, zbiorów, tabeli, baz dokumentowych.

Jeśli trzeba stworzyć jakąś niestandardową bazę danych minimalnym wysiłkiem, warto zwrócić uwagę na globalne.

3.3 Szczególny przypadek 3. Dwupoziomowe drzewo, w którym każdy węzeł drugiego poziomu ma stałą liczbę gałęzi

Pewnie się domyśliłeś: to alternatywna implementacja tabel na globalach. Porównajmy tę implementację z poprzednią.

Tabele na dwupoziomowym drzewie vs. na jednopoziomowym drzewie.

Minusy
Zalety

Wolniej przy wstawianiu, ponieważ trzeba ustawić liczbę węzłów równą liczbie kolumn.
Większe zużycie przestrzeni dyskowej. Ponieważ indeksy globalne (w rozumieniu jak indeksy tablic) z nazwami kolumn zajmują miejsce na dysku i są duplikowane dla każdego wiersza.

Szybszy dostęp do wartości poszczególnych kolumn, ponieważ nie trzeba analizować wiersza. W moich testach jest szybszy o 11,5% przy 2 kolumnach i jeszcze bardziej przy większej liczbie kolumn.
Łatwiej zmieniać schemat danych.
Bardziej przejrzysty kod.

Wynik: To kwestia gustu. Ponieważ prędkość jest jednym z kluczowych zalet globali, to niemal nie ma sensu używać tej implementacji, ponieważ prawdopodobnie nie będzie działać szybciej niż tabele w relacyjnych bazach danych.

3.4 Przypadek ogólny. Drzewa i uporządkowane drzewa.

Każda struktura danych, która może być przedstawiona w postaci drzewa, idealnie pasuje do globali.

3.4.1 Obiekty z podobiektami.

To obszar tradycyjnego zastosowania globali. W sferze medycznej istnieje ogromna liczba chorób, leków, objawów, metod leczenia. Tworzenie tabeli dla każdego pacjenta z milionem pól jest nieefektywne. Zwłaszcza, że 99% pól byłoby pustych.

Wyobraź sobie bazę danych SQL z tabelami: „pacjent” ~ 100 000 pól, „Leki” — 100 000 pól, „Terapie” — 100 000 pól, „Poważne przypadki” — 100 000 pól itd. Można również stworzyć bazę danych składającą się z wielu tysięcy tabel, każda dla określonego typu pacjenta (a mogą one się nakładać!), leczenia, leków oraz jeszcze tysiące tabel dla powiązań między tymi tabelami.

Globale idealnie nadają się do medycyny, ponieważ pozwalają stworzyć dla każdego pacjenta dokładny opis jego historii choroby, różnych terapii, działań leków w postaci drzewa, nie marnując przy tym dodatkowej przestrzeni dyskowej na puste kolumny, jak miałoby to miejsce w przypadku relacyjnym.

Na globalach wygodnie jest tworzyć bazy danych z danymi o ludziach, gdy ważne jest zgromadzenie i usystematyzowanie maksymalnej różnorodności informacji o kliencie. Jest to poszukiwane w medycynie, sektorze bankowym, marketingu, archiwistyce i innych dziedzinach.

.
Bez wątpienia, w SQL można również symulować drzewo za pomocą zaledwie kilku tabel.EAV, 1,2,3,4,5,6,7,8,9,10), jednak jest to znacznie bardziej złożone i wolniej działa. W praktyce trzeba by stworzyć globalną strukturę działającą na tabelach i ukryć całą pracę z tabelami pod warstwą abstrakcji. Nie należy emulować technologii niższego poziomu (globalne) za pomocą technologii wyższego poziomu (SQL). To jest niepraktyczne.

Nie jest tajemnicą, że zmiana schematu danych w ogromnych tabelach (ALTER TABLE) może zająć sporo czasu. MySQL, na przykład, podczas wykonywania ALTER TABLE ADD|DROP COLUMN przeprowadza pełne kopiowanie informacji ze starej do nowej tabeli (przetestowałem silniki MyISAM, InnoDB). To może zawiesić działającą bazę z miliardami wpisów na dni, jeśli nie tygodnie.

Zmiana struktury danych, jeśli używamy globalnych, nic nas nie kosztuje. W każdej chwili możemy dodać dowolne potrzebne nam nowe właściwości do dowolnego obiektu, na dowolnym poziomie hierarchii. Zmiany związane z zmianą nazw gałęzi można uruchamiać w tle na działającej bazie danych.

Dlatego, gdy mówimy o przechowywaniu obiektów z ogromną liczbą opcjonalnych właściwości, globalne są doskonałym wyborem.

Przy czym, przypominam, dostęp do dowolnej właściwości jest natychmiastowy, ponieważ w globalnych wszystkie ścieżki są reprezentowane przez B-drzewo.

Bazy danych na globalnych, w ogólności, to odmiana dokumentowo-orientowanych baz danych, umożliwiająca przechowywanie informacji hierarchicznych. W związku z tym w obszarze przechowywania kart medycznych mogą konkurować z dokumentowo-orientowanymi bazami danych. Ale to wciąż nie do końca to.Porównajmy na przykład MongoDB. W tej dziedzinie przegrywa z globalnymi z powodów:

Rozmiar dokumentu. Jednostką przechowywania jest tekst w formacie JSON (dokładniej BSON) o maksymalnym rozmiarze około 16MB. Ograniczenie to zostało wprowadzone specjalnie, aby baza JSON nie spowalniała podczas przetwarzania, jeśli przechowywany jest ogromny dokument JSON, a następnie odnosi się do niego po polach. W tym dokumencie powinna być skoncentrowana cała informacja o pacjencie. Wszyscy wiemy, jak grube mogą być karty pacjentów. Maksymalny rozmiar karty do 16MB od razu skreśla pacjentów, których karta chorób zawiera pliki z MRI, skany rentgenowskie i inne badania. Z jednej gałęzi globalnej można mieć jednak informacje o gigabajtach i terabajtach. W zasadzie na tym można by zakończyć, ale będę kontynuował.
Czas świadomości/zmiany/usunięcia nowych właściwości w karcie pacjenta. Taka baza danych musi załadować całą kartę do pamięci (to duża ilość!), sparsować BSON, dodać/zmienić/usunąć nowy węzeł, zaktualizować indeksy, zapakować w BSON, zapisać na dysku. Globalowi wystarczy jedynie odwołać się do konkretnej właściwości i przeprowadzić na niej operacje.
Szybkość dostępu do poszczególnych właściwości. Przy wielu właściwościach w dokumencie i jego złożonej strukturze dostęp do poszczególnych właściwości będzie szybszy dzięki temu, że każda ścieżka w globalnej przestrzeni to B-drzewo. W BSON trzeba będzie przeparsować dokument w sposób liniowy, aby znaleźć potrzebną właściwość.

3.3.2 Tablice asocjacyjne

Tablice asocjacyjne (nawet z zagnieżdżonymi tablicami) doskonale układają się w globalach. Na przykład taka tablica z PHP zostanie przedstawiona na pierwszym obrazku 3.3.1.

$a = array(
  "name" => "Vince Medvedev",
  "city" => "Moscow",
  "threatments" => array(
    "surgeries" => array("apedicectomy", "biopsy"),
    "radiation" => array("gamma", "x-rays"),
    "physiotherapy" => array("knee", "shoulder")
  )
);

3.3.3 Dokumenty hierarchiczne: XML, JSON

Również łatwo przechowywane w globalach. Można je zorganizować na różne sposoby.

XML
Najprostszym sposobem rozkładu XML na globaly jest trzymanie atrybutów tagów w węzłach. A jeśli potrzebny byłby szybki dostęp do atrybutów tagów, możemy je wydzielić do osobnych gałęzi.

<note id="5">
<to>Wania</to>
<from>Świata</from>
<heading>Przypomnienie</heading>
<body>Zadzwoń do mnie jutro!</body>
</note>

W COS będzie to odpowiadać kodowi:

Set ^xml("note")="id=5"
Set ^xml("note","to")="Saša"
Set ^xml("note","from")="Swieta"
Set ^xml("note","heading")="Przypomnienie"
Set ^xml("note","body")="Zadzwoń do mnie jutro!"

Uwaga: Dla XML, JSON, tablic asocjacyjnych można wymyślić wiele różnych sposobów odwzorowania na globalach. W tej sytuacji nie odzwierciedliliśmy kolejności zagnieżdżonych tagów w tagu note. W globalu ^xml zagnieżdżone tagi będą wyświetlane w porządku alfabetycznym. Aby ściśle odzwierciedlić kolejność, można zastosować na przykład takie odwzorowanie:

JSON.
Na pierwszym obrazku z sekcji 3.3.1 pokazano odwzorowanie tego dokumentu JSON:

var document = {
  "name": "Vince Medvedev",
  "city": "Moscow",
  "threatments": {
    "surgeries": ["apedicectomy", "biopsy"],
    "radiation": ["gamma", "x-rays"],
    "physiotherapy": ["knee", "shoulder"]
  },
};

3.3.4 Identyczne struktury związane relacjami hierarchicznymi

Przykłady: struktura biur sprzedaży, rozmieszczenie ludzi w strukturze MLM, baza debiutów w szachach.

Baza debiutów. Można wykorzystać ocenę siły ruchu jako wartość indeksu w globalach. W takim przypadku, aby wybrać najsilniejszy ruch, wystarczy wybrać gałąź o najwyższej wadze. W globalach wszystkie gałęzie na każdym poziomie będą posortowane według siły ruchu.

Struktura biur sprzedaży, struktura ludzi w MLM. W węzłach można przechowywać cache'owane wartości odzwierciedlające charakterystyki całego poddrzewa. Na przykład, obrót sprzedaży danego poddrzewa. W każdej chwili możemy uzyskać liczbę, która odzwierciedla osiągnięcia dowolnej gałęzi.

4. W jakich przypadkach najkorzystniej jest używać globali

W pierwszej kolumnie przedstawiono przypadki, gdy zyskasz istotny wzrost prędkości dzięki użyciu globali, a w drugiej, gdy uprości się rozwój lub model danych.

Szybkość
Wygoda przetwarzania/prezentacji danych

Wstawianie [z automatycznym sortowaniem na każdym poziomie], [indeksowaniem według klucza głównego]
Usuwanie poddrzew
Obiekty z wieloma zagnieżdżonymi właściwościami, do których potrzebny jest indywidualny dostęp
Hierarchiczna struktura z możliwością przeszukiwania gałęzi potomnych z dowolnej, nawet nieistniejącej
Przeszukiwanie poddrzew w głąb

Obiekty/elementy z ogromną liczbą opcjonalnych [i/lub zagnieżdżonych] właściwości/elementów
Dane bez schematów (schema-less). Kiedy nowe właściwości mogą często się pojawiać, a stare znikać.
Konieczność stworzenia niestandardowej bazy danych.
Bazy ścieżek i drzewa decyzji. Kiedy ścieżki wygodnie przedstawia się w formie drzewa.
Usuwanie struktur hierarchicznych bez użycia rekurencji

Kontynuacja „Gglobali — miecze-kładency dla przechowywania danych. Rzadkie tablice. Część 3”.

Zrzeczenie się odpowiedzialności: Ten artykuł i moje komentarze do niego są moją opinią i nie mają związku z oficjalnym stanowiskiem korporacji InterSystems.

Źródło: habr.com