I globali sono forzieri per la memorizzazione dei dati. Alberi. Parte 2

Inizio — vedi parte 1.

3. Opzioni di struttura nell'uso delle variabili globali

Una struttura come un albero ordinato ha diversi casi particolari. Consideriamo quelli che hanno valore pratico nell'uso delle variabili globali.

3.1 Caso particolare 1. Un nodo senza diramazioni

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

Set ^counter = 0  ; impostazione del contatore
Set id=$Increment(^counter) ;  incremento atomico

In questo caso, la variabile globale, oltre al valore, può avere anche diramazioni. L'una non esclude l'altra.

3.2 Caso particolare 2. Un nodo e molte diramazioni

In generale, questo è un classico database key-value. E se come valore memorizziamo una tupla di valori, otteniamo una tabella con chiave primaria.

Per implementare una tabella nelle variabili globali, dovremo formare noi stessi le stringhe dai valori delle colonne e poi salvarle nella variabile globale secondo la chiave primaria. Per poter separare nuovamente la stringa in colonne durante la lettura, possiamo 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 di byte prestabilito. Come avviene nei database relazionali.
3. una funzione speciale $LB (disponibile in Cache), che crea una stringa a partire dai valori.

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

È interessante notare che non è difficile creare, a livello globale, qualcosa di simile agli indici secondari nei database relazionali. Chiamiamo queste strutture globali indicizzate. Un global indicizzato è un albero ausiliario per la ricerca rapida nei campi che non sono componenti della chiave primaria del global principale. Per la sua popolazione e utilizzo è necessario scrivere codice aggiuntivo.

Creiamo un global indicizzato basato sulla prima colonna.

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

Ora, per una ricerca rapida delle informazioni nella prima colonna, dobbiamo consultare il global ^i e trovare le chiavi primarie (id) corrispondenti al valore desiderato della prima colonna.

Quando inseriamo un valore, possiamo creare immediatamente sia il valore che i globali indicizzati per i campi necessari. E per maggiore sicurezza, incapsuleremo tutto in una transazione.

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

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

Queste tabelle funzioneranno altrettanto velocemente quanto in un database tradizionale (o anche più velocemente), se le funzioni di inserimento/aggiornamento/cancellazione delle righe vengono scritte in COS/M e compilate.Ho verificato questa affermazione attraverso test di inserimento e selezione massivi su una tabella a due colonne, incluso l'uso dei comandi TSTART e TCOMMIT (transazioni).

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

Senza l'uso di transazioni, la velocità degli inserimenti su un milione di valori era di 778.361 inserimenti/secondo.
Con 300 milioni di valori — 422.141 inserimenti/secondo.

Utilizzando transazioni — 572.082 inserimenti/secondo su 50 milioni di inserimenti. Tutte le operazioni sono state svolte da codice M compilato.
I dischi rigidi sono normali, non SSD. RAID5 con Write-back. Processore Phenom II 1100T.

Per un test simile su un database SQL è necessario scrivere una stored procedure che esegue inserimenti in un ciclo. Quando ho testato MySQL 5.5 (storage InnoDB) con questo metodo, ho ottenuto risultati non superiori a 11K inserimenti al secondo.
Sì, l'implementazione delle tabelle sui globali appare più complessa rispetto ai database relazionali. Per questo motivo, i database industriali sui globali dispongono di accesso SQL per semplificare il lavoro con i dati tabellari.

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

In questo caso specifico volevo mostrare che i globali possono fungere da costruttore per creare altri database. Come un assembler, su cui si possono scrivere altri linguaggi. Ecco alcuni esempi di come si possono creare sui globali analoghi di database key-value, liste, insiemi, tabellari e orientati ai documenti.

Se è necessario creare un database non standard con il minimo sforzo, vale la pena dare un'occhiata ai globali.

3.3 Caso particolare 3. Albero a due livelli, con un numero fisso di rami per ogni nodo di secondo livello

Probabilmente avete indovinato: si tratta di 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 livello.

Svantaggi
Pro

1. Più lento nell'inserimento, poiché è necessario impostare il numero di nodi uguale al numero di colonne.
2. Maggiore utilizzo dello spazio su disco. Gli indici globali (intesi come indici degli array) con i nomi delle colonne occupano spazio su disco e vengono duplicati per ogni riga.

1. Accesso più veloce ai valori delle singole colonne, poiché non è necessario analizzare la riga. Dai miei test, è più veloce del 11,5% con 2 colonne e di più con un numero maggiore di colonne.
2. Più semplice modificare lo schema dei dati.
3. Codice più chiaro.

Risultato: Soggettivo. Poiché la velocità è uno dei principali vantaggi dei globali, non ha quasi senso utilizzare questa implementazione, poiché 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 sotto-oggetti.

Questo è il campo di applicazione tradizionale dei globali. Nel settore medico ci sono enormi quantità di malattie, farmaci, sintomi e metodi di trattamento. Creare una tabella con un milione di campi per ogni paziente non è razionale. Inoltre, il 99% dei campi sarà vuoto.

Immaginate un DB SQL composto da tabelle: «paziente» ~ 100.000 campi, «Farmaco» — 100.000 campi, «Terapia» — 100.000 campi, «Complicazioni» — 100.000 campi, e così via. Oppure si potrebbe creare un DB di migliaia di tabelle, ciascuna per un certo tipo di paziente (e potrebbero sovrapporsi!), di trattamenti, farmaci, e ancora migliaia di tabelle per le relazioni tra queste tabelle.

I globali sono perfetti per la medicina, poiché permettono di creare per ogni paziente una descrizione precisa della sua storia clinica, delle varie terapie, delle azioni dei farmaci, sotto forma di albero, senza sprecare spazio su disco con colonne vuote, come avverrebbe nel caso relazionale.

Con i globali è facile creare un DB con dati sulle persone, quando è importante raccogliere e sistematizzare il massimo di informazioni variegate sul cliente. Questo è molto richiesto in medicina, nel settore bancario, nel marketing, negli archivi e in altri ambiti.

.
Certamente, anche in SQL si può emulare un albero con solo alcune tabelle (EAV, 1,2,3,4,5,6,7,8,9,10), tuttavia è notevolmente più complesso e funzionerà più lentamente. In sostanza, sarebbe necessario scrivere un globale funzionante su tabelle e nascondere tutto il lavoro con le tabelle sotto uno strato di astrazione. Non è corretto emulare una tecnologia a basso livello (globali) con mezzi a più alto livello (SQL). Non è pratico.

Non è un segreto che modificare uno schema dati su tabelle gigantesche (ALTER TABLE) possa richiedere un tempo considerevole. MySQL, ad esempio, esegue ALTER TABLE ADD|DROP COLUMN copiando completamente le informazioni dalla vecchia alla nuova tabella (ho testato i motori MyISAM, InnoDB). Questo può bloccare un database in funzione con miliardi di record per giorni, se non settimane.

Modificare la struttura dei dati, se utilizziamo i globali, non ci costa nulla. Possiamo aggiungere in qualsiasi momento tutte le nuove proprietà necessarie a qualsiasi oggetto, a qualsiasi livello di gerarchia. Le modifiche relative alla rinominazione dei rami possono essere eseguite in background su un database attivo.


Pertanto, quando si tratta di memorizzare oggetti con un'enorme quantità di proprietà facoltative, i globali sono un'ottima scelta.

Ricordo che l'accesso a qualsiasi proprietà è immediato, poiché in globale tutti i percorsi sono costituiti da un B-tree.

Le basi di dati in globale, in generale, sono una forma di database orientato a documenti, con la possibilità di memorizzare informazioni gerarchiche. Pertanto, nel campo della conservazione delle cartelle cliniche, i database orientati a documenti possono competere con i globali. Tuttavia, non è proprio la stessa cosaPrendiamo come confronto, ad esempio, MongoDB. In questo ambito perde rispetto ai globali per i seguenti motivi:

1. Dimensione del documento. L'unità di archiviazione è un testo in formato JSON (più precisamente BSON) di dimensioni massime di circa 16 MB. Questo limite è stato impostato appositamente per evitare che il database JSON rallenti durante il parsing, nel caso in cui venga salvato un enorme documento JSON e poi venga accesso per campi. Questo documento deve contenere tutte le informazioni sul paziente. Sappiamo tutti quanto possano essere ingombranti le cartelle dei pazienti. La dimensione massima della cartella di 16 MB esclude immediatamente i pazienti le cui cartelle contengono file MRI, scanning radiografici e altri studi. In un ramo globale, invece, è possibile avere informazioni in gigabyte e terabyte. In linea di principio, si potrebbe fermarsi qui, ma continuerò.
2. Tempo di consapevolezza/cambiamento/cancellazione di nuove proprietà nella cartella del paziente. Un database di questo tipo deve caricare in memoria l'intera cartella (è un grande volume!), fare il parsing del BSON, inserire/modificare/eliminare un nuovo nodo, aggiornare gli indici, imballare in BSON e salvare su disco. Per il ramo globale, invece, è sufficiente accedere a una specifica proprietà e manipolarla.
3. Velocità di accesso a singole proprietà. Con molte proprietà in un documento e la sua struttura multilivello, l'accesso a singole proprietà sarà più veloce grazie al fatto che ogni percorso nella memoria globale è un B-tree. In BSON, invece, sarà necessario analizzare linearmente il documento per trovare la proprietà desiderata.

3.3.2 Array associativi

Gli array associativi (anche quelli con array annidati) si adattano perfettamente alla memoria globale. Ad esempio, un array di PHP come questo si rappresenterebbe 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

Si memorizzano altrettanto facilmente nella memoria globale. È possibile organizzarli in diversi modi.

XML
Il modo più semplice per organizzare XML in memorie globali è memorizzare gli attributi dei tag nei nodi. Se è necessario un accesso rapido agli attributi dei tag, possiamo estrarli in rami separati.

<note id="5">
<to>Vasya</to>
<from>Sveta</from>
<heading>Promemoria</heading>
<body>Chiamami domani!</body>
</note>

In COS ciò corrisponderà al codice:

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

Nota: Per XML, JSON e array associativi esistono moltissimi modi per visualizzarli nei globi. In questo caso, non abbiamo riflesso l'ordine degli elementi annidati nel tag note. Nel globo ^xml i tag annidati verranno visualizzati in ordine alfabetico. Per riflettere rigorosamente l'ordine, si può utilizzare, ad esempio, questa visualizzazione:

JSON.
Nella prima immagine della sezione 3.3.1 è mostrata la rappresentazione 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 relazioni gerarchiche

Esempi: struttura degli uffici di vendita, posizione delle persone in una struttura MLM, database delle aperture negli scacchi.

Database delle aperture. Si può utilizzare la valutazione della forza di mossa come valore dell'indice del nodo globale. Così, per scegliere la mossa più forte sarà sufficiente selezionare il ramo con il peso maggiore. Nel globo, tutti i rami a ogni livello saranno ordinati per forza di mossa.

Struttura degli uffici di vendita, struttura delle persone in un MLM. Nei nodi è possibile memorizzare alcuni valori di cache che riflettono le caratteristiche dell'intero sottoalbero. Ad esempio, il volume di vendite di questo sottoalbero. In qualsiasi momento possiamo ottenere un numero che riflette i risultati di qualsiasi ramo.

4. In quali casi è più vantaggioso utilizzare le variabili globali

Nella prima colonna sono presentati i casi in cui si otterrà un utile guadagno in velocità utilizzando le variabili globali, mentre nella seconda quando si semplificherà lo sviluppo o il modello di dati.

Velocità
Comodità nella gestione/rappresentazione dei dati

1. Inserimento [con ordinamento automatico a ogni livello], [indicizzazione per chiave principale]
2. Eliminazione dei sottoalberi
3. Oggetti con una massiccia quantità di proprietà annidate, che necessitano di accesso individuale
4. Struttura gerarchica con possibilità di attraversare rami secondari da qualsiasi ramo, anche non esistente
5. Attraversamento dei sottoalberi in profondità

1. Oggetti/entità con un'enorme quantità di proprietà/entità facoltative [e/o annidate]
2. Dati senza schema (schema-less). Quando le nuove proprietà possono apparire frequentemente e le vecchie scomparire.
3. È necessario creare un database non standard.
4. Basi di percorsi e alberi decisionali. Quando i percorsi sono convenienti da rappresentare come un albero.
5. Rimozione di strutture gerarchiche senza utilizzare la ricorsione

Continuazione «I globali – spade e calici per la memorizzazione dei dati. Array sparsi. Parte 3».

Avvertenza: Questo articolo e i miei commenti sono solo il mio punto di vista e non rappresentano la posizione ufficiale della corporation InterSystems.

Fonte: habr.com