I globali sono spade del tesoro per l'archiviazione dei dati. Alberi. Parte 2

Per iniziare: vedere la parte 1.

3. Varianti di strutture quando si usano i globali

Una struttura come un albero ordinato ha vari casi speciali. Consideriamo quelli che hanno valore pratico quando si lavora con i globali.

3.1 Caso speciale 1. Un nodo senza rami

Le variabili globali possono essere utilizzate non solo come un array, ma anche come variabili regolari. Ad esempio, come contatore:

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

In questo caso il globale, oltre al suo significato, può avere anche dei rami. L'uno non esclude l'altro.

3.2 Caso speciale 2. Un vertice e molti rami

In generale, questa è una base chiave-valore classica. E se salviamo una tupla di valori come valore, otterremo una tabella molto ordinaria con una chiave primaria.

Per implementare una tabella sui globali, dovremo generare noi stessi le righe dai valori delle colonne e quindi salvarle nel globale utilizzando la chiave primaria. Per rendere possibile dividere nuovamente la stringa in colonne durante la lettura, puoi utilizzare:

1. caratteri delimitatori.

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

2. uno schema rigido in cui ogni campo occupa un numero predeterminato di byte. Come avviene nei database relazionali.
3. una funzione speciale $LB (disponibile in Cache), che crea una stringa di valori.

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

È interessante notare che non è difficile utilizzare i globali per fare qualcosa di simile agli indici secondari nei database relazionali. Chiamiamo tali strutture indici globali. Un indice globale è un albero ausiliario per la ricerca rapida di campi che non fanno parte della chiave primaria del globale principale. Per compilarlo e utilizzarlo è necessario scrivere codice aggiuntivo.

Creiamo un indice globale sulla prima colonna.

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

Ora, per cercare rapidamente le informazioni nella prima colonna, dobbiamo guardare al globale ^i e trova le chiavi primarie (id) corrispondenti al valore desiderato della prima colonna.

Quando inseriamo un valore, possiamo creare immediatamente sia il valore che l'indice globale per i campi richiesti. E per affidabilità, racchiudiamo il tutto in una transazione.

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

Dettagli su come farlo su M tabelle sui globali, emulazione di indici secondari.

Tali tabelle funzioneranno velocemente come nei database tradizionali (o anche più velocemente) se le funzioni per l'inserimento/aggiornamento/eliminazione delle righe sono scritte in COS/M e compilate.Ho verificato questa affermazione con test su INSERT e SELECT in blocco in una tabella a due colonne, incluso l'utilizzo dei comandi TSTART e TCOMMIT (transazioni).

Non ho testato scenari più complessi con accesso simultaneo e transazioni parallele.

Senza utilizzare le transazioni, il tasso di inserimento era di 778 inserti/secondo per milione di valori.
Con 300 milioni di valori - 422 inserti/secondo.

Quando si utilizzano transazioni: 572 inserimenti/secondo per 082 milioni di inserimenti. Tutte le operazioni sono state eseguite dal codice M compilato.
I dischi rigidi sono normali, non SSD. RAID5 con riscrittura. Processore Phenom II 1100T.

Per testare un database SQL in modo simile, è necessario scrivere una procedura memorizzata che effettuerà gli inserimenti in un ciclo. Durante il test di MySQL 5.5 (archiviazione InnoDB), utilizzando questo metodo ho ricevuto numeri non superiori a 11 inserimenti al secondo.
Sì, l'implementazione delle tabelle sui globali sembra più complessa rispetto ai database relazionali. Pertanto, i database industriali sui globali hanno accesso SQL per semplificare il lavoro con i dati tabulari.

In generale, se lo schema dei dati non cambia frequentemente, la velocità di inserimento non è critica e l'intero database può essere facilmente rappresentato sotto forma di tabelle normalizzate, allora è più facile lavorare con SQL, poiché fornisce un livello di astrazione più elevato .

In questo caso particolare volevo dimostrarlo globals può fungere da costruttore per la creazione di altri database. Come un assembler in cui si possono scrivere altri linguaggi. Ecco alcuni esempi di come è possibile creare analoghi su globali valori-chiave, elenchi, insiemi, database tabulari e orientati ai documenti.

Se hai bisogno di creare una sorta di database non standard con il minimo sforzo, dovresti guardare ai globali.

3.3 Caso speciale 3. Albero a due livelli, ogni nodo del secondo livello ha un numero fisso di rami

Probabilmente hai indovinato: questa è un'implementazione alternativa delle tabelle sui globali. Confrontiamo questa implementazione con quella precedente.

Tabelle su un albero a due livelli vs. su un albero a un solo livello.

Contro
Pro

1. Più lento per l'inserimento, poiché è necessario impostare il numero di nodi uguale al numero di colonne.
2. Maggiore consumo di spazio su disco. Poiché gli indici globali (intesi come indici di array) con nomi di colonna occupano spazio su disco e vengono duplicati per ogni riga.

1. Accesso più rapido ai valori delle singole colonne, poiché non è necessario analizzare la stringa. Secondo i miei test, è più veloce dell'11,5% su 2 colonne e di più su un numero maggiore di colonne.
2. È più semplice modificare lo schema dei dati
3. Codice più chiaro

Conclusione: non per tutti. Poiché la velocità è uno dei vantaggi principali delle variabili globali, non ha molto senso utilizzare questa implementazione, poiché molto probabilmente non funzionerà più velocemente delle tabelle nei database relazionali.

3.4 Caso generale. Alberi e alberi ordinati

Qualsiasi struttura dati che può essere rappresentata come un albero si adatta perfettamente ai globali.

3.4.1 Oggetti con sottooggetti

Questa è l'area di utilizzo tradizionale dei globali. In campo medico esiste un numero enorme di malattie, farmaci, sintomi e metodi di trattamento. È irrazionale creare una tabella con un milione di campi per ciascun paziente. Inoltre, il 99% dei campi sarà vuoto.

Immagina un database SQL di tabelle: "paziente" ~ 100 campi, "Medicina" - 000 campi, "Terapia" - 100 campi, "Complicanze" - 000 campi, ecc. e così via. Oppure puoi creare un database di molte migliaia di tabelle, ciascuna per un tipo specifico di paziente (e possono sovrapporsi!), trattamenti, farmaci e migliaia di altre tabelle per le connessioni tra queste tabelle.

I globali sono ideali per la medicina, poiché consentono di creare per ogni paziente una descrizione accurata della sua storia medica, delle varie terapie e delle azioni dei farmaci, sotto forma di albero, senza sprecare spazio su disco aggiuntivo in colonne vuote, come farebbe essere il caso in un caso relazionale.

Utilizzando i valori globali è conveniente creare un database con dati sulle persone, quando è importante accumulare e sistematizzare il massimo di varie informazioni sul cliente. Questo è richiesto in medicina, banche, marketing, archiviazione e in altri settori

.
Naturalmente, in SQL puoi anche emulare un albero con poche tabelle (EAV, 1,2,3,4,5,6,7,8,9,10), tuttavia l'operazione è molto più complicata e sarà più lenta. In sostanza, dovresti scrivere un globale che funzioni sulle tabelle e nascondere tutto il lavoro con le tabelle sotto un livello di astrazione. È sbagliato emulare la tecnologia di livello inferiore (globali) utilizzando la tecnologia di livello superiore (SQL). Non appropriato.

Non è un segreto che la modifica dello schema dei dati su tabelle giganti (ALTER TABLE) possa richiedere molto tempo. MySQL, ad esempio, esegue ALTER TABLE ADD|DROP COLUMN copiando completamente le informazioni dalla vecchia tabella alla nuova tabella (motori MyISAM e InnoDB testati). Il che può bloccare un database funzionante con miliardi di record per giorni, se non settimane.

Cambiare la struttura dei dati se usiamo i globali non ci costa nulla. In qualsiasi momento possiamo aggiungere qualsiasi nuova proprietà di cui abbiamo bisogno a qualsiasi oggetto, a qualsiasi livello della gerarchia. Le modifiche associate alla ridenominazione dei rami possono essere eseguite in background su un database in esecuzione.


Pertanto, quando si tratta di archiviare oggetti con un numero enorme di proprietà opzionali, le proprietà globali sono un'ottima scelta.

Inoltre, lascia che ti ricordi che l'accesso a qualsiasi proprietà è immediato, poiché nel globale tutti i percorsi sono B-tree.

I database globali, in generale, sono un tipo di database orientato ai documenti con la capacità di archiviare informazioni gerarchiche. Pertanto, i database orientati ai documenti possono competere con quelli globali nel campo dell’archiviazione delle cartelle cliniche. Ma non è ancora proprio la stessa cosaPrendiamo MongoDB per confronto. In questo dominio perde contro i globali per i seguenti motivi:

1. Dimensioni del documento. L'unità di memorizzazione è testo in formato JSON (più precisamente BSON) con un volume massimo di circa 16MB. La restrizione è stata creata appositamente in modo che il database JSON non rallenti durante l'analisi se al suo interno è archiviato un documento JSON di grandi dimensioni e quindi vi si accede tramite campi. Questo documento dovrebbe contenere tutte le informazioni sul paziente. Sappiamo tutti quanto possono essere spesse le cartelle cliniche dei pazienti. La dimensione massima della scheda di 16 MB mette immediatamente fine ai pazienti la cui scheda della malattia comprende file MRI, scansioni radiografiche e altri studi. In un ramo del globale puoi avere gigabyte e terabyte di informazioni. In linea di principio possiamo porre fine a questa situazione, ma continuerò.
2. Tempo di coscienza/cambiamento/cancellazione di nuove proprietà nella cartella del paziente. Un database di questo tipo deve leggere l'intera mappa in memoria (questa è una grande quantità!), analizzare BSON, aggiungere/modificare/eliminare un nuovo nodo, aggiornare gli indici, comprimerlo in BSON e salvarlo su disco. Un globale deve solo accedere a una proprietà specifica e manipolarla.
3. Accesso rapido alle singole proprietà. Con molte proprietà in un documento e la sua struttura multi-livello, l'accesso alle singole proprietà sarà più veloce grazie al fatto che ogni percorso nel globale è un B-tree. In BSON, devi analizzare linearmente il documento per trovare la proprietà desiderata.

3.3.2 Array associativi

Gli array associativi (anche con array nidificati) si adattano perfettamente ai globali. Ad esempio, un tale array di PHP verrà visualizzato nella prima immagine 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 Documenti gerarchici: XML, JSON

Anche facilmente memorizzabile in globali. Può essere disposto in diversi modi per la conservazione.

XML
Il modo più semplice per scomporre XML in valori globali è memorizzare gli attributi dei tag nei nodi. E se è necessario un accesso rapido agli attributi dei tag, possiamo spostarli in rami separati.

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

Su COS questo corrisponderebbe al codice:

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

osservazione: Per XML, JSON e array associativi, puoi trovare molti modi diversi di visualizzare su globali. In questo caso, non abbiamo rispecchiato l'ordine dei sottotag nel tag della nota. A livello globale ^xml i sottotag verranno visualizzati in ordine alfabetico. Per riflettere rigorosamente l'ordine, è possibile utilizzare, ad esempio, la seguente visualizzazione:

JSON.
La prima immagine della sezione 3.3.1 mostra un riflesso di questo documento JSON:

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

3.3.4 Strutture identiche collegate da rapporti gerarchici

Esempi: la struttura degli uffici vendite, l'ubicazione delle persone in una struttura MLM, il database delle aperture negli scacchi.

Database dei debutti. È possibile utilizzare la stima della forza del tratto come valore di indice del nodo globale. Quindi, per scegliere la mossa più forte, basterà scegliere il ramo con il peso maggiore. Nel globale, tutti i rami ad ogni livello saranno ordinati in base alla forza del movimento.

La struttura degli uffici vendita, la struttura delle persone nel MLM. I nodi possono memorizzare determinati valori di memorizzazione nella cache che riflettono le caratteristiche dell'intero sottoalbero. Ad esempio, il volume delle vendite di un determinato sottoalbero. In qualsiasi momento possiamo ottenere una cifra che riflette i risultati di qualsiasi ramo.

4. In quali casi è più vantaggioso utilizzare i globali?

La prima colonna presenta i casi in cui otterrai un significativo aumento di velocità utilizzando i valori globali, mentre la seconda presenta i casi in cui la progettazione o il modello dati verranno semplificati.

velocità
Facilità di elaborazione/presentazione dei dati

1. Inserimento [con ordinamento automatico ad ogni livello], [indicizzazione per chiave maestra]
2. Rimozione dei sottoalberi
3. Oggetti con molte proprietà nidificate che richiedono accesso individuale
4. Struttura gerarchica con la possibilità di bypassare i rami figli di qualsiasi ramo, anche quelli inesistenti
5. Attraversamento in profondità dei sottoalberi

1. Oggetti/entità con un numero enorme di proprietà/entità opzionali [e/o annidate].
2. Dati senza schema. Quando spesso possono apparire nuove proprietà e quelle vecchie scompaiono.
3. È necessario creare un database personalizzato.
4. Basi dei percorsi e alberi decisionali. Quando è conveniente rappresentare i percorsi come un albero.
5. Rimozione delle strutture gerarchiche senza utilizzare la ricorsione

Estensione “I globali sono spade preziose per l’archiviazione dei dati. Array sparsi. Parte 3".

Negazione di responsabilità: Questo articolo e i miei commenti rappresentano la mia opinione e non hanno alcuna relazione con la posizione ufficiale di InterSystems Corporation.

Fonte: habr.com