Globals sind Schatztruhen zur Datenspeicherung. Bäume. Teil 2

Start — siehe Teil 1.

3. Variationen der Struktur bei der Verwendung von Globals

Eine Struktur wie ein geordnetes Baumdiagramm hat verschiedene spezielle Fälle. Betrachten wir die, die praktischen Nutzen bei der Arbeit mit Globals haben.

3.1 Spezialfall 1. Ein Knoten ohne Äste

Globals können nicht nur wie ein Array, sondern auch wie normale Variablen verwendet werden. Zum Beispiel als Zähler:

Set ^counter = 0  ; Zähler setzen
Set id=$Increment(^counter) ;  atomar inkrementieren

Dabei kann der Global, neben dem Wert, auch Äste besitzen. Das Eine schließt das Andere nicht aus.

3.2 Spezialfall 2. Ein Knoten und viele Äste

Im Grunde handelt es sich um eine klassische Key-Value-Datenbank. Wenn wir als Wert ein Tupel von Werten speichern, erhalten wir die ganz gewöhnliche Tabelle mit einem Primärschlüssel.

Um eine Tabelle in Globals zu realisieren, müssen wir selbst die Zeilen aus den Werten der Spalten bilden und sie dann im Global nach dem Primärschlüssel speichern. Um beim Auslesen die Zeile wieder in Spalten aufteilen zu können, können wir verwenden:

1. Trennzeichen.

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

2. ein striktes Schema, bei dem jedes Feld eine vordefinierte Anzahl von Bytes belegt, wie es auch in relationalen Datenbanken gemacht wird.
3. eine spezielle Funktion $LB (verfügbar in Cache), die eine Zeichenkette aus Werten erstellt.

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

Interessant ist, dass es auf globalen Variablen nicht schwierig ist, etwas Ähnliches wie sekundäre Indizes in relationalen Datenbanken zu erstellen. Wir nennen solche Strukturen Index-Globals. Ein Index-Global ist ein Hilfsbaum für eine schnelle Suche nach Feldern, die keine Bestandteile des Primärschlüssels des Hauptglobals sind. Um ihn zu füllen und zu nutzen, muss zusätzlicher Code geschrieben werden.

Lassen Sie uns einen Index-Global für die erste Spalte erstellen.

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

Jetzt müssen wir für eine schnelle Informationssuche in der ersten Spalte in den Globalen sehen ^i und die Primärschlüssel (id) finden, die dem gewünschten Wert der ersten Spalte entsprechen.

Beim Einfügen eines Wertes können wir sofort sowohl den Wert als auch die Index-Globals für die benötigten Felder erstellen. Zur Sicherheit verpacken wir das alles in eine Transaktion.

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

Details, wie man es in M macht Tabellen in Globalen, Emulation von Sekundärindizes.

Diese Tabellen arbeiten ebenso schnell wie in traditionellen DBs (oder sogar schneller), wenn die Funktionen zum Einfügen/Ändern/Löschen von Zeilen in COS/M geschrieben und kompiliert werden.Diese Aussage habe ich durch Tests mit massiven INSERT- und SELECT-Befehlen in einer zweispaltigen Tabelle überprüft, einschließlich der Nutzung von TSTART- und TCOMMIT-Befehlen (Transaktionen).

Komplexere Szenarien mit konkurrierendem Zugriff und parallelen Transaktionen wurden nicht getestet.

Ohne Nutzung von Transaktionen lag die Einfügeschwindigkeit bei einer Million Werten bei 778.361 Einfügungen/Sekunde.
Bei 300 Millionen Werten — 422.141 Einfügungen/Sekunde.

Bei der Nutzung von Transaktionen — 572.082 Einfügungen/Sekunde bei 50 Millionen Einfügungen. Alle Operationen wurden aus kompiliertem M-Code durchgeführt.
Es wurden gewöhnliche Festplatten verwendet, keine SSDs. RAID5 mit Write-back. Prozessor Phenom II 1100T.

Für vergleichbare Tests einer SQL-Datenbank muss eine gespeicherte Prozedur geschrieben werden, die in einer Schleife Einfügungen durchführt. Bei Tests mit MySQL 5.5 (InnoDB-Store) erhielt ich nicht mehr als 11.000 Einfügungen pro Sekunde.
Ja, die Implementierung von Tabellen in Global-DBs erscheint komplizierter als in relationalen Datenbanken. Daher bieten industrielle Datenbanken mit Global-DBs SQL-Zugriff, um die Arbeit mit tabellarischen Daten zu erleichtern.

Wenn das Datenschema also nicht häufig geändert wird, die Einfügeschwindigkeit nicht kritisch ist und die gesamte Datenbank leicht in normalisierte Tabellen dargestellt werden kann, ist es einfacher, mit SQL zu arbeiten, da es ein höheres Abstraktionsniveau bietet.

In diesem speziellen Fall wollte ich zeigen, dass Global-DBs als Baukästen zur Erstellung anderer Datenbanken dienen können.Wie ein Assembler, auf dem man andere Sprachen schreiben kann. Hier sind Beispiele, wie man in Global-DBs Entsprechungen schaffen kann für Key-Value, Listen, Mengen, Tabellen und dokumentenorientierte Datenbanken.

Wenn eine nicht standardmäßige Datenbank mit minimalem Aufwand erstellt werden soll, lohnt es sich, einen Blick auf Global-DBs zu werfen.

3.3 Spezialfall 3. Zweistufiger Baum, bei dem jeder Knoten der zweiten Ebene eine fixe Anzahl von Zweigen hat.

Sie haben wahrscheinlich erraten: Das ist eine alternative Implementierung von Tabellen in Global-DBs. Lassen Sie uns diese Implementierung mit der vorherigen vergleichen.

Tabellen in einem zweistufigen Baum vs. in einem einstufigen Baum.

Nachteile
Vorteile

1. Langsame Einfügung, da die Anzahl der zu installierenden Knoten der Anzahl der Spalten entsprechen muss.
2. Höherer Speicherplatzverbrauch. Da globale Indizes (in dem Sinne wie Array-Indizes) mit Spaltennamen Platz auf der Festplatte beanspruchen und für jede Zeile dupliziert werden.

1. Schnellerer Zugriff auf die Werte einzelner Spalten, da die Zeile nicht geparst werden muss. Laut meinen Tests ist der Zugriff auf 2 Spalten um 11,5% schneller, und bei einer höheren Anzahl von Spalten noch schneller.
2. Einfacherer Wechsel des Datenschemas.
3. Anschaulicherer Code.

Fazit: Für Liebhaber. Da Geschwindigkeit eines der wesentlichen Vorteile von Globals ist, macht es kaum Sinn, diese Implementierung zu nutzen, da sie wahrscheinlich nicht schneller als Tabellen in relationalen Datenbanken arbeitet.

3.4 Allgemeiner Fall. Bäume und geordnete Bäume.

Jede Datenstruktur, die als Baum dargestellt werden kann, eignet sich hervorragend für Globals.

3.4.1 Objekte mit Unterobjekten.

Dies ist ein traditioneller Anwendungsbereich für Globals. Im medizinischen Bereich gibt es eine riesige Anzahl an Krankheiten, Medikamenten, Symptomen und Behandlungsmethoden. Eine Tabelle mit einer Million Feldern für jeden Patienten zu erstellen, ist ineffizient. Zumal 99% der Felder leer bleiben würden.

Stellen Sie sich eine SQL-Datenbank aus Tabellen vor: „Patient“ ~ 100.000 Felder, „Medikament“ — 100.000 Felder, „Therapie“ — 100.000 Felder, „Komplikationen“ — 100.000 Felder usw. Man könnte auch eine Datenbank aus vielen Tausenden von Tabellen erstellen, jede für einen bestimmten Patiententyp (die sich überschneiden können!), Behandlung, Medikament und noch Tausende von Tabellen für die Verbindungen zwischen diesen Tabellen.

Globale Variablen sind ideal für die Medizin, da sie es ermöglichen, für jeden Patienten eine präzise Beschreibung seiner Krankengeschichte, verschiedener Therapien und Medikamentenwirkungen in Form eines Baums zu erstellen, ohne dabei überflüssigen Speicherplatz für leere Spalten zu verschwenden, wie es im relationalen Fall der Fall wäre.

Es ist bequem, mit globalen Variablen Datenbanken mit Informationen über Menschen zu erstellen,wenn es wichtig ist, eine maximale Vielfalt an Informationen über den Kunden zu sammeln und zu systematisieren. Dies ist in der Medizin, im Bankwesen, im Marketing, im Archivwesen und in anderen Bereichen gefragt.

.
Natürlich kann man auch mit SQL einen Baum nur mit wenigen Tabellen emulieren (EAV, 1,2,3,4,5,6,7,8,9,10), jedoch ist dies erheblich komplizierter und wird langsamer funktionieren. Im Grunde müsste man globale Datenstrukturen erstellen, die auf Tabellen basieren, und die gesamte Tabellenverarbeitung hinter einer Abstraktionsschicht verbergen. Es ist nicht korrekt, eine technologie mit niedrigerem Niveau (Globale) mit Mitteln einer höherstufigen Technologie (SQL) zu emulieren. Das ist ineffizient.

Es ist kein Geheimnis, dass die Änderung des Datenbankschemas auf riesigen Tabellen (ALTER TABLE) erheblich Zeit in Anspruch nehmen kann. MySQL zum Beispiel führt ALTER TABLE ADD|DROP COLUMN durch vollständiges Kopieren der Informationen aus der alten in die neue Tabelle aus (ich habe die Engines MyISAM und InnoDB getestet). Das kann eine Produktionsdatenbank mit Milliarden von Datensätzen für Tage, wenn nicht Wochen, lahmlegen.

Die Änderung der Datenstruktur, wenn wir globale Datenstrukturen verwenden, kostet uns nichts. Jederzeit können wir neue Eigenschaften zu jedem Objekt auf jeder Hierarchieebene hinzufügen, die wir benötigen. Änderungen, die das Umbenennen von Zweigen betreffen, können im Hintergrund auf einer aktiven Datenbank durchgeführt werden.


Deshalb sind globale Datenstrukturen eine ausgezeichnete Wahl, wenn es um die Speicherung von Objekten mit einer enormen Anzahl an optionalen Eigenschaften geht.

Ich erinnere daran, dass der Zugang zu jeder der Eigenschaften sofort erfolgt, da im Globalen alle Wege B-Bäume sind.

Datenbanken in den Globalen sind im Allgemeinen eine Art dokumentenbasierter Datenbanken, die die Speicherung hierarchischer Informationen ermöglichen. Daher können dokumentenbasierte Datenbanken im Bereich der Speicherung von medizinischen Akten mit den Globalen konkurrieren. Aber das ist immer noch nicht ganz das.Nehmen wir zum Vergleich beispielsweise MongoDB. In diesem Bereich verliert sie gegenüber den Globalen aus folgenden Gründen:

1. Die Größe des Dokuments. Die Speichereinheit ist ein Text im JSON-Format (genauer gesagt BSON) mit einem maximalen Volumen von etwa 16 MB. Diese Begrenzung wurde absichtlich eingeführt, um sicherzustellen, dass die JSON-Datenbank beim Parsen nicht ins Stocken gerät, wenn darin ein riesiges JSON-Dokument gespeichert wird und man später auf die Felder zugreift. In diesem Dokument sollte alle Informationen über den Patienten gesammelt werden. Wir wissen alle, wie dick die Patientenakten sein können. Die maximale Größe von 16 MB schließt Patienten aus, deren Krankheitsakte MRT-Dateien, Röntgenaufnahmen und andere Untersuchungen enthält. In einem Branch kann man jedoch Informationen im Umfang von Gigabytes und Terabytes speichern. An sich könnte man hier aufhören, aber ich werde fortfahren.
2. Zeit für Bewusstsein/Änderungen/Löschungen neuer Eigenschaften in der Patientenakte. Eine solche Datenbank muss die gesamte Akte in den Speicher laden (das ist ein großer Umfang!), das BSON parsen, einen neuen Knoten hinzufügen/ändern/löschen, die Indizes aktualisieren, in BSON packen und auf der Festplatte speichern. Dem Globalen reicht es jedoch, nur auf eine bestimmte Eigenschaft zuzugreifen und mit ihr zu arbeiten.
3. Zugriffsgeschwindigkeit auf einzelne Eigenschaften. Bei einer Vielzahl von Eigenschaften in einem Dokument und seiner mehrstufigen Struktur ist der Zugriff auf einzelne Eigenschaften schneller, da jeder Pfad im globalen Bereich ein B-Baum ist. In BSON hingegen muss das Dokument linear geparst werden, um die benötigte Eigenschaft zu finden.

3.3.2 Assoziative Arrays

Assoziative Arrays (auch mit verschachtelten Arrays) lassen sich hervorragend in globale Bereiche abbilden. Ein solches Array aus PHP wird in der ersten Abbildung 3.3.1 dargestellt.

$a = array(
  "name" => "Vince Medvedev",
  "city" => "Moskau",
  "threatments" => array(
    "surgeries" => array("Apendektomie", "Biopsie"),
    "radiation" => array("Gamma", "Röntgen"),
    "physiotherapy" => array("Knie", "Schulter")
  )
);

3.3.3 Hierarchische Dokumente: XML, JSON

Lassen sich ebenfalls leicht in globalen Bereichen speichern. Für die Speicherung können verschiedene Anordnungen verwendet werden.

XML
Der einfachste Weg, XML in globale Bereiche zu gliedern, besteht darin, die Attribute der Tags in den Knoten zu speichern. Wenn ein schneller Zugriff auf die Tag-Attribute erforderlich ist, können wir diese in separate Zweige auslagern.

<note id="5">
<to>Vasya</to>
<from>Licht</from>
<heading>Erinnerung</heading>
<body>Ruf mich morgen an!</body>
</note>

Im COS entspricht dies dem folgenden Code:

Set ^xml("note")="id=5"
Set ^xml("note","to")="Sasha"
Set ^xml("note","from")="Sveta"
Set ^xml("note","heading")="Erinnerung"
Set ^xml("note","body")="Ruf mich morgen an!"

Hinweis: Für XML, JSON und assoziative Arrays gibt es viele verschiedene Möglichkeiten, sie in Globals darzustellen. In diesem Fall haben wir die Reihenfolge der verschachtelten Tags im Tag note nicht reflektiert. In der Globale. ^xml Verschachtelte Tags werden alphabetisch angezeigt. Für eine strikte Reflektion der Reihenfolge kann beispielsweise diese Darstellung verwendet werden:

JSON.
Im ersten Bild aus Abschnitt 3.3.1 wird die Darstellung dieses JSON-Dokuments gezeigt:

var document = {
  "name": "Vince Medvedev",
  "city": "Moscow",
  "threatments": {
    "surgeries": ["Apedektomie", "Biopsie"],
    "radiation": ["Gamma", "Röntgen"],
    "physiotherapy": ["Knie", "Schulter"]
  },
};

3.3.4 Gleiche Strukturen mit hierarchischen Beziehungen

Beispiele: Struktur von Verkaufsbüros, Anordnung von Personen in einer MLM-Struktur, Datenbank von Schacheröffnungen.

Datenbank von Eröffnungen. Als Wert des Knoteninex im Global kann die Bewertung der Zugstärke verwendet werden. Dann reicht es aus, den Ast mit dem höchsten Gewicht zu wählen, um den stärksten Zug auszuwählen. In der Global werden alle Äste auf jeder Ebene nach Zugstärke sortiert.

Struktur von Verkaufsbüros, Struktur der Menschen in MLM. In den Knoten können bestimmte zwischengespeicherte Werte gespeichert werden, die die Merkmale des gesamten Teilbaums widerspiegeln. Zum Beispiel das Verkaufsvolumen dieses Teilbaums. Zu jeder Zeit können wir eine Zahl abrufen, die die Erfolge eines beliebigen Zweigs darstellt.

4. In welchen Fällen ist die Verwendung von Globals am vorteilhaftesten?

In der ersten Spalte sind die Fälle aufgeführt, in denen Sie einen erheblichen Geschwindigkeitsgewinn durch die Verwendung von Globals erzielen, und in der zweiten, wann die Entwicklung oder das Datenmodell vereinfacht wird.

Geschwindigkeit
Komfort bei der Verarbeitung/Präsentation von Daten

1. Einfügen [mit automatischer Sortierung auf jeder Ebene], [indizierung nach dem Hauptschlüssel]
2. Entfernen von Teilbäumen
3. Objekte mit einer Vielzahl von verschachtelten Eigenschaften, die individuellen Zugriff benötigen
4. Hierarchische Struktur mit der Möglichkeit, untergeordnete Zweige von jedem, sogar nicht existierenden, aus zu durchlaufen
5. Durchlaufen von Teilbäumen in der Tiefe

1. Objekte/Entitäten mit einer riesigen Anzahl von optionalen [und/oder verschachtelten] Eigenschaften/Entitäten
2. Schemafreie Daten (schema-less). Wenn häufig neue Eigenschaften auftauchen und alte verschwinden können.
3. Es muss eine nicht standardisierte Datenbank erstellt werden.
4. Datenbank von Pfaden und Entscheidungsbäumen. Wenn Wege bequem in Form eines Baums dargestellt werden.
5. Entfernung von hierarchischen Strukturen ohne Rekursion

Fortsetzung „Globale Variablen — Speicher für Daten. Sparse Arrays. Teil 3“.

Haftungsausschluss: Dieser Artikel und meine Kommentare dazu spiegeln meine persönliche Meinung wider und stehen nicht im Zusammenhang mit der offiziellen Position der InterSystems Corporation.

Quelle: habr.com