🥇Глобали — мечове-кладенци за съхранение на данни. Дървета. Част 2

3. Варианти на структурите при използването на глобали

Структурата, известна като подредено дърво, има различни специфични случаи. Нека разгледаме тези, които имат практическа стойност при работа с глобали.

3.1 Специфичен случай 1. Един възел без клони

Глобалите могат да се използват не само като масив, но и като обикновени променливи. Например, като брояч:

Set ^counter = 0  ; задаване на брояча
Set id=$Increment(^counter) ; атомарно инкрементиране

При това глобалът, освен стойността, може да има и клони. Едното не изключва другото.

3.2 Специфичен случай 2. Една върхова точка и множество клони

Общо взето — това е класическа key-value база. А ако като стойност запазим кортеж от стойности, то ще получим обикновена таблица с първичен ключ.

За реализация на таблица на глобалите, ще трябва сами да формираме редове от стойностите на колоните и след това да ги запазим в глобала по първичния ключ. За да може при прочитане да можем да разделим реда отново на колони, можем да използваме:

разделящи символи.

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

строга схема, при която всяко поле заема предварително определен брой байтове. Както се прави в релационни бази данни.
специална функция $LB (има в Cache), която съставя ред от стойности.
```
Set ^t(id1) = $LB("col11", "col21", "col31")
Set ^t(id2) = $LB("col12", "col22", "col32")
```

Какво е интересно, не е трудно да се направи нещо подобно на вторичните индекси в релационни бази данни. Нека наречем тези структури индексни глобали. Индексният глобал е помощно дърво за бързо търсене по полета, които не са част от първичния ключ на основния глобал. За да се заполни и използва, е нужно да се напише допълнителен код.

Нека създадем индексен глобал по първата колона.

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

Сега, за бързо търсене на информация по първата колона, трябва да погледнем в глобала ^i и да намерим първичните ключове (id), съответстващи на желаната стойност на първата колона.

При вмъкване на стойност можем веднага да създаваме както стойността, така и индексните глобали по нужните полета. А за надеждност можем да обвием всичко в транзакция.

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

Подробности как да направите на M таблици на глобалите, емулация на вторични индекси.

Таблиците ще работят също толкова бързо, колкото и в традиционните бази данни (или дори по-бързо), ако функциите за вмъкване/обновяване/изтриване на редове се напишат на COS/M и се компилират.Твърдението проверявах чрез тестове на масивни INSERT и SELECT в една двуколонна таблица, включително с използване на командите TSTART и TCOMMIT (транзакции).

По-сложни сценарии с конкурентен достъп и паралелни транзакции не бяха тествани.

Без използване на транзакции скоростта на вмъкванията беше 778 361 вмъквания/секунда при един милион стойности.
При 300 милиона стойности — 422 141 вмъквания/секунда.

При използване на транзакции — 572 082 вмъквания/секунда за 50М вмъквания. Всички операции бяха проведени от компилиран M-код.
Жестоките дискове са обикновени, не SSD. RAID5 с Write-back. Процесор Phenom II 1100T.

За аналогично тестване на SQL базата е необходимо да напишете хранима процедура, която в цикъл ще прави вмъквания. При тестването на MySQL 5.5 (хранилище InnoDB) по този метод получих цифри не по-високи от 11К вмъквания в секунда.
Да, реализирането на таблици на глобали изглежда по-сложно, отколкото в релационните бази данни. Затова индустриалните бази данни на глобали предлагат SQL достъп за опростяване на работата с таблични данни.

Всъщност, ако схемата на данните не се променя често, скоростта на вмъкване не е критична и цялата база може да се представи лесно под формата на нормализирани таблици, по-удобно е да се работи именно със SQL, тъй като той осигурява по-високо ниво на абстракция.

В този специален случай исках да покажа, че глобалите могат да действат като конструктор за създаване на други бази данни. Като асемблер, на който може да се напишат други езици. А ето и примери как могат да се създадат аналози на глобалите key-value, списъци, множества, таблични, документо-ориентирани бази данни.

Ако е необходимо да се създаде нестандартна база данни с минимални усилия, е добре да се погледне към глобалите.

3.3 Специален случай 3. Двуниво дърво, при което всеки възел на второ ниво има фиксиран брой клони.

Вероятно се досещате: това е алтернативна реализация на таблиците на глобали. Нека сравним тази реализация с предишната.

Таблици на двунивно дърво спрямо еднонивно дърво.

Минуси
Плюсове

По-бавни при вмъкване, тъй като е необходимо да се зададе брой на възлите равен на броя на колоните.
По-голямо задание на дисковото пространство. Понеже глобалните индекси (в смисъл на индекси в масиви) с имената на колоните заемат място на диска и се дублират за всеки ред.

По-бърз достъп до стойностите на отделните колони, тъй като не е необходимо да се парсира реда. Според моите тестове е по-бързо с 11,5% при 2 колони и дори по-бързо при повече колони.
По-лесна смяна на данните.
По-ясен код.

Изход: На почитателите. Понеже скоростта е едно от най-ключовите предимства на глобалите, почти няма смисъл да се използва тази реализация, тъй като вероятно ще работи по-бавно от таблиците в релационни бази данни.

3.4 Общ случай. Дървета и подредени дървета.

Всяка структура от данни, която може да бъде представена под формата на дърво, се вписва прекрасно в глобалите.

3.4.1 Обекти с подобекти.

Това е област на традиционното приложение на глобалите. В медицинската сфера съществува огромно количество заболявания, лекарства, симптоми и методи на лечение. Създаването на таблица с милион полета за всеки пациент е нерационално. Особено когато 99% от полетата ще бъдат празни.

Представете си SQL БД от таблици: "пациент" ~ 100 000 полета, "Лекарство" — 100 000 полета, "Терапия" — 100 000 полета, "Осложнения" — 100 000 полета и т.н. Може да се създаде и БД от хиляди таблици, всяка за определен тип пациент (а те могат да се припокриват!), лечение, лекарство и хиляди таблици за връзките между тези таблици.

Глобалите са идеално пригодени за медицината, тъй като позволяват да се създаде точно описание на историята на заболяването на всеки пациент, различни терапии и действия на лекарствата, под формата на дърво, без да се харчи излишно дисково пространство за празни колони, както би било в релационния случай.

С глобалите е удобно да се създадат БД с данни за хората,, когато е важно да се накопичи и систематизира максимално разнообразна информация за клиента. Това е търсено в медицината, банковата сфера, маркетинга, архивната работа и други области.

.
Безусловно, в SQL също може да се емулира дърво с няколко таблици (EAV, 1,2,3,4,5,6,7,8,9,10), но това е съществено по-сложно и ще работи по-бавно. По същество ще трябва да се напише глобален, работещ на таблици и да се скрие цялата работа с таблиците зад слой на абстракция. Грешно е да се емулира по-нискостепенна технология (глобали) с средства на по-високостепенна (SQL). Неетично е.

Не е тайна, че промяната на схемата на данните в гигантски таблици (ALTER TABLE) може да отнеме значително време. MySQL, например, извършва ALTER TABLE ADD|DROP COLUMN като пълно копиране на информацията от старата в новата таблица (тествах двигатели MyISAM, InnoDB). Което може да блокира работната база с милиарди записи за дни, ако не и за седмици.

Промяната на структурата на данните, ако използваме глобали, не ни струва нищо. По всяко време можем да добавим нови свойства към всеки обект, на всяко ниво в йерархията. Промените, свързани с преименуването на клонове, могат да се стартират във фонов режим на работеща база данни.

Затова, когато става въпрос за съхранение на обекти с огромно количество незадължителни свойства, глобалите са отличен избор.

Освен това, напомням, достъпът до всяко от свойствата е мигновен, тъй като в глобала всички пътища представляват B-tree.

Базите данни на глобали, в общия случай, са разновидност на документно-ориентирани бази данни, с възможност за съхранение на йерархична информация. Поради това в сферата на съхранение на медицински картони, глобалите могат да конкурират документно-ориентираните бази данни. Но все пак, това не е съвсем същото.Вземете за сравнение, например, MongoDB. В тази сфера, тя губи пред глобалите поради следните причини:

Размерът на документа. Единицата за съхранение е текст във формат JSON (по-точно BSON) с максимален обем около 16MB. Ограничението е направено специално, за да не забавя JSON-базата при парсене, ако съдържа огромен JSON-документ, а след това се извършват запитвания по полета. В този документ трябва да бъде концентрирана цялата информация за пациента. Всички знаем колко обемисти могат да бъдат картите на пациентите. Максималният размер на картата от 16MB веднага поставя бариера за пациенти, чиито картони включват файлове от МРТ, сканирания на рентгенография и други изследвания. В една клонка на глобала обаче може да се съхранява информация на гигабайти и терабайти. В принципе, на това може да се сложи край, но аз ще продължа.
Време на съзнание/промяна/изтриване на нови свойства в картата на пациента. Тази БД трябва да зареди цялата карта в паметта (това е голям обем!), да парсира BSON, да добави/промени/изтрие нов възел, да обнови индексите, да опакова в BSON и да запази на диск. Глобалът обаче просто трябва да се обърне към конкретното свойство и да извърши операции с него.
Бързина на достъп до отделни свойства. При множество свойства в документа и многостепенната му структура достъпът до отделните свойства ще бъде по-бърз, тъй като всеки път в глобалът е B-tree. В BSON обаче ще трябва линейно да парсираме документа, за да намерим нужното свойство.

3.3.2 Асоциативни масиви

Асоциативните масиви (дори и с вложени масиви) се вписват отлично в глобалите. Например такъв масив от PHP ще се изобрази в първата картинка 3.3.1.

$a = array(
  "name" => "Vince Medvedev",
  "city" => "Moscow",
  "threatments" => array(
    "surgeries" => array("апендектомия", "биопсия"),
    "radiation" => array("гама", "рентгенови лъчи"),
    "physiotherapy" => array("коляно", "рамо")
  )
);

3.3.3 Йерархични документи: XML, JSON

Също така лесно се съхраняват в глобалите. За съхранение можем да разложим по различни начини.

XML
Най-простият начин за разлагане на XML в глобали е, когато в възлите съ храним атрибутите на таговете. А ако бърз достъп до атрибутите на таговете е необходим, можем да ги изнесем в отделни клонове.

<note id="5">
<to>Вася</to>
<from>Светлина</from>
<heading>Напомняне</heading>
<body>Обади ми се утре!</body>
</note>

На COS това ще съответства на кода:

Set ^xml("note")="id=5"
Set ^xml("note","to")="Саша"
Set ^xml("note","from")="Света"
Set ^xml("note","heading")="Напомняне"
Set ^xml("note","body")="Позвони ми утре!"

Забележка: За XML, JSON, асоциативни масиви могат да се измислят много различни начини на представяне в глобалите. В този случай не отразихме реда на вложените тагове в тага note. В глобалът ^xml вложените тагове ще се отразяват в азбучен ред. За строго отразяване на реда можем да използваме, например, такова представяне:

JSON.
На първата картинка от раздел 3.3.1 е показано отразяването на този JSON-документ:

var document = {
  "name": "Vince Medvedev",
  "city": "Moscow",
  "threatments": {
    "surgeries": ["апендектомия", "биопсия"],
    "radiation": ["гама", "рентгенови лъчи"],
    "physiotherapy": ["коляно", "рамо"]
  },
};

3.3.4 Идентични структури, свързани с йерархични отношения

Примери: структура на търговски офиси, разположение на хора в MLM структура, база на дебютите в шахматите.

База на дебютите. Можете да използвате оценка на силата на хода като индекс на узела в глобала. Тогава, за да изберете най-силния ход, ще е достатъчно да изберете клон с най-високото тегло. В глобала всички клони на всеки уровень ще бъдат подредени по сила на хода.

Структура на офисите за продажби, структура на хората в MLM. В узлите може да се съхраняват кеширащи стойности, отразяващи характеристиките на цялото поддърво. Например, обемът на продажбите на това поддърво. Във всеки момент можем да получим число, отразяващо постиженията на всеки клон.

4. В какви случаи е най-изгодно да се използват глобали

В първата колона са представени случаите, когато получавате значително предимство по отношение на скоростта при използване на глобали, а във втората, когато разработката или моделът на данни ще се опростят.

Скорост
Удобство при обработка/представяне на данни

Вмъкване [с автоматично сортиране на всеки уровень], [индексиране по главния ключ]
Изтриване на поддървета
Обекти с много вложени свойства, които изискват индивидуален достъп
Иерархична структура с възможност за преминаване през дъщерни клони с всякакви, дори несъществуващи
Преминаване през поддървета в дълбочина

Обекти/същности с огромно количество задължителни [и/или вложени] свойства/същности
Безсхемни данни (schema-less). Когато нови свойства често могат да се появят, а старите да изчезнат.
Трябва да се създаде нестандартна база данни.
Бази на пътища и дървета на решения. Когато е удобно да се представят пътищата като дърво.
Изтриване на йерархични структури без използване на рекурсия

Продължение «Глобали — мечове-кладенци за съхранение на данни. Разредени масиви. Част 3».

Отказ: тази статия и моите коментари към нея са мое мнение и нямат отношение към официалната позиция на корпорацията InterSystems.

Източник: habr.com