Os globais son espadas de tesouro para almacenar datos. Árbores. Parte 2

Primeiros pasos - ver a parte 1.

3. Variantes de estruturas ao utilizar globais

Unha estrutura como unha árbore ordenada ten varios casos especiais. Consideremos aqueles que teñen un valor práctico ao traballar con globais.

3.1 Caso especial 1. Un nodo sen ramas

Os globais pódense usar non só como unha matriz, senón tamén como variables regulares. Por exemplo, como contador:

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

Neste caso, o global, ademais do seu significado, tamén pode ter ramas. Un non exclúe ao outro.

3.2 Caso especial 2. Un vértice e moitas ramas

En xeral, esta é unha base de clave-valor clásica. E se gardamos unha tupla de valores como valor, obteremos unha táboa moi común cunha chave primaria.

Para implementar unha táboa sobre globais, teremos que xerar filas nós mesmos a partir dos valores das columnas e despois gardalas no global usando a chave primaria. Para facer posible dividir a cadea en columnas de novo ao ler, pode usar:

1. caracteres delimitadores.

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

2. un esquema ríxido no que cada campo ocupa un número predeterminado de bytes. Como se fai nas bases de datos relacionais.
3. unha función especial $LB (dispoñible na caché), que crea unha cadea de valores.

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

Curiosamente, non é difícil usar globais para facer algo semellante aos índices secundarios nas bases de datos relacionais. Chamemos a tales estruturas índices globais. Un índice global é unha árbore auxiliar para buscar rapidamente campos que non forman parte da clave primaria do global principal. Para enchelo e usalo, cómpre escribir código adicional.

Imos crear un índice global na primeira columna.

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

Agora, para buscar rapidamente información na primeira columna, temos que mirar o global ^i e busque as claves primarias (id) correspondentes ao valor desexado da primeira columna.

Ao inserir un valor, podemos crear inmediatamente o valor e o índice global dos campos obrigatorios. E para fiabilidade, envolvémolo todo nunha transacción.

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

Detalles sobre como facelo en M táboas sobre globais, emulación de índices secundarios.

Tales táboas funcionarán tan rápido como nas bases de datos tradicionais (ou aínda máis rápido) se as funcións para inserir/actualizar/eliminar filas están escritas en COS/M e compiladas.Comprobei esta declaración con probas en masa INSERT e SELECT nunha táboa de dúas columnas, incluíndo o uso dos comandos TSTART e TCOMMIT (transaccións).

Non probei escenarios máis complexos con acceso simultáneo e transaccións paralelas.

Sen utilizar transaccións, a taxa de inserción foi de 778 insercións/segundo por millón de valores.
Con 300 millóns de valores - 422 insercións/segundo.

Cando se usan transaccións: 572 insercións/segundo para insercións de 082 millóns. Todas as operacións realizáronse a partir do código M compilado.
Os discos duros son normais, non SSD. RAID5 con reescritura. Procesador Phenom II 1100T.

Para probar unha base de datos SQL dun xeito similar, cómpre escribir un procedemento almacenado que realizará insercións nun bucle. Ao probar MySQL 5.5 (almacenamento InnoDB), usando este método recibín números de non máis de 11K insercións por segundo.
Si, a implementación de táboas en globais parece máis complexa que nas bases de datos relacionais. Polo tanto, as bases de datos industriais sobre globais teñen acceso SQL para simplificar o traballo con datos tabulares.

En xeral, se o esquema de datos non cambia con frecuencia, a velocidade de inserción non é crítica e toda a base de datos pódese representar facilmente en forma de táboas normalizadas, entón é máis fácil traballar con SQL, xa que proporciona un maior nivel de abstracción. .

Neste caso concreto quería demostralo globals poden actuar como un construtor para crear outras bases de datos. Como un ensamblador no que se poden escribir outras linguas. Aquí tes exemplos de como podes crear análogos en globais clave-valor, listas, conxuntos, bases de datos tabulares e orientadas a documentos.

Se necesitas crear algún tipo de base de datos non estándar cun mínimo esforzo, deberías mirar cara aos globais.

3.3 Caso especial 3. Árbore de dous niveis, cada nodo do segundo nivel ten un número fixo de ramas

Probablemente o adiviñaches: esta é unha implementación alternativa de táboas sobre globais. Imos comparar esta implementación coa anterior.

Táboas nunha árbore de dous niveis vs. nunha árbore dun só nivel.

Contra
Pros

1. Máis lento para a inserción, xa que cómpre establecer o número de nós igual ao número de columnas.
2. Máis consumo de espazo en disco. Xa que os índices globais (entendidos como índices de matriz) con nomes de columna ocupan espazo no disco e duplícanse para cada fila.

1. Acceso máis rápido aos valores das columnas individuais, xa que non é necesario analizar a cadea. Segundo as miñas probas, é un 11,5% máis rápido en 2 columnas e máis nun número maior de columnas.
2. Máis fácil cambiar o esquema de datos
3. Código máis claro

Conclusión: non para todos. Dado que a velocidade é un dos beneficios máis fundamentais dos globais, non ten sentido usar esta implementación, xa que o máis probable é que non funcione máis rápido que as táboas das bases de datos relacionais.

3.4 Caso xeral. Árbores e árbores ordenadas

Calquera estrutura de datos que se poida representar como unha árbore encaixa perfectamente cos globais.

3.4.1 Obxectos con subobxectos

Esta é a área de uso tradicional dos globais. No campo médico hai un gran número de enfermidades, medicamentos, síntomas e métodos de tratamento. É irracional crear unha táboa con un millón de campos para cada paciente. Ademais, o 99% dos campos estarán baleiros.

Imaxina unha base de datos SQL de táboas: "paciente" ~ 100 campos, "Medicina" - 000 campos, "Terapia" - 100 campos, "Complicacións" - 000 campos, etc. etcétera. Ou pode crear unha base de datos de moitos miles de táboas, cada unha para un tipo específico de paciente (e poden superpoñerse!), tratamentos, medicamentos e miles de táboas máis para conexións entre estas táboas.

Os globais son ideais para a medicina, xa que permiten crear para cada paciente unha descrición precisa do seu historial médico, varias terapias e as accións dos medicamentos, en forma de árbore, sen perder espazo en disco extra en columnas baleiras, como faría. ser o caso nun caso relacional.

Usando globais é conveniente crear unha base de datos con datos sobre persoas, cando é importante acumular e sistematizar un máximo de información variada sobre o cliente. Isto é demandado en medicina, banca, mercadotecnia, arquivo e outras áreas

.
Por suposto, en SQL tamén pode emular unha árbore con só unhas poucas táboas (EAV, 1,2,3,4,5,6,7,8,9,10), con todo isto é significativamente máis complicado e será máis lento. Esencialmente, terías que escribir un global que funcione en táboas e ocultar todo o traballo con táboas baixo unha capa de abstracción. É incorrecto emular tecnoloxía de nivel inferior (globais) utilizando tecnoloxía de nivel superior (SQL). Inadecuado.

Non é ningún segredo que cambiar o esquema de datos en táboas xigantes (ALTER TABLE) pode levar moito tempo. MySQL, por exemplo, fai ALTER TABLE ADD|DROP COLUMN copiando completamente a información da táboa antiga á táboa nova (motores MyISAM e InnoDB probados). O que pode colgar unha base de datos de traballo con miles de millóns de rexistros durante días, se non semanas.

Cambiar a estrutura de datos se usamos globais non nos custa nada. En calquera momento podemos engadir as novas propiedades que precisemos a calquera obxecto, en calquera nivel da xerarquía. Os cambios asociados ao cambio de nome das ramas pódense executar en segundo plano nunha base de datos en execución.


Polo tanto, cando se trata de almacenar obxectos cunha gran cantidade de propiedades opcionais, os globais son unha excelente opción.

Ademais, permítanme lembrar que o acceso a calquera das propiedades é instantáneo, xa que no global todos os camiños son árbores B.

As bases de datos globais, en xeral, son un tipo de base de datos orientada a documentos coa capacidade de almacenar información xerárquica. Polo tanto, as bases de datos orientadas a documentos poden competir cos globais no campo do almacenamento de rexistros médicos. Pero aínda non é o mesmoTomemos MongoDB para comparar. Neste dominio perde ante os globais polas seguintes razóns:

1. Tamaño do documento. A unidade de almacenamento é texto en formato JSON (máis precisamente BSON) cun volume máximo duns 16 MB. A restrición fíxose especificamente para que a base de datos JSON non se ralentice durante a análise se se almacena nela un documento JSON enorme e despois accede por campos. Este documento debe conter toda a información sobre o paciente. Todos sabemos o grosos que poden ser os rexistros dos pacientes. O tamaño máximo da tarxeta de 16 MB pon fin inmediatamente aos pacientes cuxa tarxeta de enfermidade inclúe ficheiros de resonancia magnética, exploracións de raios X e outros estudos. Nunha rama do global podes ter gigabytes e terabytes de información. En principio, podemos acabar con isto, pero vou seguir.
2. Tempo de conciencia/cambio/eliminación de novas propiedades na historia clínica do paciente. Dita base de datos debe ler o mapa completo na memoria (isto é unha gran cantidade!), analizar BSON, engadir/cambiar/eliminar un novo nodo, actualizar índices, empaquetalo en BSON e gardalo no disco. Un global só precisa acceder a unha propiedade específica e manipulala.
3. Acceso rápido a propiedades individuais. Con moitas propiedades nun documento e a súa estrutura de varios niveis, o acceso ás propiedades individuais será máis rápido debido ao feito de que cada camiño no global é unha árbore B. En BSON, tes que analizar linealmente o documento para atopar a propiedade desexada.

3.3.2 Arrays asociativos

As matrices asociativas (mesmo con matrices aniñadas) encaixan perfectamente nos globais. Por exemplo, tal matriz de PHP mostrarase na primeira imaxe 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 Documentos xerárquicos: XML, JSON

Tamén se almacena facilmente en globais. Pódese dispor de diferentes xeitos para o almacenamento.

XML
A forma máis sinxela de descompoñer XML en globais é almacenar atributos de etiquetas en nós. E se é necesario un acceso rápido aos atributos das etiquetas, poderemos movelos a ramas separadas.

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

En COS isto correspondería ao código:

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

Comentario: Para XML, JSON, matrices asociativas, podes atopar moitas formas diferentes de mostrar en globais. Neste caso, non reflectimos a orde das subetiquetas na etiqueta da nota. A nivel mundial ^xml as subetiquetas mostraranse por orde alfabética. Para reflectir estrictamente a orde, pode usar, por exemplo, a seguinte pantalla:

JSON.
A primeira imaxe da sección 3.3.1 mostra un reflexo deste documento JSON:

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

3.3.4 Estruturas idénticas conectadas por relacións xerárquicas

Exemplos: a estrutura das oficinas de vendas, a localización das persoas nunha estrutura de MLM, a base de datos de ocos no xadrez.

Base de datos de estreas. Podes usar a estimación da forza de trazo como o valor do índice do nodo global. Despois, para escoller o movemento máis forte, abondará con escoller a rama de maior peso. No global, todas as ramas de cada nivel ordenaranse por forza de movemento.

A estrutura das oficinas de vendas, a estrutura das persoas en MLM. Os nodos poden almacenar certos valores de caché que reflicten as características de toda a subárbore. Por exemplo, o volume de vendas dunha determinada subárbore. En calquera momento podemos obter unha cifra que reflicta os logros de calquera rama.

4. En que casos é máis beneficioso utilizar globais?

A primeira columna presenta casos nos que obterás unha ganancia de velocidade significativa mediante o uso de globais, e a segunda cando se simplificará o deseño ou o modelo de datos.

Acelerar
Facilidade de tratamento/presentación de datos

1. Inserción [con clasificación automática en cada nivel], [indexación por chave mestra]
2. Eliminando subárbores
3. Obxectos con moitas propiedades aniñadas que requiren acceso individual
4. Estrutura xerárquica coa capacidade de evitar ramas fillas de calquera rama, incluso as inexistentes
5. Percorrido en profundidade de subárbores

1. Obxectos/entidades cun gran número de propiedades/entidades opcionais [e/ou aniñadas].
2. Datos sen esquema. Cando moitas veces poden aparecer novas propiedades e desaparecer as antigas.
3. Debe crear unha base de datos personalizada.
4. Bases de camiños e árbores de decisión. Cando é conveniente representar camiños como unha árbore.
5. Eliminación de estruturas xerárquicas sen utilizar recursividade

Extensión "Os globais son espadas de tesouro para almacenar datos. Arrays escasos. Parte 3".

retratação: Este artigo e os meus comentarios ao mesmo son a miña opinión e non teñen relación coa posición oficial de InterSystems Corporation.

Fonte: www.habr.com