Les globals sont des épées au trésor pour stocker des données. Des arbres. Partie 2

Pour commencer - voir la partie 1.

3. Variantes de structures lors de l'utilisation de globales

Une structure telle qu’un arbre ordonné présente divers cas particuliers. Considérons ceux qui ont une valeur pratique lorsque l'on travaille avec des valeurs globales.

3.1 Cas particulier 1. Un nœud sans branches

Les variables globales peuvent être utilisées non seulement comme un tableau, mais également comme des variables normales. Par exemple, comme compteur :

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

Dans ce cas, le global, en plus de sa signification, peut aussi avoir des branches. L’un n’exclut pas l’autre.

3.2 Cas particulier 2. Un sommet et plusieurs branches

En général, il s’agit d’une base clé-valeur classique. Et si nous enregistrons un tuple de valeurs en tant que valeur, nous obtiendrons une table très ordinaire avec une clé primaire.

Pour implémenter une table sur les globales, nous devrons générer nous-mêmes des lignes à partir des valeurs des colonnes, puis les enregistrer dans la globale à l'aide de la clé primaire. Pour permettre de diviser à nouveau la chaîne en colonnes lors de la lecture, vous pouvez utiliser :

1. caractères délimiteurs.

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

2. un schéma rigide dans lequel chaque champ occupe un nombre prédéterminé d'octets. Comme cela se fait dans les bases de données relationnelles.
3. une fonction spéciale $LB (disponible dans le Cache), qui crée une chaîne de valeurs.

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

Fait intéressant, il n’est pas difficile d’utiliser des globaux pour faire quelque chose de similaire aux index secondaires dans les bases de données relationnelles. Appelons de telles structures des indices globaux. Un index global est un arbre auxiliaire permettant de rechercher rapidement des champs qui ne font pas partie de la clé primaire du global principal. Pour le remplir et l'utiliser, vous devez écrire du code supplémentaire.

Créons un index global sur la première colonne.

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

Maintenant, pour rechercher rapidement des informations dans la première colonne, nous devons examiner le contexte global. ^i et trouver les clés primaires (id) correspondant à la valeur souhaitée de la première colonne.

Lors de l'insertion d'une valeur, nous pouvons immédiatement créer à la fois la valeur et l'index global pour les champs requis. Et pour plus de fiabilité, intégrons le tout dans une transaction.

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

Détails sur la façon de le faire sur M tables sur les globales, émulation d'index secondaires.

De telles tables fonctionneront aussi rapidement que dans les bases de données traditionnelles (voire même plus rapidement) si les fonctions d'insertion/mise à jour/suppression de lignes sont écrites en COS/M et compilées.J'ai vérifié cette instruction avec des tests sur INSERT et SELECT en masse dans une table à deux colonnes, notamment en utilisant les commandes TSTART et TCOMMIT (transactions).

Je n'ai pas testé de scénarios plus complexes avec accès simultané et transactions parallèles.

Sans utiliser de transactions, le taux d'insertion était de 778 361 insertions/seconde par million de valeurs.
Avec 300 millions de valeurs - 422 141 insertions/seconde.

Lors de l'utilisation de transactions - 572 082 insertions/seconde pour 50 millions d'insertions. Toutes les opérations ont été effectuées à partir du code M compilé.
Les disques durs sont classiques, pas SSD. RAID5 avec réécriture. Processeur Phenom II 1100T.

Pour tester une base de données SQL de la même manière, vous devez écrire une procédure stockée qui effectuera des insertions en boucle. Lors du test de MySQL 5.5 (stockage InnoDB), en utilisant cette méthode, j'ai reçu des nombres ne dépassant pas 11 XNUMX insertions par seconde.
Oui, l'implémentation de tables sur des globales semble plus complexe que dans des bases de données relationnelles. Par conséquent, les bases de données industrielles globales disposent d'un accès SQL pour simplifier le travail avec des données tabulaires.

En général, si le schéma de données ne change pas fréquemment, que la vitesse d'insertion n'est pas critique et que l'ensemble de la base de données peut être facilement représenté sous forme de tableaux normalisés, il est alors plus facile de travailler avec SQL, car il offre un niveau d'abstraction plus élevé. .

Dans ce cas particulier, je voulais montrer que les globals peuvent agir comme un constructeur pour créer d'autres bases de données. Comme un assembleur dans lequel d'autres langages peuvent être écrits. Voici des exemples de la façon dont vous pouvez créer des analogues sur des variables globales bases de données clé-valeur, listes, ensembles, tabulaires et orientées document.

Si vous avez besoin de créer une sorte de base de données non standard avec un minimum d'effort, vous devriez alors vous tourner vers les globales.

3.3 Cas particulier 3. Arbre à deux niveaux, chaque nœud du deuxième niveau possède un nombre fixe de branches

Vous l'avez probablement deviné : il s'agit d'une implémentation alternative des tables sur les globales. Comparons cette implémentation avec la précédente.

Tables sur une arborescence à deux niveaux vs. sur un arbre à un seul niveau.

Moins
Avantages

1. Plus lent pour l'insertion, car vous devez définir le nombre de nœuds égal au nombre de colonnes.
2. Plus de consommation d'espace disque. Étant donné que les index globaux (entendus comme des index de tableau) avec des noms de colonnes occupent de l'espace disque et sont dupliqués pour chaque ligne.

1. Accès plus rapide aux valeurs des colonnes individuelles, car il n'est pas nécessaire d'analyser la chaîne. D'après mes tests, il est 11,5% plus rapide sur 2 colonnes et plus sur un plus grand nombre de colonnes.
2. Plus facile de modifier le schéma de données
3. Code plus clair

Conclusion: pas pour tout le monde. Étant donné que la vitesse est l'un des principaux avantages des variables globales, il ne sert à rien d'utiliser cette implémentation, car elle ne fonctionnera probablement pas plus rapidement que les tables des bases de données relationnelles.

3.4 Cas général. Arbres et arbres ordonnés

Toute structure de données pouvant être représentée sous forme d'arbre s'adapte parfaitement aux valeurs globales.

3.4.1 Objets avec sous-objets

C'est le domaine d'utilisation traditionnelle des globals. Dans le domaine médical, il existe un grand nombre de maladies, de médicaments, de symptômes et de méthodes de traitement. Il est irrationnel de créer un tableau avec un million de champs pour chaque patient. De plus, 99 % des champs seront vides.

Imaginez une base de données SQL de tables : « patient » ~ 100 000 champs, « Médecine » - 100 000 champs, « Thérapie » - 100 000 champs, « Complications » - 100 000 champs, etc. et ainsi de suite. Ou vous pouvez créer une base de données de plusieurs milliers de tables, chacune pour un type spécifique de patient (et elles peuvent se chevaucher !), des traitements, des médicaments et des milliers d'autres tables pour les connexions entre ces tables.

Les globales sont idéales pour la médecine, car elles vous permettent de créer pour chaque patient une description précise de ses antécédents médicaux, de ses diverses thérapies et de l'action des médicaments, sous la forme d'un arbre, sans gaspiller d'espace disque supplémentaire sur des colonnes vides, comme le ferait être le cas dans un cas relationnel.

En utilisant des variables globales, il est pratique de créer une base de données avec des données sur les personnes, lorsqu'il est important d'accumuler et de systématiser un maximum d'informations diverses sur le client. Ceci est demandé dans les domaines de la médecine, de la banque, du marketing, de l'archivage et dans d'autres domaines.

.
Bien entendu, en SQL, vous pouvez également émuler un arbre avec seulement quelques tables (EAV, 1,2,3,4,5,6,7,8,9,10), mais cela est nettement plus compliqué et sera plus lent. Essentiellement, vous devrez écrire un global qui fonctionne sur les tables et masquer tout le travail avec les tables sous une couche d'abstraction. Il est erroné d’émuler une technologie de niveau inférieur (globaux) à l’aide d’une technologie de niveau supérieur (SQL). Inapproprié.

Ce n'est un secret pour personne que modifier le schéma de données sur des tables géantes (ALTER TABLE) peut prendre beaucoup de temps. MySQL, par exemple, effectue ALTER TABLE ADD|DROP COLUMN en copiant complètement les informations de l'ancienne table vers la nouvelle table (moteurs MyISAM, InnoDB testés). Ce qui peut bloquer une base de données fonctionnelle contenant des milliards d’enregistrements pendant des jours, voire des semaines.

Changer la structure des données si nous utilisons des globales ne nous coûte rien. À tout moment, nous pouvons ajouter toutes les nouvelles propriétés dont nous avons besoin à n'importe quel objet, à n'importe quel niveau de la hiérarchie. Les modifications associées au renommage des branches peuvent être exécutées en arrière-plan sur une base de données en cours d'exécution.


Par conséquent, lorsqu’il s’agit de stocker des objets avec un grand nombre de propriétés facultatives, les globales constituent un excellent choix.

De plus, permettez-moi de vous rappeler que l'accès à n'importe laquelle des propriétés est instantané, puisque dans le global tous les chemins sont des B-trees.

Les bases de données globales, en général, sont un type de base de données orientée document avec la capacité de stocker des informations hiérarchiques. Par conséquent, les bases de données orientées documents peuvent rivaliser avec les bases de données globales dans le domaine du stockage des dossiers médicaux. Mais ce n'est toujours pas tout à fait pareilPrenons MongoDB à titre de comparaison. Dans ce domaine il perd face aux globaux pour les raisons suivantes :

1. Taille du document. L'unité de stockage est du texte au format JSON (plus précisément BSON) d'un volume maximum d'environ 16 Mo. La restriction a été faite spécifiquement pour que la base de données JSON ne ralentisse pas pendant l'analyse si un énorme document JSON y est stocké puis accessible par les champs. Ce document doit contenir toutes les informations sur le patient. Nous savons tous à quel point les dossiers des patients peuvent être volumineux. La taille maximale de la carte de 16 Mo met immédiatement fin aux patients dont la carte maladie comprend des fichiers IRM, des radiographies et d'autres études. Dans une branche du monde, vous pouvez disposer de gigaoctets et de téraoctets d’informations. En principe, nous pouvons y mettre un terme, mais je continuerai.
2. Moment de conscience/changement/suppression de nouvelles propriétés dans le dossier du patient. Une telle base de données doit lire la carte entière en mémoire (c'est une grande quantité !), analyser BSON, ajouter/modifier/supprimer un nouveau nœud, mettre à jour les index, la compresser dans BSON et la sauvegarder sur le disque. Un global n'a besoin que d'accéder à une propriété spécifique et de la manipuler.
3. Accès rapide aux propriétés individuelles. Avec de nombreuses propriétés dans un document et sa structure à plusieurs niveaux, l'accès aux propriétés individuelles sera plus rapide du fait que chaque chemin dans le global est un arbre B. Dans BSON, vous devez analyser linéairement le document pour trouver la propriété souhaitée.

3.3.2 Tableaux associatifs

Les tableaux associatifs (même avec des tableaux imbriqués) s'adaptent parfaitement aux valeurs globales. Par exemple, un tel tableau de PHP sera affiché dans la première image 3.3.1.

$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 Documents hiérarchiques : XML, JSON

Également facilement stocké dans les globals. Peut être aménagé de différentes manières pour le stockage.

XML
Le moyen le plus simple de décomposer XML en éléments globaux consiste à stocker les attributs de balise dans des nœuds. Et si un accès rapide aux attributs des balises est nécessaire, nous pouvons les déplacer dans des branches distinctes.

<note id=5>
<to>Вася</to>
<from>Света</from>
<heading>Напоминание</heading>
<body>Позвони мне завтра!</body>
</note>

Sur COS cela correspondrait au code :

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

Remarque: Pour XML, JSON et les tableaux associatifs, vous pouvez proposer de nombreuses façons différentes d'afficher sur les valeurs globales. Dans ce cas, nous n'avons pas reflété l'ordre des sous-balises dans la balise de note. À l'échelle mondiale ^xml les sous-balises seront affichées par ordre alphabétique. Pour refléter strictement l'ordre, vous pouvez utiliser, par exemple, l'affichage suivant :

JSON.
La première image de la section 3.3.1 montre un reflet de ce document JSON :

var document = {
  "name": "Vince Medvedev",
  "city": "Moscow",
  "threatments": {
    "surgeries": ["apedicectomy", "biopsy"],
    "radiation": ["gamma", "x-rays"],
    "physiotherapy": ["knee", "shoulder"]
  },
};

3.3.4 Structures identiques reliées par des relations hiérarchiques

Exemples : la structure des bureaux de vente, la localisation des personnes dans une structure MLM, la base de données des ouvertures aux échecs.

Lancement de la base de données. Vous pouvez utiliser l'estimation de la force de course comme valeur d'index du nœud global. Ensuite, afin de choisir le coup le plus fort, il suffira de choisir la branche ayant le plus de poids. Dans le monde global, toutes les branches de chaque niveau seront triées par force de mouvement.

La structure des bureaux de vente, la structure des personnes en MLM. Les nœuds peuvent stocker certaines valeurs de mise en cache qui reflètent les caractéristiques de l'ensemble du sous-arbre. Par exemple, le volume des ventes d'un sous-arbre donné. A tout moment, nous pouvons obtenir un chiffre reflétant les réalisations de n'importe quelle branche.

4. Dans quels cas est-il plus avantageux d’utiliser des variables globales ?

La première colonne présente les cas où vous obtiendrez un gain de vitesse significatif en utilisant des globaux, et la seconde où la conception ou le modèle de données sera simplifié.

vitesse
Facilité de traitement/présentation des données

1. Insertion [avec tri automatique à chaque niveau], [indexation par passe passe]
2. Suppression de sous-arbres
3. Objets avec de nombreuses propriétés imbriquées nécessitant un accès individuel
4. Structure hiérarchique avec la possibilité de contourner les branches enfants de n'importe quelle branche, même celles inexistantes
5. Traversée en profondeur des sous-arbres

1. Objets/entités avec un grand nombre de propriétés/entités facultatives [et/ou imbriquées]
2. Données sans schéma. De nouvelles propriétés peuvent souvent apparaître et les anciennes disparaître.
3. Vous devez créer une base de données personnalisée.
4. Bases de chemin et arbres de décision. Lorsqu’il est pratique de représenter les chemins sous forme d’arbre.
5. Supprimer les structures hiérarchiques sans utiliser la récursivité

Extension « Les planètes sont des épées-trésor pour stocker des données. Tableaux clairsemés. Partie 3".

Clause de non-responsabilité  : Cet article et mes commentaires sont mon opinion et n'ont aucun rapport avec la position officielle d'InterSystems Corporation.

Source: habr.com