Globale — Datenlager-Schwerter. Bäume. Teil 1

Die sogenannten globalen Datenbank-Schatten sind seit langem bekannt, doch nur wenige wissen, wie man sie effektiv einsetzt oder haben dieses Superwerkzeug nicht im Griff.

Wenn Sie die globalen Datenbanken für die Aufgaben nutzen, bei denen sie wirklich glänzen, können Sie außergewöhnliche Ergebnisse erzielen – sei es in der Leistung oder in der Vereinfachung der Lösungsfindung.1, 2).

Globale Datenbanken sind eine spezielle Art der Speicherung und Verarbeitung von Daten, die sich grundlegend von SQL-Tabellen unterscheidet. Sie wurden 1966 in der Programmiersprache M(UMPS) entwickelt. (eine evolutionäre Weiterentwicklung von Caché ObjectScript, kurz COS) und werden nach wie vor in medizinischen Datenbanken aktiv eingesetzt. Darüber hinaus haben sie in einigen anderen Bereichen, in denen Zuverlässigkeit und hohe Leistung erforderlich sind, wie z. B. Finanzwesen und Handel, Fuß gefasst. Cache ObjectScript, später COS) in medizinischen Datenbanken und werden dort immer noch aktiv verwendetModerne relationale Datenbanksysteme unterstützen mit globalen Datenbanken Transaktionen, Logging, Replikation und Partitionierung. Sie können zur Erstellung moderner, zuverlässiger, verteilter und schneller Systeme verwendet werden.

Globale Variablen in modernen DBMS unterstützen Transaktionen, Protokollierung, Replikation und Partitionierung. Das heißt, sie können moderne, zuverlässige, verteilte und schnelle Systeme bilden.

Globale schränken Sie nicht auf das relationale Modell ein. Sie bieten die Freiheit zur Entwicklung von Datensstrukturen, die auf spezifische Aufgaben optimiert sind. Für viele Anwendungen kann der sinnvolle Einsatz von Globals tatsächlich eine geheimnisvolle Waffe sein, die eine Leistung ermöglicht, von der Entwickler relationaler Anwendungen nur träumen können.

Globals können als Methode zur Datenspeicherung in vielen modernen Programmiersprachen eingesetzt werden, sowohl in höheren als auch in niedrigeren. Daher werde ich in diesem Artikel speziell auf Globals eingehen und nicht auf die Sprache, aus der sie ursprünglich stammen.

2. Wie Globals funktionieren

Lassen Sie uns zunächst klären, wie Globals funktionieren und wo ihre Stärken liegen. Globals können aus verschiedenen Perspektiven betrachtet werden. In diesem Teil des Artikels werden wir sie als Bäume betrachten. Oder als hierarchische Datenspeicher.

Vereinfachend gesagt, ist ein Global ein persistentes Array. Ein Array, das automatisch auf der Festplatte gespeichert wird.
Es ist kaum vorstellbar, dass es eine einfachere Methode zur Datenspeicherung gibt. Im Code (in den Sprachen COS/M) unterscheidet es sich lediglich durch ein Zeichen ^ vor dem Namen.

Um Daten im Globalen zu speichern, ist es nicht notwendig, SQL zu lernen; die Befehle dazu sind sehr einfach. Man kann sie in einer Stunde lernen.

Lassen Sie uns mit dem einfachsten Beispiel beginnen. Eine einlagige Struktur mit 2 Zweigen. Die Beispiele sind in COS geschrieben.

Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"

Beim Einfügen von Informationen in das Globale (Befehl Set) passieren automatisch 3 Dinge:

1. Die Daten werden auf der Festplatte gespeichert.
2. Indizierung. Das, was in Klammern steht, fungiert als Schlüssel (in englischer Literatur - 'subscript'), und rechts vom Gleichheitszeichen steht der Wert ('node value').
3. Sortierung. Die Daten werden nach dem Schlüssel sortiert. Bei der Durchquerung des Arrays wird das erste Element „Sergey Smith“ und das zweite „John Sidorov“ sein. Beim Abrufen der Benutzerliste aus dem Globalen verbringt die Datenbank keine Zeit mit der Sortierung. Zudem kann man die Ausgabe einer sortierten Liste anfordern, beginnend mit einem beliebigen Schlüssel, sogar mit einem nicht existierenden (die Ausgabe beginnt mit dem ersten tatsächlichen Schlüssel, der nach dem nicht existierenden folgt).

All diese Vorgänge erfolgen unglaublich schnell. Auf meinem Heimcomputer erreichte ich Werte von bis zu 750.000 Einfügungen/Sekunde in einem einzelnen Prozess. Auf Multicore-Prozessoren können die Werte sogar zehn Millionen Einfügungen/Sekunde erreichen.

Natürlich sagt die Einfügungsrate allein wenig aus. Man kann beispielsweise Informationen schnell in Textdateien schreiben – so sagt man funktioniert die Verarbeitung bei Visa. Doch im Fall von Globalen erhalten wir am Ende ein strukturiertes, indiziertes Speicherformat, mit dem man anschließend einfach und schnell umgehen kann.

• Die größte Stärke von Globalen ist die Geschwindigkeit, mit der neue Knoten eingefügt werden.
• Die Daten in Globalen sind immer indiziert. Ihr Zugriff erfolgt sowohl auf der gleichen Ebene als auch in die Tiefe des Baums immer schnell.

Fügen wir dem Globalen noch ein paar Zweige der zweiten und dritten Ebene hinzu.

Set ^a("+7926X", "city") = "Moskau"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36

Es ist offensichtlich, dass man auf der Basis von Globals mehrstufige Bäume erstellen kann. Der Zugriff auf jeden Knoten erfolgt nahezu sofort durch die automatische Indizierung beim Einfügen. Und auf jeder Ebene des Baumes sind alle Verzweigungen nach Schlüssel sortiert.

Wie zu sehen ist, können Informationen sowohl im Schlüssel als auch im Wert gespeichert werden. Die Gesamtlänge des Schlüssels (die Summe der Längen aller Indizes) kann bis zu 511 Bytes, und die Werte 3,6 MB für Caché betragen. Die Anzahl der Stufen im Baum (Anzahl der Dimensionen) beträgt 31.

Ein weiterer interessanter Punkt. Man kann einen Baum erstellen, ohne die Werte der Knoten der oberen Ebenen festzulegen.

Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3

Leere Kreise sind Knoten, denen kein Wert zugewiesen wurde.

Um Globals besser zu verstehen, vergleichen wir sie mit anderen Bäumen: mit Gartenbäumen und mit Bäumen der Dateisysteme.

Lassen Sie uns die Bäume auf Globals mit den uns am vertrautesten hierarchischen Strukturen vergleichen: mit normalen Bäumen, die in Gärten und Feldern wachsen, sowie mit Dateisystemen.

Wie wir sehen, befinden sich bei Gartenbäumen die Blätter und Früchte nur an den Enden der Äste.
In Dateisystemen wird die Information nur an den Enden der Äste gespeichert, die die vollständigen Namen der Dateien sind.

Hier ist die Datenstruktur des Globals.

Unterschiede:

1. Innere Knoten: Informationen im Global können in jedem Knoten gespeichert werden, nicht nur an den Enden der Äste.
2. Äußere Knoten: Im Global müssen die Werte an den Enden der Äste definiert sein, in Dateisystembäumen und Gartenbäumen jedoch nicht.

Was die inneren Knoten betrifft, so kann man sagen, dass die Struktur des Globals ein Übermengen der Struktur von Namensbäumen in Dateisystemen und Gartenbäumen ist. Das heißt, sie ist flexibler.

Im Allgemeinen stellt das Global dar einen geordneten Baum mit der Möglichkeit, Daten in jedem Knoten zu speichern..

Um das Funktionieren von Globals besser zu verstehen, stellen wir uns vor, was gewesen wäre, wenn die Entwickler von Dateisystemen einen Ansatz ähnlich dem der Globals zur Speicherung von Informationen verwendet hätten.

1. Wenn eine einzige Datei im Verzeichnis gelöscht wird, würde automatisch das Verzeichnis sowie alle übergeordneten Verzeichnisse, die nur dieses kürzlich gelöschte Verzeichnis enthalten, gelöscht.
2. Die Notwendigkeit von Verzeichnissen wäre entfallen. Es gäbe einfach Dateien mit Unterdateien und Dateien ohne Unterdateien. Verglichen mit einem normalen Baum würde jeder Ast zur Frucht werden.

   
   

3. Dateien wie README.txt könnten möglicherweise überflüssig werden. Alles, was über den Inhalt eines Verzeichnisses zu sagen wäre, könnte direkt in die Verzeichnisdatei geschrieben werden. Im Pfadnamen ist der Dateiname vom Verzeichnisnamen indistinguierbar, weshalb man sich auf Dateien allein beschränken könnte.
4. Die Geschwindigkeit beim Löschen von Verzeichnissen mit Unterverzeichnissen und Dateien würde erheblich steigen. Oft gab es auf Habré Artikel darüber, wie lange und mühsam es ist, Millionen von kleinen Dateien zu löschen (1, 2). Wenn man jedoch ein Pseudodateisystem auf Globalen erstellt, würde es Sekunden oder sogar Bruchteile davon in Anspruch nehmen. Bei meinem Test zum Löschen von Teilbäumen auf meinem Heimcomputer habe ich in 1 Sekunde zwischen 96-341 Millionen Knoten aus einem zweistufigen Baum auf einer HDD (nicht SSD) gelöscht. Hierbei handelt es sich um das Löschen eines Teils des Baums und nicht einfach um das Löschen einer gesamten Datei mit Globals.

Das Löschen von Teilbäumen ist eine weitere Stärke von Globals. Dafür ist keine Rekursion erforderlich. Es geschieht unglaublich schnell.

In unserem Baum könnte dies mit dem Befehl erfolgen Beenden.

Kill ^a("+7926X")

Um besser zu verstehen, welche Aktionen uns mit Globals zur Verfügung stehen, gebe ich eine kurze Übersicht.

Wichtige Befehle und Funktionen zur Arbeit mit Globals in COS

Set
Zweige bis zum Knoten einrichten (falls noch nicht bestimmt) und Knoteneigenschaft festlegen

Zusammenführen
Unterbaum kopieren

Beenden
Unterbaum löschen

ZKill
Wert eines bestimmten Knotens löschen. Der Unterbaum, der aus dem Knoten herausgeht, bleibt unberührt

$Query
Vollständige Durchquerung des Baumes mit Tiefensuche

$Order
Äste eines bestimmten Knotens durchlaufen

$Data
Überprüfung, ob der Knoten definiert ist

$Increment
Atomare Inkrementierung des Knotenwerts. Um Lese- und Schreibvorgänge zu vermeiden, für ACID. In letzter Zeit wird empfohlen, auf $Sequence

Danke für Ihre Aufmerksamkeit, wir stehen Ihnen für Fragen zur Verfügung.

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.

Fortsetzung Globals sind Schatztruhen zur Datenspeicherung. Bäume. Teil 2. Sie erfahren, welche Datentypen auf Globals angezeigt werden können und bei welchen Aufgaben sie die größten Vorteile bieten.

Quelle: habr.com