Глобаль — мечі-кладенцы для зберігання даних. Дерева. Частина 2

Початок — див. частину 1.

3. Варіанти структур при використанні глобалів
Така структура як впорядкований дерево має різні приватні випадки. Розглянемо ті, які мають практичну цінність при роботі з глобаль.

3.1 Приватний випадок 1. Один вузол без гілок

Глобаль можна використовувати не тільки подібно масиву, але і як звичайні змінні. Наприклад як лічильник:

Set ^counter = 0 ; установка лічильника
Set id=$Increment(^counter) ; атомарний инкрементирование

При цьому глобал, крім значення, може ще мати ще й гілки. Одне не виключає другого.

3.2 Приватний випадок 2. Одна вершина і безліч гілок
Взагалі — це класична key-value база. А якщо в якості значення ми будемо зберігати кортеж значень, то отримаємо саму звичайну таблицю з первинним ключем.



Для реалізації таблиці на глобалах нам доведеться самим формувати рядки з значень колонок, а потім зберігати їх в глобал по первинному ключу. Щоб при зчитуванні було можливо розділити рядок знову на колонки можна використовувати:

  1. символи-роздільники.
    Set ^t(id1) = "col11/col21/col31"
    Set ^t(id2) = "col12/col22/col32"
  2. жорстку схему, за якою кожне поле займає заздалегідь певне число байт. Як і робиться в реляційних БД.
  3. спеціальну функцію $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) відповідні потрібного значення першої колонки.

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

СТОРІНКУ
Set ^t(id1) = $LB("col11", "col21", "col31")
Set^i("col11", id1) = 1
TCOMMIT

Подробиці як зробити на M таблиці на глобалах, емуляцію вторинних індексів.

Працювати такі таблиці будуть також швидко як і в традиційних БД (або навіть швидше), якщо функції вставки/оновлення/видалення рядків написати на COS/M і скомпілювати.

Так, реалізація таблиць на глобалах виглядає більш складною, ніж в реляційних БД. Тому промислові БД на глобалах мають SQL-доступ для спрощення роботи з табличними даними.

Взагалі, якщо схема даних не буде часто змінюватися, швидкість вставки некритична і всю базу можна легко представити у вигляді нормалізованих таблиць, то простіше працювати саме з SQL, так як він забезпечує більш високий рівень абстракції.
У цьому окремому випадку я хотів показати, що глобаль можуть виступати як конструктор для створення інших БД. Як асемблер, на якому можна написати інші мови. А ось приклади, як можна створити на глобалах аналоги key-value, списків, множин, табличних, документо-орієнтованих БД.
Якщо потрібно створити якусь нестандартну БД мінімальними зусиллями, то варто поглянути в бік глобалів.

3.3 Приватний випадок 3. Дворівневе дерево, біля кожного вузла другого рівня фіксоване число гілок
Ви, напевно, здогадалися: це альтернативна реалізація таблиць на глобалах. Порівняємо цю реалізацію з попередньою.
Таблиці на дворівневому дереві vs. на однорівневому дереві.
Мінуси Плюси
  1. Повільніше на вставку і видалення, так як потрібно встановлювати/видаляти число вузлів рівне числу стовпців.
  2. Більше витрата дискового простору. Так як індекси глобала (в розумінні як індекси у масивів) з назвами колонок займають місце на диску і дублюються для кожного рядка.

  1. Швидше доступ до значень окремих колонок, так як не потрібно парсити рядок. За моїми тестів швидше на 11,5% на 2-х колонках і більше на більшому числі колонок.
  2. Простіше міняти схему даних

  3. Наочніше код
Висновок: на любителя. Оскільки швидкість — одне з ключових переваг глобалів, то майже немає сенсу використовувати цю реалізацію, так як вона швидше за все буде працювати не швидше таблиць реляційних базах даних.

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. У цій сфері вона програє глобаль з причин:

  1. Розмір документа. Одиницею зберігання є текст у форматі JSON (точніше BSON) максимального обсягу близько 16МБ. Обмеження зроблено спеціально, щоб JSON-база не гальмувала при парсингу, якщо в ній збережуть величезний JSON-документ, а потім будуть звертатися до нього по полях. В цьому документі повинна бути зосереджена вся інформація про пацієнта. Ми всі знаємо якими товстими можуть бути картки пацієнтів. Максимальний розмір карти в 16МБ відразу ставить хрест на пацієнтах, що в карту хвороб яких включені файли МРТ, скани ренгенографія та інших досліджень. В однієї гілки глобал ж можна мати інформацію на гігабайти і терабайти. В принципі на цьому можна поставити крапку, але я продовжу.
  2. Час свідомості/зміни/видалення нових властивостей в карті пацієнта. Така БД повинна вважати в пам'ять всю карту цілком (це великий обсяг!), розпарсити BSON, внести/змінити/видалити новий вузол, оновити індекси, запакувати в BSON, зберегти на диск. Глобалу ж достатньо лише звернутися до конкретного властивості і провести з ним маніпуляції.
  3. Швидкість доступу до окремих властивостей. При безлічі властивостей в документі та його багаторівневої структурі доступ до окремим властивостям буде швидше за рахунок того, що кожний шлях в глобале це B-tree. У BSON ж доведеться лінійно розпарсити документ, щоб знайти потрібну властивість.

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

Асоціативні масиви (навіть з вкладеними масивами) прекрасно лягають на глобаль. Наприклад такий масив PHP відобразиться в першу картинку 3.3.1.

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


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",
"центр": "Moscow",
"threatments": {
"surgeries": ["apedicectomy", "biopsy"],
"radiation": ["gamma","x-rays"],
"physiotherapy": ["knee", "shoulder"]
},
};


3.3.4 Однакові структури, пов'язані ієрархічними відносинами

Приклади: структура офісів продажів, розташування людей в МЛМ-структурі, база дебютів у шахах.

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



Структура офісів продажів, структура людей в МЛМ. В вузлах можна зберігати якісь кешуючі значення відображають характеристики всього піддерева. Наприклад, обсяг продажів даного піддерева. У будь-який момент ми можемо отримати цифру, яка відображає досягнення будь-якої гілки.



4. В яких випадках найбільш вигідно використовувати глобаль
У першій колонці представлені випадки, коли ви отримаєте суттєвий виграш у швидкості при використанні глобалів, а в другій коли спроститься розробка або модель даних.
Швидкість Зручність обробки/представлення даних
  1. Вставка [з автоматичною сортуванням на кожному рівні], [індексуванням по головному ключу]
  2. Видалення піддерев

  3. Об'єкти з масою вкладений властивостей, до яких потрібен індивідуальний доступ
  4. Ієрархічна структура з можливістю обходу дочірніх гілок з будь-якої, навіть не існуючої
  5. Обхід піддерев в глибину
  1. Об'єкти/сутності з величезною кількістю необов'язкових [та/або вкладених] властивостей/сутностей
  2. Безсхемные дані (schema-less). Коли часто можуть з'являтися нові властивості і зникати старі.

  3. Потрібно створити нестандартну БД.
  4. Бази шляхів і дерева рішень. Коли шляху зручно представляти у вигляді дерева.
  5. Видалення ієрархічних структур без використання рекурсії
Планується продовження «Глобаль — мечі-кладенцы для зберігання даних. Зріджені масиви. Частина 3»

Disclaimer: дана стаття і мої коментарі до неї є моєю думкою і не мають відношення до офіційної позиції корпорації InterSystems.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.