Globals – Schätze zur Datenspeicherung. Bäume. Teil 2

Start — siehe Teil 1.

3. Strukturvarianten bei der Verwendung von Globals

Eine strukturierte Form wie ein geordnetes Baumdiagramm hat verschiedene spezifische Fälle. Lassen Sie uns die betrachten, die praktische Bedeutung bei der Arbeit mit Globals haben.

3.1 Spezifischer Fall 1. Ein Knoten ohne Zweige

Globals können nicht nur wie Arrays verwendet werden, sondern auch wie gewöhnliche Variablen. Beispielsweise als Zähler:

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

Dabei kann der Global neben dem Wert auch Zweige haben. Das eine schließt das andere nicht aus.

3.2 Spezifischer Fall 2. Ein Gipfel und viele Zweige

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

Um eine Tabelle in Globals zu implementieren, müssen wir die Zeilen selbst aus den Werten der Spalten bilden und sie dann im Global unter dem Primärschlüssel speichern. Damit beim Lesen die Zeile wieder in Spalten getrennt werden kann, kann man Folgendes verwenden:

1. Trennzeichen.

   Set ^t(id1) = "col11/kol21/kol31"
   Set ^t(id2) = "col12/kol22/kol32"

2. ein strenges Schema, bei dem jedes Feld eine vorher festgelegte Anzahl von Bytes占.
3. eine spezielle Funktion $LB (vorhanden in Cache), die einen String aus Werten erstellt.

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

Interessanterweise ist es nicht schwer, in Globals etwas Ähnliches wie sekundäre Indizes in relationalen Datenbanken zu erstellen. Nennen wir solche Strukturen Index-Globals. Ein Index-Global ist ein Hilfsbaum für eine schnelle Suche nach Feldern, die nicht Teil des Primärschlüssels des Hauptglobals sind. Für seine Füllung und Nutzung 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 im Global ^i nach den Primärschlüsseln (id) suchen, die dem gewünschten Wert der ersten Spalte entsprechen.

Beim Einfügen eines Wertes können wir sofort den Wert und die Index-Globals für die erforderlichen Felder erstellen. Zur Sicherheit wickeln wir das Ganze in eine Transaktion ein.

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

Details, wie man in M Tabellen in Globals, sekundäre Indizes emulieren.

Solche Tabellen werden ebenso schnell arbeiten wie in traditionellen Datenbanken (oder sogar schneller), wenn die Funktionen für das Einfügen, Aktualisieren und Löschen von Zeilen in COS/M geschrieben und kompiliert werden.Diese Aussage habe ich mit Tests zu massiven INSERT- und SELECT-Operationen in einer zweispaltigen Tabelle überprüft, einschließlich der Verwendung von TSTART- und TCOMMIT-Befehlen (Transaktionen).

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

Ohne die Verwendung von Transaktionen lag die Geschwindigkeit der Inserts bei einer Million Werten bei 778.361 Inserts/Sekunde.
Bei 300 Millionen Werten waren es 422.141 Inserts/Sekunde.

Bei Verwendung von Transaktionen waren es 572.082 Inserts/Sekunde für 50 Millionen Inserts. Alle Operationen wurden aus dem kompilierten M-Code durchgeführt.
Es wurden normale Festplatten verwendet, keine SSDs. RAID5 mit Write-back. Prozessor Phenom II 1100T.

Für ein ähnliches Testen einer SQL-Datenbank muss ein gespeicherter Prozess geschrieben werden, der wiederholt Inserts durchführt. Bei einem Test mit MySQL 5.5 (InnoDB-Speicher) erhielt ich nach dieser Methode nicht mehr als 11K Inserts pro Sekunde.
Ja, die Implementierung von Tabellen in Globals sieht komplizierter aus als in relationalen Datenbanken. Daher haben industrielle Datenbanken in Globals SQL-Zugriff zur Vereinfachung der Arbeit mit Tabellendaten.

Generell, wenn sich das Datenschema nicht oft ändert, die Insertgeschwindigkeit nicht kritisch ist und die gesamte Datenbank leicht in normalisierten 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 Globals als Konstruktor zur Erstellung anderer Datenbanken dienen können.. Wie ein Assemblersprachen, in dem man andere Sprachen schreiben kann. Und hier sind Beispiele, wie man in Globals Analogien erstellen kann. key-value, Listen, Mengen, Tabellen, dokumentenorientierte Datenbanken.

Wenn man eine nicht standardisierte Datenbank mit minimalem Aufwand erstellen muss, sollte man einen Blick auf Globals werfen.

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

Sie haben wahrscheinlich erraten: dies ist eine alternative Implementierung von Tabellen in Globals. Lassen Sie uns diese Implementierung mit der vorherigen vergleichen.

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

Nachteile
Vorteile

1. Langsame Einfügungen, da die Anzahl der Knoten gleich der Anzahl der Spalten festgelegt werden muss.
2. Mehr Speicherplatz. Da die globalen Indizes (im Sinne von Indizes in Arrays) mit den 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 es 11,5 % schneller bei 2 Spalten und noch schneller bei einer größeren Anzahl von Spalten.
2. Einfachere Änderung des Datenschemas
3. Anschaulicherer Code

Ausgabe: Für Liebhaber. Da Geschwindigkeit eines der Hauptmerkmale von Globals ist, macht es kaum Sinn, diese Implementierung zu verwenden, da sie wahrscheinlich nicht schneller als Tabellen in relationalen Datenbanken funktioniert.

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

Jede Datenstruktur, die als Baum dargestellt werden kann, passt hervorragend zu Globals.

3.4.1 Objekte mit Unterobjekten

Dies ist der traditionelle Anwendungsbereich von Globals. Im medizinischen Bereich gibt es eine riesige Anzahl von Krankheiten, Medikamenten, Symptomen und Behandlungsmethoden. Für jeden Patienten eine Tabelle mit Millionen von Feldern zu erstellen, ist unvernünftig. 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 DB aus vielen Tausend Tabellen erstellen, jede für einen bestimmten Patiententyp (und die können sich überschneiden!), Behandlungen, Medikamente und noch Tausende von Tabellen für die Beziehungen zwischen diesen Tabellen.

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

Mit Globals ist es bequem, Datenbanken mit Informationen über Menschen zu erstellen, wenn es wichtig ist, eine Vielzahl von 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 mit SQL auch Bäume mit nur wenigen Tabellen emulieren (EAV, 1,2,3,4,5,6,7,8,9,10), jedoch ist das erheblich komplizierter und wird langsamer funktionieren. Im Grunde müsste man globale Funktionen schreiben, die auf Tabellen basieren, und die gesamte Arbeit mit den Tabellen hinter einer Abstraktionsschicht verbergen. Man sollte nicht versuchen, eine technologie mit niedrigem Niveau (Globalvariablen) mit höheren Mitteln (SQL) zu emulieren. Es ist unpraktisch.

Es ist kein Geheimnis, dass das Ändern des Datenmodells in riesigen Tabellen (ALTER TABLE) viel Zeit in Anspruch nehmen kann. MySQL beispielsweise führt ALTER TABLE ADD|DROP COLUMN durch, indem es die Informationen aus der alten in die neue Tabelle vollständig kopiert (ich habe die Engines MyISAM, InnoDB getestet). Das kann eine Produktionsdatenbank mit Milliarden von Einträgen tage- oder sogar wochenlang zum Stillstand bringen.

Die Änderung der Datenstruktur, wenn wir globale Variablen verwenden, kostet uns nichts. Jederzeit können wir neue erforderliche Eigenschaften zu jedem Objekt auf jeder Hierarchieebene hinzufügen. Änderungen, die mit der Umbenennung von Zweigen verbunden sind, können im Hintergrund auf einer aktiven DB ausgeführt werden.


Daher ist es, wenn es darum geht, Objekte mit einer riesigen Anzahl optionaler Eigenschaften zu speichern, eine globale Variable eine ausgezeichnete Wahl.

Außerdem kann ich daran erinnern, dass der Zugriff auf jede dieser Eigenschaften sofort ist, da in der globalen Variable alle Wege als B-Baum dargestellt werden.

Datenbanken, die auf globalen Variablen basieren, sind im Allgemeinen eine Art dokumentenorientierte DB, die die Speicherung hierarchischer Informationen ermöglicht. Daher können in dem Bereich der Speicherung von medizinischen Akten globale Variablen mit dokumentenorientierten Datenbanken konkurrieren. Aber es ist dennoch nicht ganz das.Nehmen wir zum Vergleich MongoDB. In diesem Bereich verliert es gegen globale Variablen aus folgenden Gründen:

1. Größe des Dokuments. Die Speichereinheit ist ein Text im JSON-Format (genauer gesagt BSON) mit einer maximalen Größe von etwa 16MB. Diese Beschränkung wurde absichtlich festgelegt, damit die JSON-Datenbank beim Parsen nicht verlangsamt, wenn sie ein riesiges JSON-Dokument speichert und später darauf nach Feldern zugreift. In diesem Dokument muss alle Informationen über den Patienten konzentriert sein. Wir alle wissen, wie dick Patientenakten sein können. Die maximale Größe von 16MB für eine Akte schließt Patienten aus, deren Krankengeschichte Dateien von MRTs, Röntgenaufnahmen und anderen Studien umfasst. In einem Zweig der globalen Variablen kann man jedoch Informationen in Gigabyte und Terabyte haben. Prinzipiell könnte man hier einen Punkt setzen, aber ich werde fortfahren.
2. Zeit der Bewusstseinsänderung/Löschung neuer Eigenschaften in der Patientenkarte. Eine solche Datenbank muss die gesamte Karte in den Speicher laden (das ist ein großes Volumen!), BSON parsen, einen neuen Knoten hinzufügen/ändern/löschen, Indizes aktualisieren, in BSON verpacken und auf die Festplatte speichern. Dem Globalen reicht es, auf eine bestimmte Eigenschaft zuzugreifen und mit ihr zu arbeiten.
3. Zugriffszeite auf einzelne Eigenschaften. Bei vielen Eigenschaften in einem Dokument und seiner mehrstufigen Struktur wird der Zugriff auf einzelne Eigenschaften schneller sein, da jeder Pfad im Globalen 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 (sogar mit verschachtelten Arrays) lassen sich hervorragend in Globals abbilden. So wird beispielsweise ein solches Array aus PHP im ersten Bild 3.3.1 dargestellt.

$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 Hierarchische Dokumente: XML, JSON

Auch sie lassen sich leicht in Globals speichern. Es gibt viele Möglichkeiten, sie zu strukturieren.

XML
Der einfachste Weg, XML in Globals abzubilden, ist, die Attribute der Tags in den Knoten zu speichern. Wenn schneller Zugriff auf die Attribute erforderlich ist, können wir sie in separate Äste auslagern.

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

Auf 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, assoziative Arrays lassen sich viele verschiedene Wege zur Darstellung in Globals erfinden. In diesem Fall haben wir die Reihenfolge der verschachtelten Tags im Tag note nicht abgebildet. Im Globalen ^xml werden verschachtelte Tags alphabetisch sortiert. Um die Reihenfolge genau widerzuspiegeln, kann beispielsweise eine solche 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": ["apedicectomy", "biopsy"],
    "radiation": ["gamma", "x-rays"],
    "physiotherapy": ["knee", "shoulder"]
  },
};

3.3.4 Gleiche Strukturen, die durch hierarchische Beziehungen verbunden sind

Beispiele: Struktur von Verkaufsbüros, Positionierung von Personen in einer MLM-Struktur, Datenbank von Eröffnungen im Schach.

Eröffnungsdatenbank. Man kann die Bewertung der Zugstärke als Indexwert für die Globals verwenden. Um dann den stärksten Zug auszuwählen, reicht es aus, den Zweig mit dem höchsten Gewicht zu wählen. In den Globals werden alle Zweige auf jeder Ebene nach Zugstärke sortiert.

Struktur der Verkaufsbüros, Struktur der Personen im MLM. In den Knoten können bestimmte Cache-Werte gespeichert werden, die die Eigenschaften des gesamten Unterbaums widerspiegeln. Zum Beispiel das Verkaufsvolumen dieses Unterbaums. Jederzeit können wir eine Zahl erhalten, die die Erfolge eines beliebigen Zweigs widerspiegelt.

4. In welchen Fällen ist es am vorteilhaftesten, Globals zu verwenden.

In der ersten Spalte werden die Fälle dargestellt, in denen Sie eine erhebliche Geschwindigkeitssteigerung durch die Verwendung von Globals erzielen, und in der zweiten Spalte, wenn die Entwicklung oder das Datenmodell vereinfacht wird.

Geschwindigkeit
Komfort bei der Verarbeitung/Vorstellung von Daten.

1. Einfügung [mit automatischer Sortierung auf jeder Ebene], [indiziert nach dem Hauptschlüssel].
2. Entfernung von Unterbäumen.
3. Objekte mit vielen verschachtelten Eigenschaften, zu denen ein individueller Zugriff erforderlich ist.
4. Hierarchische Struktur mit der Möglichkeit, Unterzweige von jedem beliebigen, sogar nicht existierenden, zu durchlaufen.
5. Tiefe Durchquerung von Unterbäumen.

1. Objekte/Entitäten mit einer riesigen Anzahl von optionalen [und/oder verschachtelten] Eigenschaften/Entitäten.
2. Schema-freie Daten. Wenn häufig neue Eigenschaften auftauchen und alte verschwinden können.
3. Es muss eine nicht standardmäßige DB erstellt werden.
4. Wegdatenbanken und Entscheidungshierarchien. Wenn es bequem ist, Wege in Form eines Baums darzustellen.
5. Entfernung hierarchischer Strukturen ohne Rekursion.

Fortsetzung „Globals – Datenspeicher-Magier. Sparse Arrays. Teil 3“.

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

Quelle: habr.com