Os globais são espadas-tesouro para armazenar dados. Árvores. Parte 2

Primeiros passos - veja a parte 1.

3. Variantes de estruturas ao usar globais

Uma estrutura como uma árvore ordenada possui vários casos especiais. Vamos considerar aqueles que têm valor prático ao trabalhar com globais.

3.1 Caso especial 1. Um nó sem ramificações

Globais podem ser usados ​​não apenas como um array, mas também como variáveis ​​regulares. Por exemplo, como contador:

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

Nesse caso, o global, além do significado, também pode ter ramificações. Um não exclui o outro.

3.2 Caso especial 2. Um vértice e muitos ramos

Em geral, esta é uma base clássica de valores-chave. E se salvarmos uma tupla de valores como valor, obteremos uma tabela muito comum com uma chave primária.

Para implementar uma tabela em globais, teremos que gerar nós mesmos linhas a partir dos valores das colunas e, em seguida, salvá-las no global usando a chave primária. Para que seja possível dividir novamente a string em colunas durante a leitura, você pode usar:

1. caracteres delimitadores.

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

2. um esquema rígido em que cada campo ocupa um número predeterminado de bytes. Como é feito em bancos de dados relacionais.
3. uma função especial $LB (disponível em Cache), que cria uma sequência de valores.

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

Curiosamente, não é difícil usar globais para fazer algo semelhante aos índices secundários em bancos de dados relacionais. Vamos chamar essas estruturas de índices globais. Um índice global é uma árvore auxiliar para pesquisar rapidamente campos que não fazem parte da chave primária do global principal. Para preenchê-lo e usá-lo, você precisa escrever um código adicional.

Vamos criar um índice global na primeira coluna.

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

Agora, para pesquisar rapidamente as informações na primeira coluna, temos que olhar para o global ^i e encontre as chaves primárias (id) correspondentes ao valor desejado da primeira coluna.

Ao inserir um valor, podemos criar imediatamente o valor e o índice global para os campos obrigatórios. E para maior confiabilidade, vamos envolver tudo em uma transação.

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

Detalhes sobre como fazer isso em M tabelas em globais, emulação de índices secundários.

Essas tabelas funcionarão tão rapidamente quanto em bancos de dados tradicionais (ou até mais rápido) se as funções para inserir/atualizar/excluir linhas forem escritas em COS/M e compiladas.Verifiquei esta declaração com testes em massa INSERT e SELECT em uma tabela de duas colunas, inclusive usando os comandos TSTART e TCOMMIT (transações).

Não testei cenários mais complexos com acesso simultâneo e transações paralelas.

Sem o uso de transações, a taxa de inserção foi de 778 inserções/segundo por milhão de valores.
Com 300 milhões de valores – 422 inserções/segundo.

Ao usar transações – 572 inserções/segundo para 082 milhões de inserções. Todas as operações foram realizadas a partir do código M compilado.
Os discos rígidos são normais, não SSD. RAID5 com write-back. Processador Phenom II 1100T.

Para testar um banco de dados SQL de maneira semelhante, você precisa escrever um procedimento armazenado que realizará inserções em um loop. Ao testar o MySQL 5.5 (armazenamento InnoDB), usando este método, recebi números não superiores a 11 mil inserções por segundo.
Sim, a implementação de tabelas em globais parece mais complexa do que em bancos de dados relacionais. Portanto, os bancos de dados industriais globais têm acesso SQL para simplificar o trabalho com dados tabulares.

Em geral, se o esquema de dados não muda com frequência, a velocidade de inserção não é crítica e todo o banco de dados pode ser facilmente representado na forma de tabelas normalizadas, então é mais fácil trabalhar com SQL, pois fornece um maior nível de abstração .

Neste caso específico eu queria mostrar que globais podem atuar como construtores para a criação de outros bancos de dados. Como um assembler no qual outras linguagens podem ser escritas. Aqui estão alguns exemplos de como você pode criar análogos em globais valores-chave, listas, conjuntos, bancos de dados tabulares e orientados a documentos.

Se você precisar criar algum tipo de banco de dados não padrão com o mínimo de esforço, então você deve procurar os globais.

3.3 Caso especial 3. Árvore de dois níveis, cada nó do segundo nível possui um número fixo de ramos

Você provavelmente adivinhou: esta é uma implementação alternativa de tabelas em globais. Vamos comparar esta implementação com a anterior.

Tabelas em uma árvore de dois níveis vs. em uma árvore de nível único.

Contras
Prós

1. Mais lento para inserção, pois é necessário definir o número de nós igual ao número de colunas.
2. Mais consumo de espaço em disco. Já os índices globais (entendidos como índices de array) com nomes de colunas ocupam espaço em disco e são duplicados para cada linha.

1. Acesso mais rápido aos valores de colunas individuais, pois não há necessidade de analisar a string. De acordo com meus testes, é 11,5% mais rápido em 2 colunas e mais em um número maior de colunas.
2. Mais fácil de alterar o esquema de dados
3. Código mais claro

Conclusão: não para todos. Como a velocidade é um dos principais benefícios dos globais, não faz muito sentido usar essa implementação, já que ela provavelmente não terá um desempenho mais rápido do que tabelas em bancos de dados relacionais.

3.4 Caso geral. Árvores e árvores ordenadas

Qualquer estrutura de dados que possa ser representada como uma árvore se ajusta perfeitamente aos globais.

3.4.1 Objetos com subobjetos

Esta é a área de uso tradicional dos globais. Na área médica existe um grande número de doenças, medicamentos, sintomas e métodos de tratamento. É irracional criar uma tabela com um milhão de campos para cada paciente. Além disso, 99% dos campos estarão vazios.

Imagine um banco de dados SQL de tabelas: “paciente” ~ 100 campos, “Medicina” - 000 campos, “Terapia” - 100 campos, “Complicações” - 000 campos, etc. e assim por diante. Ou você pode criar um banco de dados com milhares de tabelas, cada uma para um tipo específico de paciente (e elas podem se sobrepor!), tratamentos, medicamentos e milhares de outras tabelas para conexões entre essas tabelas.

Os globais são ideais para a medicina, pois permitem criar para cada paciente uma descrição precisa de seu histórico médico, diversas terapias e ações dos medicamentos, em forma de árvore, sem desperdiçar espaço extra em disco em colunas vazias, como faria ser o caso em um caso relacional.

Usando globais é conveniente criar um banco de dados com dados sobre pessoas, quando é importante acumular e sistematizar o máximo de informações diversas sobre o cliente. Isso é muito procurado em medicina, bancos, marketing, arquivamento e outras áreas

.
Claro, em SQL você também pode emular uma árvore com apenas algumas tabelas (Eav, 1,2,3,4,5,6,7,8,9,10), no entanto, isso é significativamente mais complicado e será mais lento. Essencialmente, você teria que escrever um global que funcionasse em tabelas e ocultar todo o trabalho com tabelas sob uma camada de abstração. É errado emular tecnologia de nível inferior (globais) usando tecnologia de nível superior (SQL). Inapropriado.

Não é nenhum segredo que alterar o esquema de dados em tabelas gigantes (ALTER TABLE) pode levar bastante tempo. MySQL, por exemplo, faz ALTER TABLE ADD|DROP COLUMN copiando completamente as informações da tabela antiga para a nova tabela (mecanismos MyISAM e InnoDB testados). O que pode travar um banco de dados funcional com bilhões de registros por dias, senão semanas.

Alterar a estrutura de dados se usarmos globais não nos custa nada. A qualquer momento podemos adicionar quaisquer novas propriedades necessárias a qualquer objeto, em qualquer nível da hierarquia. As alterações associadas à renomeação de ramificações podem ser executadas em segundo plano em um banco de dados em execução.


Portanto, quando se trata de armazenar objetos com um grande número de propriedades opcionais, os globais são uma ótima escolha.

Além disso, lembro que o acesso a qualquer uma das propriedades é instantâneo, pois no global todos os caminhos são árvores B.

Os bancos de dados globais, em geral, são um tipo de banco de dados orientado a documentos com capacidade de armazenar informações hierárquicas. Portanto, os bancos de dados orientados a documentos podem competir com os globais na área de armazenamento de registros médicos. Mas ainda não é exatamente o mesmoVamos usar o MongoDB para comparação. Neste domínio perde para os globais pelos seguintes motivos:

1. Tamanho do documento. A unidade de armazenamento é um texto em formato JSON (mais precisamente BSON) com volume máximo de cerca de 16 MB. A restrição foi feita especificamente para que o banco de dados JSON não fique lento durante a análise se um enorme documento JSON for armazenado nele e depois acessado pelos campos. Este documento deve conter todas as informações sobre o paciente. Todos nós sabemos o quão densos podem ser os registros dos pacientes. O tamanho máximo do cartão de 16 MB põe fim imediatamente aos pacientes cujo cartão de doença inclui arquivos de ressonância magnética, exames de raios X e outros estudos. Em um ramo do global você pode ter gigabytes e terabytes de informação. Em princípio, podemos pôr fim a isto, mas continuarei.
2. Tempo de consciência/alteração/exclusão de novas propriedades no prontuário do paciente. Esse banco de dados deve ler o mapa inteiro na memória (isso é uma grande quantidade!), analisar BSON, adicionar/alterar/excluir um novo nó, atualizar índices, compactá-lo em BSON e salvá-lo em disco. Um global só precisa acessar uma propriedade específica e manipulá-la.
3. Acesso rápido a propriedades individuais. Com muitas propriedades em um documento e sua estrutura multinível, o acesso às propriedades individuais será mais rápido devido ao fato de que cada caminho no global é uma árvore B. No BSON, você deve analisar linearmente o documento para encontrar a propriedade desejada.

3.3.2 Matrizes associativas

Matrizes associativas (mesmo com matrizes aninhadas) se encaixam perfeitamente em globais. Por exemplo, tal array do PHP será exibido na primeira figura 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 hierárquicos: XML, JSON

Também facilmente armazenado em globais. Pode ser disposto de diferentes maneiras para armazenamento.

XML
A maneira mais fácil de decompor XML em globais é armazenar atributos de tags em nós. E se for necessário acesso rápido aos atributos da tag, podemos movê-los para ramificações separadas.

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

No COS isso corresponderia ao código:

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

Nota: Para XML, JSON e matrizes associativas, você pode criar muitas maneiras diferentes de exibição em globais. Nesse caso, não refletimos a ordem das subtags na tag note. Globalmente ^xml as subtags serão exibidas em ordem alfabética. Para refletir estritamente a ordem, você pode usar, por exemplo, a seguinte exibição:

JSON.
A primeira imagem da seção 3.3.1 mostra um 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 relações hierárquicas

Exemplos: a estrutura dos escritórios de vendas, a localização das pessoas numa estrutura de MLM, a base de dados de vagas no xadrez.

Banco de dados de estreia. Você pode usar a estimativa da força do golpe como o valor do índice do nó global. Então, para escolher o movimento mais forte, bastará escolher o galho de maior peso. No global, todos os ramos em cada nível serão classificados pela força do movimento.

A estrutura dos escritórios de vendas, a estrutura das pessoas no MLM. Os nós podem armazenar determinados valores de cache que refletem as características de toda a subárvore. Por exemplo, o volume de vendas de uma determinada subárvore. A qualquer momento podemos obter um número que reflecte as realizações de qualquer ramo.

4. Em que casos é mais benéfico usar globais?

A primeira coluna apresenta casos em que você obterá um ganho significativo de velocidade usando globais, e a segunda quando o design ou modelo de dados será simplificado.

velocidade
Facilidade de processamento/apresentação de dados

1. Inserção [com classificação automática em cada nível], [indexação por chave mestra]
2. Removendo subárvores
3. Objetos com muitas propriedades aninhadas que requerem acesso individual
4. Estrutura hierárquica com a capacidade de ignorar ramificações filhas de qualquer ramificação, mesmo as inexistentes
5. Percurso em profundidade de subárvores

1. Objetos/entidades com um grande número de propriedades/entidades opcionais [e/ou aninhadas]
2. Dados sem esquema. Quando muitas vezes novas propriedades podem aparecer e as antigas desaparecerem.
3. Você precisa criar um banco de dados personalizado.
4. Bases de caminhos e árvores de decisão. Quando for conveniente representar caminhos como uma árvore.
5. Removendo estruturas hierárquicas sem usar recursão

Extensão “Globais são espadas de tesouro para armazenamento de dados. Matrizes esparsas. Parte 3".

Aviso Legal: Este artigo e meus comentários são minha opinião e não têm relação com a posição oficial da InterSystems Corporation.

Fonte: habr.com