Olá, Habr! Apresento a sua atenção uma tradução do artigo
"Como funciona um banco de dados relacional".

Quando se trata de bancos de dados relacionais, não posso deixar de pensar que algo está faltando. Eles são usados em todos os lugares. Existem muitos bancos de dados diferentes disponíveis, desde o pequeno e útil SQLite até o poderoso Teradata. Mas existem apenas alguns artigos que explicam como funciona o banco de dados. Você pode pesquisar por si mesmo usando "howdoesarelationaldatabasework" para ver quantos resultados existem. Além disso, esses artigos são curtos. Se você estiver procurando pelas tecnologias mais recentes (BigData, NoSQL ou JavaScript), encontrará artigos mais detalhados explicando como elas funcionam.

Os bancos de dados relacionais são muito antigos e enfadonhos para serem explicados fora dos cursos universitários, artigos de pesquisa e livros?

Como desenvolvedor, odeio usar algo que não entendo. E se os bancos de dados são usados há mais de 40 anos, deve haver uma razão. Ao longo dos anos, passei centenas de horas para realmente entender essas estranhas caixas pretas que uso todos os dias. Bancos de dados relacionais muito interessante porque eles baseado em conceitos úteis e reutilizáveis. Se você está interessado em entender um banco de dados, mas nunca teve tempo ou disposição para se aprofundar neste amplo tópico, você deve aproveitar este artigo.

Embora o título deste artigo seja explícito, o objetivo deste artigo não é entender como usar o banco de dados. portanto, você já deve saber como escrever uma solicitação de conexão simples e consultas básicas CRU; caso contrário, você pode não entender este artigo. Essa é a única coisa que você precisa saber, eu explico o resto.

Começarei com alguns princípios básicos da ciência da computação, como complexidade de tempo de algoritmos (BigO). Eu sei que alguns de vocês odeiam esse conceito, mas sem ele vocês não conseguirão entender as complexidades do banco de dados. Como este é um assunto enorme, vou me concentrar em o que eu acho importante: como o banco de dados processa SQL pedido. vou apenas apresentar conceitos básicos de banco de dadospara que no final do artigo você tenha uma ideia do que está acontecendo nos bastidores.

Como este é um artigo longo e técnico que envolve muitos algoritmos e estruturas de dados, reserve um tempo para lê-lo. Alguns conceitos podem ser difíceis de compreender; você pode ignorá-los e ainda assim ter uma ideia geral.

Para os mais experientes, este artigo está dividido em 3 partes:

Visão geral dos componentes de banco de dados de baixo e alto nível
Visão geral do processo de otimização de consulta
Visão geral do gerenciamento de transações e buffer pool

Voltar à rotina

Anos atrás (em uma galáxia muito, muito distante...), os desenvolvedores precisavam saber exatamente o número de operações que estavam codificando. Eles conheciam de cor seus algoritmos e estruturas de dados porque não podiam se dar ao luxo de desperdiçar a CPU e a memória de seus computadores lentos.

Nesta parte, lembrarei alguns desses conceitos, pois são essenciais para a compreensão do banco de dados. Também apresentarei o conceito índice de banco de dados.

O(1) versus O(n2)

Hoje em dia, muitos desenvolvedores não se importam com a complexidade temporal dos algoritmos... e eles estão certos!

Mas quando você está lidando com muitos dados (não estou falando de milhares) ou se está lutando em milissegundos, torna-se fundamental entender esse conceito. E como você pode imaginar, os bancos de dados precisam lidar com ambas as situações! Não vou fazer você gastar mais tempo do que o necessário para entender o que quero dizer. Isso nos ajudará a entender o conceito de otimização baseada em custos posteriormente (custo baseado otimização).

Conceito

Complexidade de tempo do algoritmo usado para ver quanto tempo um algoritmo levará para ser concluído para uma determinada quantidade de dados. Para descrever essa complexidade, usamos a notação matemática grande O. Essa notação é usada com uma função que descreve quantas operações um algoritmo precisa para um determinado número de entradas.

Por exemplo, quando digo "este algoritmo tem complexidade O(some_function())", significa que o algoritmo requer operações some_function(a_certain_amount_of_data) para processar uma certa quantidade de dados.

Neste caso, Não é a quantidade de dados que importa**, de outra forma ** como o número de operações aumenta com o aumento do volume de dados. A complexidade do tempo não fornece um número exato de operações, mas é uma boa maneira de estimar o tempo de execução.

Neste gráfico você pode ver o número de operações versus a quantidade de dados de entrada para diferentes tipos de complexidades de tempo de algoritmo. Usei uma escala logarítmica para exibi-los. Em outras palavras, a quantidade de dados aumenta rapidamente de 1 para 1 bilhão. Podemos ver que:

O(1) ou complexidade constante permanece constante (caso contrário, não seria chamada de complexidade constante).
O(log(n)) permanece baixo mesmo com bilhões de dados.
Pior dificuldade - O(n2), onde o número de operações cresce rapidamente.
As outras duas complicações aumentam com a mesma rapidez.

Примеры

Com uma pequena quantidade de dados, a diferença entre O(1) e O(n2) é insignificante. Por exemplo, digamos que você tenha um algoritmo que precisa processar 2000 elementos.

O algoritmo O(1) custará 1 operação
O algoritmo O(log(n)) custará 7 operações
O algoritmo O(n) custará 2 operações
O algoritmo O(n*log(n)) custará 14 operações
O algoritmo O(n2) custará 4 de operações

A diferença entre O(1) e O(n2) parece grande (4 milhões de operações), mas você perderá no máximo 2 ms, apenas tempo para piscar os olhos. Na verdade, os processadores modernos podem processar centenas de milhões de operações por segundo. É por isso que o desempenho e a otimização não são um problema em muitos projetos de TI.

Como eu disse, ainda é importante conhecer esse conceito ao trabalhar com grandes quantidades de dados. Se desta vez o algoritmo tiver que processar 1 de elementos (o que não é muito para um banco de dados):

O algoritmo O(1) custará 1 operação
O algoritmo O(log(n)) custará 14 operações
O algoritmo O(n) custará 1 de operações
O algoritmo O(n*log(n)) custará 14 de operações
O algoritmo O(n2) custará 1 de operações

Não fiz as contas, mas diria que com o algoritmo O(n2) você tem tempo para tomar um café (até dois!). Se você adicionar outro 0 ao volume de dados, terá tempo para tirar uma soneca.

Vamos mais fundo

Para sua informação:

Uma boa pesquisa na tabela hash encontra um elemento em O(1).
Pesquisar uma árvore bem balanceada produz resultados em O(log(n)).
Pesquisar um array produz resultados em O(n).
Os melhores algoritmos de classificação têm complexidade O(n*log(n)).
Um algoritmo de classificação ruim tem complexidade O(n2).

Nota: Nas partes seguintes veremos esses algoritmos e estruturas de dados.

Existem vários tipos de complexidade de tempo de algoritmo:

cenário médio
Melhor cenário possível
e pior cenário

A complexidade do tempo costuma ser o pior cenário.

Eu estava falando apenas sobre a complexidade de tempo do algoritmo, mas a complexidade também se aplica a:

consumo de memória do algoritmo
algoritmo de consumo de E/S de disco

Claro, existem complicações piores que n2, por exemplo:

n4: isso é terrível! Alguns dos algoritmos mencionados possuem essa complexidade.
3n: isso é ainda pior! Um dos algoritmos que veremos no meio deste artigo tem essa complexidade (e na verdade é usado em muitos bancos de dados).
fatorial n: você nunca obterá seus resultados mesmo com uma pequena quantidade de dados.
nn: Se você se depara com essa complexidade, você deve se perguntar se esse é realmente o seu campo de atuação...

Nota: não dei a definição real da designação O grande, apenas uma ideia. Você pode ler este artigo em Wikipedia para a definição real (assintótica).

MesclarClassificação

O que você faz quando precisa classificar uma coleção? O que? Você chama a função sort()... Ok, boa resposta... Mas para um banco de dados, você deve entender como essa função sort() funciona.

Existem vários algoritmos de classificação bons, então vou me concentrar nos mais importantes: classificação por mesclagem. Você pode não entender por que a classificação de dados é útil agora, mas deveria entender depois da parte de otimização da consulta. Além disso, entender a classificação por mesclagem nos ajudará mais tarde a entender a operação comum de junção de banco de dados chamada fundir juntar (associação de fusão).

Mesclar

Como muitos algoritmos úteis, a classificação por mesclagem depende de um truque: combinar 2 matrizes classificadas de tamanho N/2 em uma matriz classificada de N elementos custa apenas N operações. Esta operação é chamada de fusão.

Vamos ver o que isso significa com um exemplo simples:

Esta figura mostra que para construir o array final classificado de 8 elementos, você só precisa iterar uma vez nos 2 arrays de 4 elementos. Como ambas as matrizes de 4 elementos já estão classificadas:

1) você compara os dois elementos atuais em duas matrizes (no início atual = primeiro)
2) então pegue o menor e coloque-o em uma matriz de 8 elementos
3) e vá para o próximo elemento na matriz onde você pegou o menor elemento
e repita 1,2,3 até chegar ao último elemento de uma das matrizes.
Então você pega os elementos restantes do outro array para colocá-los em um array de 8 elementos.

Isso funciona porque ambas as matrizes de 4 elementos são classificadas e você não precisa "voltar" nessas matrizes.

Agora que entendemos o truque, aqui está meu pseudocódigo para mesclagem:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

A classificação por mesclagem divide um problema em problemas menores e, em seguida, encontra os resultados dos problemas menores para obter o resultado do problema original (nota: esse tipo de algoritmo é chamado de divisão e conquista). Se você não entende esse algoritmo, não se preocupe; Não entendi na primeira vez que vi. Se puder ajudá-lo, vejo este algoritmo como um algoritmo de duas fases:

Fase de divisão, onde a matriz é dividida em matrizes menores
A fase de classificação é onde pequenos arrays são combinados (usando união) para formar um array maior.

Fase de divisão

Na fase de divisão, o array é dividido em arrays unitários em 3 etapas. O número formal de etapas é log(N) (já que N=8, log(N) = 3).

Como eu sei disso?

Eu sou um gênio! Em uma palavra – matemática. A ideia é que cada etapa divida o tamanho do array original por 2. O número de etapas é o número de vezes que você pode dividir o array original em dois. Esta é a definição exata de um logaritmo (base 2).

Fase de classificação

Na fase de classificação, você começa com matrizes unitárias (elemento único). Durante cada etapa você aplica múltiplas operações de mesclagem e o custo total é N = 8 operações:

Na primeira etapa você tem 4 mesclagens que custam 2 operações cada
Na segunda etapa você tem 2 mesclagens que custam 4 operações cada
Na terceira etapa você tem 1 mesclagem que custa 8 operações

Como existem etapas log(N), custo totalN * log(N) operações.

Vantagens da classificação por mesclagem

Por que esse algoritmo é tão poderoso?

Porque:

Você pode alterá-lo para reduzir o consumo de memória para não criar novos arrays, mas modificar diretamente o array de entrada.

Nota: este tipo de algoritmo é chamado in-lugar (classificação sem memória adicional).

Você pode alterá-lo para usar espaço em disco e uma pequena quantidade de memória ao mesmo tempo, sem incorrer em sobrecarga significativa de E/S de disco. A ideia é carregar na memória apenas as partes que estão sendo processadas no momento. Isso é importante quando você precisa classificar uma tabela de vários gigabytes com apenas um buffer de memória de 100 megabytes.

Nota: este tipo de algoritmo é chamado classificação externa.

Você pode alterá-lo para ser executado em vários processos/threads/servidores.

Por exemplo, a classificação por mesclagem distribuída é um dos principais componentes Hadoop (que é uma estrutura em big data).

Este algoritmo pode transformar chumbo em ouro (sério!).

Esse algoritmo de classificação é usado na maioria (se não em todos) dos bancos de dados, mas não é o único. Se você quiser saber mais, pode ler isto trabalho de pesquisa, que discute os prós e os contras dos algoritmos comuns de classificação de banco de dados.

Matriz, Árvore e Tabela Hash

Agora que entendemos a ideia de complexidade e classificação de tempo, devo falar sobre três estruturas de dados. Isto é importante porque eles são a base dos bancos de dados modernos. Também apresentarei o conceito índice de banco de dados.

Matriz

Uma matriz bidimensional é a estrutura de dados mais simples. Uma tabela pode ser considerada um array. Por exemplo:

Esta matriz bidimensional é uma tabela com linhas e colunas:

Cada linha representa uma entidade
As colunas armazenam propriedades que descrevem a entidade.
Cada coluna armazena dados de um tipo específico (inteiro, string, data...).

Isso é conveniente para armazenar e visualizar dados, porém, quando você precisa encontrar um valor específico, não é adequado.

Por exemplo, se você quiser encontrar todos os caras que trabalham no Reino Unido, precisará examinar cada linha para determinar se essa linha pertence ao Reino Unido. Vai custar N transaçõesOnde N - número de linhas, o que não é ruim, mas poderia haver uma forma mais rápida? Agora é hora de conhecermos as árvores.

Nota: A maioria dos bancos de dados modernos fornece arrays estendidos para armazenar tabelas de forma eficiente: tabelas organizadas por heap e tabelas organizadas por índice. Mas isso não altera o problema de encontrar rapidamente uma condição específica em um grupo de colunas.

Árvore e índice do banco de dados

Uma árvore de pesquisa binária é uma árvore binária com uma propriedade especial, a chave em cada nó deve ser:

maior que todas as chaves armazenadas na subárvore esquerda
menos que todas as chaves armazenadas na subárvore certa

Vamos ver o que isso significa visualmente

Idéia

Esta árvore possui N = 15 elementos. Digamos que estou procurando 208:

Começo na raiz cuja chave é 136. Como 136<208, olho para a subárvore direita do nó 136.
398>208, portanto, estou olhando para a subárvore esquerda do nó 398
250>208, portanto, estou olhando para a subárvore esquerda do nó 250
200<208, portanto estou olhando para a subárvore direita do nó 200. Mas 200 não tem subárvore certa, valor não existe (porque se existir, estará na subárvore certa 200).

Agora digamos que estou procurando 40

Começo na raiz cuja chave é 136. Como 136 > 40, olho para a subárvore esquerda do nó 136.
80 > 40, portanto estou olhando para a subárvore esquerda do nó 80
40 = 40, nó existe. Eu recupero o ID da linha dentro do nó (não mostrado na imagem) e procuro na tabela o ID da linha fornecido.
Conhecer o ID da linha me permite saber exatamente onde os dados estão na tabela, para que eu possa recuperá-los instantaneamente.

No final, ambas as pesquisas me custarão o número de níveis dentro da árvore. Se você ler a parte sobre classificação por mesclagem com atenção, verá que existem níveis de log (N). Acontece que, log de custo de pesquisa (N), nada mal!

Voltemos ao nosso problema

Mas isso é muito abstrato, então voltemos ao nosso problema. Em vez de um número inteiro simples, imagine uma string que represente o país de alguém na tabela anterior. Digamos que você tenha uma árvore que contenha o campo “país” (coluna 3) da tabela:

Se você quiser saber quem trabalha no Reino Unido
você olha para a árvore para obter o nó que representa a Grã-Bretanha
dentro de "UKnode" você encontrará a localização dos registros dos trabalhadores do Reino Unido.

Esta pesquisa custará operações log(N) em vez de N operações se você usar o array diretamente. O que você acabou de apresentar foi índice de banco de dados.

Você pode construir uma árvore de índice para qualquer grupo de campos (string, número, 2 linhas, número e string, data...), desde que tenha uma função para comparar chaves (ou seja, grupos de campos) para poder definir ordem entre as chaves (que é o caso de qualquer tipo básico no banco de dados).

B+TreeIndex

Embora esta árvore funcione bem para obter um valor específico, há um GRANDE problema quando você precisa obter vários elementos entre dois valores. Isso custará O(N) porque você terá que olhar para cada nó da árvore e verificar se está entre esses dois valores (por exemplo, com uma travessia ordenada da árvore). Além disso, esta operação não é compatível com E/S de disco, pois é necessário ler a árvore inteira. Precisamos encontrar uma maneira de executar com eficiência solicitação de intervalo. Para resolver este problema, os bancos de dados modernos usam uma versão modificada da árvore anterior chamada B+Tree. Em uma árvore B+Tree:

apenas os nós mais baixos (folhas) guardar informação (localização das linhas na tabela relacionada)
o resto dos nós estão aqui para roteamento para o nó correto durante a pesquisa.

Como você pode ver, há mais nós aqui (duas vezes). Na verdade, você tem nós adicionais, "nós de decisão", que o ajudarão a encontrar o nó correto (que armazena a localização das linhas na tabela associada). Mas a complexidade da pesquisa ainda é O(log(N)) (há apenas mais um nível). A grande diferença é que nós no nível inferior estão conectados aos seus sucessores.

Com esta Árvore B+, se você procura valores entre 40 e 100:

Você só precisa procurar 40 (ou o valor mais próximo depois de 40 se 40 não existir) como fez com a árvore anterior.
Em seguida, colete 40 herdeiros usando links diretos de herdeiros até chegar a 100.

Digamos que você encontre M sucessores e a árvore tenha N nós. Encontrar um nó específico custa log(N) como a árvore anterior. Mas depois de obter esse nó, você obterá M sucessores em M operações com referências aos seus sucessores. Esta pesquisa custa apenas M+log(N) operações em comparação com N operações na árvore anterior. Além disso, você não precisa ler a árvore completa (apenas nós M+log(N)), o que significa menos uso de disco. Se M for pequeno (por exemplo, 200 linhas) e N for grande (1 de linhas), haverá uma GRANDE diferença.

Mas há novos problemas aqui (de novo!). Se você adicionar ou excluir uma linha no banco de dados (e, portanto, no índice B+Tree associado):

você deve manter a ordem entre os nós dentro de uma árvore B+, caso contrário não será capaz de encontrar os nós dentro de uma árvore não classificada.
você deve manter o número mínimo possível de níveis em B+Tree, caso contrário a complexidade de tempo O(log(N)) se torna O(N).

Em outras palavras, B+Tree deve ser auto-ordenado e equilibrado. Felizmente, isso é possível com operações inteligentes de exclusão e inserção. Mas isso tem um custo: inserções e exclusões em uma árvore B+ custam O(log(N)). É por isso que alguns de vocês já ouviram isso usar muitos índices não é uma boa ideia. Realmente, você está retardando a inserção/atualização/exclusão rápida de uma linha em uma tabelaporque o banco de dados precisa atualizar os índices da tabela usando uma operação cara O(log(N)) para cada índice. Além disso, adicionar índices significa mais carga de trabalho para gerenciador de transações (será descrito no final do artigo).

Para mais detalhes, você pode ver o artigo da Wikipedia em B+Árvore. Se você quiser um exemplo de implementação de B+Tree em um banco de dados, dê uma olhada Este artigo и Este artigo de um desenvolvedor líder de MySQL. Ambos se concentram em como o InnoDB (o mecanismo MySQL) lida com índices.

Nota: Um leitor me disse que, devido às otimizações de baixo nível, a árvore B+ deveria estar completamente balanceada.

Tabela hash

Nossa última estrutura de dados importante é a tabela hash. Isto é muito útil quando você deseja pesquisar valores rapidamente. Além disso, compreender uma tabela hash nos ajudará mais tarde a entender uma operação comum de junção de banco de dados chamada hash join ( junção de hash). Esta estrutura de dados também é usada pelo banco de dados para armazenar algumas coisas internas (por exemplo, mesa de bloqueio ou conjunto de buffers, veremos esses dois conceitos posteriormente).

Uma tabela hash é uma estrutura de dados que encontra rapidamente um elemento por sua chave. Para construir uma tabela hash você precisa definir:

pista para seus elementos
função hash para chaves. Os hashes de chave computados fornecem a localização dos elementos (chamados segmentos ).
função para comparar chaves. Depois de encontrar o segmento correto, você deve encontrar o elemento que procura dentro do segmento usando esta comparação.

Exemplo simples

Vejamos um exemplo claro:

Esta tabela hash possui 10 segmentos. Como sou preguiçoso, imaginei apenas 5 segmentos, mas sei que você é inteligente, então vou deixar você imaginar os outros 5 sozinho. Usei uma função hash módulo 10 da chave. Em outras palavras, armazeno apenas o último dígito da chave do elemento para encontrar seu segmento:

se o último dígito for 0, o elemento cai no segmento 0,
se o último dígito for 1, o elemento cai no segmento 1,
se o último dígito for 2, o elemento cai na área 2,
...

A função de comparação que usei é simplesmente igualdade entre dois inteiros.

Digamos que você queira obter o elemento 78:

A tabela hash calcula o código hash para 78, que é 8.
A tabela hash analisa o segmento 8 e o primeiro elemento encontrado é 78.
Ela devolve o item 78 para você
A pesquisa custa apenas 2 operações (um para calcular o valor do hash e outro para procurar o elemento dentro do segmento).

Agora digamos que você deseja obter o elemento 59:

A tabela hash calcula o código hash para 59, que é 9.
A tabela hash pesquisa no segmento 9, o primeiro elemento encontrado é 99. Como 99!=59, o elemento 99 não é um elemento válido.
Usando a mesma lógica, são retirados o segundo elemento (9), o terceiro (79), ..., o último (29).
Elemento não encontrado.
A busca custou 7 operações.

Boa função hash

Como você pode ver, dependendo do valor que você procura, o custo não é o mesmo!

Se eu alterar agora a função hash módulo 1 da chave (ou seja, pegando os últimos 000 dígitos), a segunda pesquisa custará apenas 000 operação, pois não há elementos no segmento 6. O verdadeiro desafio é encontrar uma boa função hash que crie buckets contendo um número muito pequeno de elementos.

No meu exemplo, encontrar uma boa função hash é fácil. Mas este é um exemplo simples, encontrar uma boa função hash é mais difícil quando a chave é:

string (por exemplo - sobrenome)
2 linhas (por exemplo - sobrenome e nome)
2 linhas e data (por exemplo - sobrenome, nome e data de nascimento)
...

Com uma boa função hash, as pesquisas na tabela hash custam O(1).

Matriz versus tabela hash

Por que não usar um array?

Hum, boa pergunta.

A tabela hash pode ser parcialmente carregado na memória, e os segmentos restantes podem permanecer no disco.
Com um array você deve usar espaço contíguo na memória. Se você estiver carregando uma mesa grande é muito difícil encontrar espaço contínuo suficiente.
Para uma tabela hash, você pode selecionar a chave desejada (por exemplo, país e sobrenome da pessoa).

Para mais informações, você pode ler o artigo sobre JavaHashMap, que é uma implementação eficiente de uma tabela hash; você não precisa entender Java para entender os conceitos abordados neste artigo.

Fonte: habr.com

Como funcionam os bancos de dados relacionais (parte 1)