Ola Habr! Presento á súa atención a tradución do artigo
"Como funciona unha base de datos relacional".

Cando se trata de bases de datos relacionais non podo evitar pensar que falta algo. Utilízanse en todas partes. Hai moitas bases de datos dispoñibles, desde o pequeno e útil SQLite ata o poderoso Teradata. Pero só hai algúns artigos que explican como funciona a base de datos. Podes buscar por ti mesmo usando "howdoesarelationaldatabasework" para ver os poucos resultados que hai. Ademais, estes artigos son breves. Se estás buscando as tecnoloxías máis avanzadas (BigData, NoSQL ou JavaScript), atoparás artigos máis detallados que explican como funcionan.

As bases de datos relacionais son demasiado antigas e aburridas para ser explicadas fóra dos cursos universitarios, traballos de investigación e libros?

Como programador, odio usar algo que non entendo. E se as bases de datos se usan durante máis de 40 anos, debe haber unha razón. Ao longo dos anos, pasei centos de horas para comprender realmente estas estrañas caixas negras que uso todos os días. Bases de datos relacionais moi interesante porque eles baseado en conceptos útiles e reutilizables. Se estás interesado en comprender unha base de datos, pero nunca tiveches tempo ou ganas de afondar neste amplo tema, deberías gozar deste artigo.

Aínda que o título deste artigo é explícito, o propósito deste artigo non é entender como usar a base de datos. Polo tanto, xa debería saber escribir unha solicitude de conexión sinxela e consultas básicas CRUDO; se non, pode que non entenda este artigo. Iso é o único que debes saber, o resto explico.

Comezarei con algúns conceptos básicos de informática, como a complexidade temporal dos algoritmos (BigO). Sei que algúns de vostedes odian este concepto, pero sen el non poderán comprender as complejidades da base de datos. Xa que este é un tema enorme, Voume centrar o que penso que é importante: como se procesa a base de datos SQL investigación. Só presentarei conceptos básicos de bases de datospara que ao final do artigo teñas unha idea do que está a pasar baixo o capó.

Dado que este é un artigo longo e técnico que inclúe moitos algoritmos e estruturas de datos, tómate o teu tempo para lelo. Algúns conceptos poden ser difíciles de entender; podes omitilos e aínda tes a idea xeral.

Para os máis informados entre vós, este artigo está dividido en 3 partes:

Visión xeral dos compoñentes de base de datos de baixo e alto nivel
Visión xeral do proceso de optimización de consultas
Visión xeral da xestión de transaccións e agrupacións de búfer

Volver ao básico

Hai anos (nunha galaxia moi, moi lonxe...), os desenvolvedores tiñan que saber exactamente o número de operacións que estaban codificando. Coñecían os seus algoritmos e estruturas de datos de memoria porque non podían permitirse o luxo de desperdiciar a CPU e a memoria dos seus ordenadores lentos.

Nesta parte recordareivos algúns destes conceptos xa que son esenciais para comprender a base de datos. Tamén vou presentar o concepto índice de base de datos.

O(1) vs O(n2)

Hoxe en día, a moitos desenvolvedores non lles importa a complexidade temporal dos algoritmos... e teñen razón!

Pero cando estás a tratar con moitos datos (non falo de miles) ou se estás loitando en milisegundos, tórnase fundamental comprender este concepto. E como podes imaxinar, as bases de datos teñen que facer fronte a ambas situacións! Non vou facer que dedique máis tempo do necesario para entender o punto. Isto axudaranos a comprender o concepto de optimización baseada en custos máis tarde (custa baseado optimización).

Concepto

Complexidade temporal do algoritmo usado para ver canto tempo tardará en executar un algoritmo para unha determinada cantidade de datos. Para describir esta complexidade, usamos a notación matemática grande O. Esta notación úsase cunha función que describe cantas operacións necesita un algoritmo para un determinado número de entradas.

Por exemplo, cando digo "este algoritmo ten complexidade O(some_function())", quere dicir que o algoritmo require algunha_función(a_certain_amount_of_data) operacións para procesar unha determinada cantidade de datos.

Neste caso, Non é a cantidade de datos o que importa**, en caso contrario ** como aumenta o número de operacións co aumento do volume de datos. A complexidade do tempo non proporciona un número exacto de operacións, pero é unha boa forma de estimar o tempo de execución.

Neste gráfico podes ver o número de operacións fronte á cantidade de datos de entrada para diferentes tipos de complexidades temporais do algoritmo. Usei unha escala logarítmica para mostralos. Noutras palabras, a cantidade de datos aumenta rapidamente de 1 a 1 millóns. Podemos ver que:

O(1) ou complexidade constante permanece constante (se non, non se chamaría complexidade constante).
O(sesión(n)) segue sendo baixo mesmo con miles de millóns de datos.
A peor dificultade - O(n2), onde o número de operacións crece rapidamente.
As outras dúas complicacións aumentan igual de rápido.

Exemplos

Cunha pequena cantidade de datos, a diferenza entre O(1) e O(n2) é insignificante. Por exemplo, digamos que tes un algoritmo que necesita procesar 2000 elementos.

O algoritmo O(1) custará 1 operación
O algoritmo O(log(n)) custará 7 operacións
O algoritmo O(n) custará 2 operacións
O algoritmo O(n*log(n)) custará 14 operacións
O algoritmo O(n2) custará 4 de operacións

A diferenza entre O(1) e O(n2) parece grande (4 millóns de operacións) pero perderás un máximo de 2 ms, só tempo para pestanexar os ollos. De feito, os procesadores modernos poden procesar centos de millóns de operacións por segundo. É por iso que o rendemento e a optimización non son un problema en moitos proxectos de TI.

Como dixen, aínda é importante coñecer este concepto cando se traballa con grandes cantidades de datos. Se esta vez o algoritmo ten que procesar 1 de elementos (o que non é tanto para unha base de datos):

O algoritmo O(1) custará 1 operación
O algoritmo O(log(n)) custará 14 operacións
O algoritmo O(n) custará 1 de operacións
O algoritmo O(n*log(n)) custará 14 de operacións
O algoritmo O(n2) custará 1 de operacións

Non fixen os cálculos, pero diría que co algoritmo O(n2) tes tempo para tomar un café (¡incluso dous!). Se engades outro 0 ao volume de datos, terás tempo para botar unha sesta.

Imos afondar

Para a súa información:

Unha boa procura da táboa hash atopa un elemento en O(1).
A busca dunha árbore ben equilibrada produce resultados en O(log(n)).
A busca dunha matriz produce resultados en O(n).
Os mellores algoritmos de ordenación teñen complexidade O(n*log(n)).
Un mal algoritmo de clasificación ten complexidade O(n2).

Nota: nas seguintes partes veremos estes algoritmos e estruturas de datos.

Hai varios tipos de complexidade temporal do algoritmo:

escenario de caso medio
o mellor dos casos
e o peor dos casos

A complexidade do tempo adoita ser o peor dos casos.

Só falaba da complexidade temporal do algoritmo, pero a complexidade tamén se aplica a:

consumo de memoria do algoritmo
Algoritmo de consumo de E/S de disco

Por suposto, hai complicacións peores que n2, por exemplo:

n4: isto é terrible! Algúns dos algoritmos mencionados teñen esta complexidade.
3n: isto é aínda peor! Un dos algoritmos que veremos no medio deste artigo ten esta complexidade (e en realidade úsase en moitas bases de datos).
factorial n: nunca obterás os teus resultados nin sequera cunha pequena cantidade de datos.
nn: Se atopas esta complexidade, deberías preguntarche se este é realmente o teu campo de actividade...

Nota: non che dei a definición real da designación O grande, só unha idea. Podes ler este artigo en Wikipedia para a definición real (asintótica).

MergeSort

Que fas cando necesitas ordenar unha colección? Que? Vostede chama á función sort()... Ok, boa resposta... Pero para unha base de datos, debe entender como funciona esta función sort().

Hai varios bos algoritmos de clasificación, polo que me centrarei no máis importante: fusión ordenar. Quizais non entendas por que é útil ordenar datos agora mesmo, pero deberías despois da parte de optimización de consultas. Ademais, entender a ordenación por fusión axudaranos a comprender máis tarde a operación común de unión de base de datos chamada fundir unirse (asociación de fusión).

Combinar

Como moitos algoritmos útiles, a ordenación por fusión depende dun truco: combinar 2 matrices ordenadas de tamaño N/2 nunha matriz ordenada de N elementos custa só N operacións. Esta operación chámase fusión.

Vexamos o que significa isto cun exemplo sinxelo:

Esta figura mostra que para construír a matriz final de 8 elementos, só precisa iterar unha vez sobre as dúas matrices de 2 elementos. Xa que as dúas matrices de 4 elementos xa están ordenadas:

1) compara os dous elementos actuais en dúas matrices (ao principio actual = primeiro)
2) A continuación, tome o máis pequeno para poñelo nunha matriz de 8 elementos
3) e pase ao seguinte elemento da matriz onde colleu o elemento máis pequeno
e repita 1,2,3 ata chegar ao último elemento dunha das matrices.
Despois colle os elementos restantes da outra matriz para poñelos nunha matriz de 8 elementos.

Isto funciona porque ambas as matrices de 4 elementos están ordenadas e, polo tanto, non tes que "volver" nesas matrices.

Agora que entendemos o truco, aquí está o meu pseudocódigo para combinar:

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 clasificación por fusión divide un problema en problemas máis pequenos e despois atopa os resultados dos problemas máis pequenos para obter o resultado do problema orixinal (nota: este tipo de algoritmo chámase dividir e vencer). Se non entendes este algoritmo, non te preocupes; Non o entendín a primeira vez que o vin. Se pode axudarche, vexo este algoritmo como un algoritmo de dúas fases:

Fase de división, onde a matriz se divide en matrices máis pequenas
A fase de clasificación é onde se combinan matrices pequenas (usando unión) para formar unha matriz máis grande.

Fase de división

Na fase de división, a matriz divídese en matrices unitarias en 3 pasos. O número formal de pasos é log(N) (xa que N=8, log(N) = 3).

Como sei isto?

Son xenio! Nunha palabra - matemáticas. A idea é que cada paso divide o tamaño da matriz orixinal en 2. O número de pasos é o número de veces que podes dividir a matriz orixinal en dous. Esta é a definición exacta dun logaritmo (base 2).

Fase de clasificación

Na fase de clasificación, comeza con matrices unitarias (de un só elemento). Durante cada paso aplicas varias operacións de combinación e o custo total é N = 8 operacións:

Na primeira etapa tes 4 fusións que custan 2 operacións cada unha
No segundo paso tes 2 fusións que custan 4 operacións cada unha
No terceiro paso tes 1 fusión que custa 8 operacións

Dado que hai pasos log(N), custo total N * operacións log(N)..

Vantaxes da ordenación por fusión

Por que este algoritmo é tan poderoso?

Porque:

Podes cambialo para reducir a pegada de memoria para que non crees novas matrices senón que modifiques directamente a matriz de entrada.

Nota: este tipo de algoritmo chámase in-lugar (clasificación sen memoria adicional).

Podes cambialo para usar espazo no disco e unha pequena cantidade de memoria ao mesmo tempo sen incorrer en sobrecarga de E/S do disco. A idea é cargar na memoria só aquelas partes que se están procesando actualmente. Isto é importante cando precisa ordenar unha táboa de varios gigabytes con só un búfer de memoria de 100 megabytes.

Nota: este tipo de algoritmo chámase clasificación externa.

Podes cambialo para executalo en varios procesos/fíos/servidores.

Por exemplo, a ordenación por fusión distribuída é un dos compoñentes clave Hadoop (que é unha estrutura en big data).

Este algoritmo pode converter o chumbo en ouro (de verdade!).

Este algoritmo de clasificación utilízase na maioría das bases de datos (se non en todas), pero non é o único. Se queres saber máis, podes ler isto traballo de investigación, que analiza os pros e os contras dos algoritmos comúns de clasificación de bases de datos.

Matriz, árbore e táboa hash

Agora que entendemos a idea da complexidade do tempo e da clasificación, debería falarvos de 3 estruturas de datos. Isto é importante porque eles son a base das bases de datos modernas. Tamén vou presentar o concepto índice de base de datos.

Array

Unha matriz bidimensional é a estrutura de datos máis sinxela. Unha táboa pódese pensar como unha matriz. Por exemplo:

Esta matriz bidimensional é unha táboa con filas e columnas:

Cada liña representa unha entidade
As columnas almacenan propiedades que describen a entidade.
Cada columna almacena datos dun tipo específico (número enteiro, cadea, data...).

Isto é conveniente para almacenar e visualizar datos, non obstante, cando necesitas atopar un valor específico, isto non é adecuado.

Por exemplo, se queres atopar todos os mozos que traballan no Reino Unido, terías que mirar cada fila para determinar se esa fila pertence ao Reino Unido. Custarache N transacciónsonde N - número de liñas, que non está mal, pero podería haber un xeito máis rápido? Agora toca que nos familiaricemos coas árbores.

Nota: a maioría das bases de datos modernas proporcionan matrices estendidas para almacenar táboas de forma eficiente: táboas organizadas por montón e táboas organizadas por índices. Pero isto non cambia o problema de atopar rapidamente unha condición específica nun grupo de columnas.

Árbore e índice da base de datos

Unha árbore de busca binaria é unha árbore binaria cunha propiedade especial, a clave en cada nodo debe ser:

maior que todas as claves almacenadas na subárbore esquerda
menos que todas as claves almacenadas na subárbore correcta

Vexamos que significa isto visualmente

Idea

Esta árbore ten N = 15 elementos. Digamos que estou buscando 208:

Comezo na raíz cuxa clave é 136. Desde 136<208, miro a subárbore dereita do nodo 136.
398>208 polo tanto, estou mirando a subárbore esquerda do nodo 398
250>208 polo tanto, estou mirando a subárbore esquerda do nodo 250
200<208, polo tanto estou mirando a subárbore correcta do nodo 200. Pero 200 non ten subárbore correcta, valor non existe (porque se existe, estará na subárbore dereita 200).

Agora digamos que estou buscando 40

Comezo pola raíz cuxa clave é 136. Xa que 136 > 40, miro a subárbore esquerda do nodo 136.
80 > 40, polo tanto estou mirando a subárbore esquerda do nodo 80
40 = 40, nodo existe. Recupero o ID da fila dentro do nodo (non se mostra na imaxe) e busco na táboa o ID da fila indicado.
Coñecer o ID da fila permíteme saber exactamente onde están os datos na táboa, para poder recuperalos ao instante.

Ao final, ambas as procuras custaránme o número de niveis dentro da árbore. Se le atentamente a parte sobre a ordenación por fusión, debería ver que hai niveis de rexistro(N). Resulta que, rexistro de custos de busca (N), non está mal!

Volvamos ao noso problema

Pero isto é moi abstracto, así que volvamos ao noso problema. En lugar dun simple enteiro, imaxina unha cadea que represente o país de alguén na táboa anterior. Digamos que tes unha árbore que contén o campo "país" (columna 3) da táboa:

Se queres saber quen traballa no Reino Unido
miras a árbore para obter o nodo que representa a Gran Bretaña
dentro de "UKnode" atoparás a localización dos rexistros dos traballadores do Reino Unido.

Esta busca custará operacións de rexistro(N) en lugar de N operacións se usa a matriz directamente. O que acabas de presentar foi índice de base de datos.

Podes construír unha árbore de índices para calquera grupo de campos (cadea, número, 2 liñas, número e cadea, data...) sempre que teñas unha función para comparar claves (é dicir, grupos de campos) para poder establecer orde entre as chaves (que é o caso de calquera tipo básico da base de datos).

B+TreeIndex

Aínda que esta árbore funciona ben para obter un valor específico, hai un GRAN problema cando o necesitas obter varios elementos entre dous valores. Isto custará O(N) porque terás que mirar cada nodo da árbore e comprobar se está entre estes dous valores (por exemplo, cun percorrido ordenado da árbore). Ademais, esta operación non é compatible con E/S do disco xa que tes que ler toda a árbore. Necesitamos atopar unha forma de executar de forma eficiente solicitude de rango. Para resolver este problema, as bases de datos modernas usan unha versión modificada da árbore anterior chamada B+Tree. Nunha árbore B+Tree:

só os nodos máis baixos (follas) almacenar información (localización das filas na táboa relacionada)
o resto dos nodos están aquí para enrutamento ao nodo correcto durante a busca.

Como podes ver, hai máis nodos aquí (dúas veces). De feito, tes nodos adicionais, "nodos de decisión", que che axudarán a atopar o nodo correcto (que almacena a localización das filas na táboa asociada). Pero a complexidade da busca segue sendo O(log(N)) (só hai un nivel máis). A gran diferenza é iso os nodos do nivel inferior están conectados cos seus sucesores.

Con este B+Tree, se buscas valores entre 40 e 100:

Só tes que buscar 40 (ou o valor máis próximo despois de 40 se 40 non existe) como fixeches coa árbore anterior.
A continuación, recolle 40 herdeiros usando ligazóns de herdeiros directos ata chegar aos 100.

Digamos que atopa M sucesores e que a árbore ten N nós. Atopar un nodo específico custa log(N) como a árbore anterior. Pero unha vez que obteñas este nodo, obterás sucesores M en operacións M con referencias aos seus sucesores. Esta busca só custa M+log(N) operacións comparadas con N operacións da árbore anterior. Ademais, non tes que ler a árbore completa (só M+log(N) nós), o que significa menos uso do disco. Se M é pequena (por exemplo, 200 filas) e N é grande (1 filas), haberá unha GRAN diferenza.

Pero hai novos problemas aquí (de novo!). Se engades ou eliminas unha fila na base de datos (e polo tanto no índice B+Tree asociado):

debes manter a orde entre os nós dentro dunha árbore B+, se non, non poderás atopar os nós dentro dunha árbore sen clasificar.
debes manter o número mínimo posible de niveis en B+Árbore, se non, a complexidade do tempo O(log(N)) pasa a ser O(N).

Noutras palabras, B+Tree debe ser autoordenado e equilibrado. Afortunadamente, isto é posible coas operacións intelixentes de eliminación e inserción. Pero isto ten un custo: as insercións e eliminacións nunha árbore B+ custan O(log(N)). É por iso que algúns de vós xa o escoitaron usar demasiados índices non é unha boa idea. De verdade, está a ralentizar a inserción/actualización/eliminación rápida dunha fila nunha táboaporque a base de datos necesita actualizar os índices da táboa usando unha costosa operación O(log(N)) para cada índice. Ademais, engadir índices significa máis carga de traballo para xestor de transaccións (describirase ao final do artigo).

Para máis detalles, podes ver o artigo da Wikipedia sobre B+Árbore. Se queres un exemplo de implementación de B+Tree nunha base de datos, bótalle un ollo Este artigo и Este artigo dun desenvolvedor líder de MySQL. Ambos céntranse en como InnoDB (o motor MySQL) manexa os índices.

Nota: un lector díxome que, debido ás optimizacións de baixo nivel, a árbore B+ debería estar completamente equilibrada.

Táboa de hash

A nosa última estrutura de datos importante é a táboa hash. Isto é moi útil cando queres buscar valores rapidamente. Ademais, comprender unha táboa hash axudaranos a comprender máis tarde unha operación común de unión de base de datos chamada hash join ( hash join). Esta estrutura de datos tamén é usada pola base de datos para almacenar algunhas cousas internas (p. ex. mesa de bloqueo ou piscina tampón, veremos estes dous conceptos máis adiante).

Unha táboa hash é unha estrutura de datos que atopa rapidamente un elemento pola súa chave. Para construír unha táboa hash, cómpre definir:

a clave para os teus elementos
función hash para chaves. Os hash de clave calculados dan a localización dos elementos (chamados segmentos ).
función para comparar claves. Unha vez que atopes o segmento correcto, debes atopar o elemento que buscas dentro do segmento mediante esta comparación.

Un exemplo sinxelo

Poñamos un exemplo claro:

Esta táboa hash ten 10 segmentos. Porque son preguiceiro, só retratei 5 segmentos, pero sei que es intelixente, así que deixarei que te imagines os outros 5 pola túa conta. Usei unha función hash módulo 10 da clave. Noutras palabras, almacene só o último díxitos da clave do elemento para atopar o seu segmento:

se o último díxito é 0, o elemento cae no segmento 0,
se o último díxito é 1, o elemento cae no segmento 1,
se o último díxito é 2, o elemento cae na área 2,
...

A función de comparación que usei é simplemente a igualdade entre dous números enteiros.

Digamos que quere obter o elemento 78:

A táboa hash calcula o código hash para 78, que é 8.
A táboa hash mira o segmento 8 e o primeiro elemento que atopa é 78.
Ela devolveche o artigo 78
A busca só custa 2 operacións (un para calcular o valor hash e outro para buscar o elemento dentro do segmento).

Agora digamos que quere obter o elemento 59:

A táboa hash calcula o código hash para 59, que é 9.
A táboa hash busca no segmento 9, o primeiro elemento atopado é 99. Dado que 99!=59, o elemento 99 non é un elemento válido.
Usando a mesma lóxica, tómanse o segundo elemento (9), o terceiro (79), ..., o último (29).
Non se atopou o elemento.
A busca custou 7 operacións.

Boa función hash

Como podes ver, dependendo do valor que busques, o custo non é o mesmo!

Se agora cambio a función hash módulo 1 da clave (é dicir, tomando os últimos 000 díxitos), a segunda busca só custa 000 operación xa que non hai elementos no segmento 6. O verdadeiro reto é atopar unha boa función hash que cree baldes que conteñan un número moi pequeno de elementos.

No meu exemplo, atopar unha boa función hash é doado. Pero este é un exemplo sinxelo, atopar unha boa función hash é máis difícil cando a clave é:

cadea (por exemplo, apelido)
2 liñas (por exemplo: apelidos e nome)
2 liñas e data (por exemplo: apelidos, nome e data de nacemento)
...

Cunha boa función hash, as consultas de táboas hash custan O(1).

Array vs táboa hash

Por que non usar unha matriz?

Hmm, boa pregunta.

A táboa hash pode ser parcialmente cargado na memoria, e os segmentos restantes poden permanecer no disco.
Cunha matriz debes usar espazo contiguo na memoria. Se estás cargando unha mesa grande é moi difícil atopar suficiente espazo continuo.
Para unha táboa hash, pode seleccionar a clave que quere (por exemplo, o país e o apelido da persoa).

Para obter máis información, podes ler o artigo sobre JavaHashMap, que é unha implementación eficiente dunha táboa hash; non precisa entender Java para comprender os conceptos tratados neste artigo.

Fonte: www.habr.com

Como funcionan as bases de datos relacionais (Parte 1)