Hola Habr! Presento a la vostra atenció la traducció de l'article
"Com funciona una base de dades relacional".

Quan es tracta de bases de dades relacionals, no puc evitar pensar que falta alguna cosa. S'utilitzen a tot arreu. Hi ha moltes bases de dades diferents disponibles, des de la petita i útil SQLite fins a la potent Teradata. Però només hi ha uns quants articles que expliquen com funciona la base de dades. Podeu cercar-vos per vosaltres mateixos utilitzant "com funciona la base de dades relacional" per veure els pocs resultats que hi ha. A més, aquests articles són breus. Si busqueu les últimes tecnologies de moda (BigData, NoSQL o JavaScript), trobareu articles més detallats que expliquen com funcionen.

Les bases de dades relacionals són massa antigues i massa avorrides per ser explicades fora de cursos universitaris, treballs de recerca i llibres?

Com a desenvolupador, odio fer servir alguna cosa que no entenc. I si les bases de dades s'utilitzen durant més de 40 anys, hi ha d'haver un motiu. Al llarg dels anys, he passat centenars d'hores per entendre realment aquestes estranyes caixes negres que faig servir cada dia. Bases de dades relacionals molt interessant perquè ells basat en conceptes útils i reutilitzables. Si us interessa entendre una base de dades, però mai no heu tingut el temps ni la ganes d'aprofundir en aquest ampli tema, hauríeu de gaudir d'aquest article.

Tot i que el títol d'aquest article és explícit, l'objectiu d'aquest article no és entendre com utilitzar la base de dades. Per tant ja hauríeu de saber com escriure una sol·licitud de connexió senzilla i consultes bàsiques RAW; en cas contrari és possible que no entengueu aquest article. Això és l'únic que has de saber, la resta t'explico.

Començaré amb alguns conceptes bàsics de la informàtica, com ara la complexitat temporal dels algorismes (BigO). Sé que alguns de vosaltres odien aquest concepte, però sense ell no podreu entendre les complexitats de la base de dades. Com que aquest és un gran tema, Em centraré el que crec que és important: com es processa la base de dades SQL sol·licitud. Només us presentaré conceptes bàsics de bases de dadesperquè al final de l'article tingueu una idea del que passa sota el capó.

Com que aquest és un article llarg i tècnic que inclou molts algorismes i estructures de dades, preneu-vos el temps per llegir-lo. Alguns conceptes poden ser difícils d'entendre; podeu saltar-los i encara teniu una idea general.

Per als més informats entre vosaltres, aquest article es divideix en 3 parts:

Visió general dels components de la base de dades de baix i alt nivell
Visió general del procés d'optimització de consultes
Visió general de la gestió de transaccions i agrupacions de buffer

Tornar als bàsics

Fa anys (en una galàxia molt, molt llunyana...), els desenvolupadors havien de saber exactament el nombre d'operacions que codificaven. Sabien els seus algorismes i estructures de dades de memòria perquè no es podien permetre el luxe de malgastar la CPU i la memòria dels seus ordinadors lents.

En aquesta part, us recordaré alguns d'aquests conceptes ja que són essencials per entendre la base de dades. També introduiré el concepte índex de base de dades.

O(1) vs O(n2)

Avui en dia, molts desenvolupadors no els importa la complexitat temporal dels algorismes... i tenen raó!

Però quan esteu tractant amb moltes dades (no parlo de milers) o si teniu problemes en mil·lisegons, és fonamental entendre aquest concepte. I com us podeu imaginar, les bases de dades han de fer front a les dues situacions! No us faré passar més temps del necessari per entendre el punt. Això ens ajudarà a entendre més endavant el concepte d'optimització basada en costos (cost basat optimització).

Concepte

Complexitat temporal de l'algorisme s'utilitza per veure quant de temps trigarà a completar-se un algorisme per a una quantitat determinada de dades. Per descriure aquesta complexitat, utilitzem la notació matemàtica gran O. Aquesta notació s'utilitza amb una funció que descriu quantes operacions necessita un algorisme per a un nombre determinat d'entrades.

Per exemple, quan dic "aquest algorisme té complexitat O(some_function())", vol dir que l'algoritme requereix operacions some_function(a_certain_amount_of_data) per processar una certa quantitat de dades.

En aquest cas, No és la quantitat de dades el que importa**, d'una altra manera ** com augmenta el nombre d'operacions amb l'augment del volum de dades. La complexitat temporal no proporciona un nombre exacte d'operacions, però és una bona manera d'estimar el temps d'execució.

En aquest gràfic podeu veure el nombre d'operacions en comparació amb la quantitat de dades d'entrada per a diferents tipus de complexitats temporals d'algorisme. Vaig utilitzar una escala logarítmica per mostrar-los. En altres paraules, la quantitat de dades augmenta ràpidament d'1 a 1 mil milions. Podem veure que:

O(1) o complexitat constant es manté constant (en cas contrari no s'anomenaria complexitat constant).
O(log(n)) segueix sent baix fins i tot amb milers de milions de dades.
La pitjor dificultat - O(n2), on el nombre d'operacions creix ràpidament.
Les altres dues complicacions augmenten amb la mateixa rapidesa.

Примеры

Amb una petita quantitat de dades, la diferència entre O(1) i O(n2) és insignificant. Per exemple, suposem que teniu un algorisme que necessita processar 2000 elements.

L'algorisme O(1) us costarà 1 operació
L'algorisme O(log(n)) us costarà 7 operacions
L'algorisme O(n) us costarà 2 operacions
L'algorisme O(n*log(n)) us costarà 14 operacions
L'algorisme O(n2) us costarà 4 d'operacions

La diferència entre O(1) i O(n2) sembla gran (4 milions d'operacions) però perdràs un màxim de 2 ms, just el temps de parpellejar els ulls. De fet, els processadors moderns poden processar centenars de milions d'operacions per segon. És per això que el rendiment i l'optimització no són un problema en molts projectes informàtics.

Com he dit, encara és important conèixer aquest concepte quan es treballa amb grans quantitats de dades. Si aquesta vegada l'algoritme ha de processar 1 d'elements (que no és tant per a una base de dades):

L'algorisme O(1) us costarà 1 operació
L'algorisme O(log(n)) us costarà 14 operacions
L'algorisme O(n) us costarà 1 d'operacions
L'algorisme O(n*log(n)) us costarà 14 d'operacions
L'algorisme O(n2) us costarà 1 d'operacions

No he fet les matemàtiques, però diria que amb l'algoritme O(n2) tens temps per prendre un cafè (fins i tot dos!). Si afegiu un altre 0 al volum de dades, tindreu temps per fer una migdiada.

Anem més a fons

Per a la seva informació:

Una bona cerca de taula hash troba un element a O(1).
Cercar un arbre ben equilibrat produeix resultats en O(log(n)).
La cerca a través d'una matriu produeix resultats en O(n).
Els millors algorismes d'ordenació tenen complexitat O(n*log(n)).
Un algorisme d'ordenació dolent té complexitat O(n2).

Nota: a les parts següents veurem aquests algorismes i estructures de dades.

Hi ha diversos tipus de complexitat temporal de l'algorisme:

escenari mitjà
el millor dels casos
i el pitjor dels casos

La complexitat temporal és sovint el pitjor dels casos.

Només estava parlant de la complexitat temporal de l'algorisme, però la complexitat també s'aplica a:

consum de memòria de l'algorisme
algorisme de consum d'E/S de disc

Per descomptat, hi ha complicacions pitjors que n2, per exemple:

n4: això és terrible! Alguns dels algorismes esmentats tenen aquesta complexitat.
3n: això és encara pitjor! Un dels algorismes que veurem a la meitat d'aquest article té aquesta complexitat (i en realitat s'utilitza en moltes bases de dades).
factorial n: mai obtindreu els vostres resultats fins i tot amb una petita quantitat de dades.
nn: Si trobeu aquesta complexitat, hauríeu de preguntar-vos si aquest és realment el vostre camp d'activitat...

Nota: no us vaig donar la definició real de la designació O gran, només una idea. Podeu llegir aquest article a Wikipedia per a la definició real (asimptòtica).

MergeSort

Què fas quan necessites ordenar una col·lecció? Què? Truqueu a la funció sort()... D'acord, bona resposta... Però per a una base de dades, heu d'entendre com funciona aquesta funció sort().

Hi ha diversos bons algorismes d'ordenació, així que em centraré en el més important: combinar ordenar. És possible que no entengueu per què l'ordenació de dades és útil ara mateix, però ho haureu de fer després de la part d'optimització de consultes. A més, entendre l'ordenació de combinació ens ajudarà a entendre més tard l'operació comuna d'unió a la base de dades anomenada unir unir-se (associació de fusió).

Fusionar

Com molts algorismes útils, l'ordenació per fusió es basa en un truc: combinar 2 matrius ordenades de mida N/2 en una matriu ordenada d'elements només costa N operacions. Aquesta operació s'anomena fusió.

Vegem què significa això amb un exemple senzill:

Aquesta figura mostra que per construir la matriu de 8 elements ordenada final, només cal que itereu una vegada sobre les 2 matrius de 4 elements. Com que les dues matrius de 4 elements ja estan ordenades:

1) compareu els dos elements actuals en dues matrius (al principi actual = primer)
2) a continuació, agafeu el més petit per posar-lo en una matriu de 8 elements
3) i aneu al següent element de la matriu on heu pres l'element més petit
i repetiu 1,2,3 fins arribar a l'últim element d'una de les matrius.
A continuació, agafeu els elements restants de l'altra matriu per posar-los en una matriu de 8 elements.

Això funciona perquè les dues matrius de 4 elements estan ordenades i, per tant, no heu de "tornar" en aquestes matrius.

Ara que entenem el truc, aquí teniu el meu pseudocodi per 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;

L'ordenació combinada divideix un problema en problemes més petits i després troba els resultats dels problemes més petits per obtenir el resultat del problema original (nota: aquest tipus d'algorisme s'anomena dividir i vèncer). Si no enteneu aquest algorisme, no us preocupeu; No ho vaig entendre la primera vegada que el vaig veure. Si us pot ajudar, veig aquest algorisme com un algorisme de dues fases:

Fase de divisió, on la matriu es divideix en matrius més petites
La fase d'ordenació és on es combinen matrius petites (mitjançant unió) per formar una matriu més gran.

Fase de divisió

En l'etapa de divisió, la matriu es divideix en matrius unitàries en 3 passos. El nombre formal de passos és log(N) (ja que N=8, log(N) = 3).

Com ho sé?

Sóc un geni! En una paraula: matemàtiques. La idea és que cada pas divideix la mida de la matriu original per 2. El nombre de passos és el nombre de vegades que podeu dividir la matriu original en dos. Aquesta és la definició exacta d'un logaritme (base 2).

Fase de classificació

En la fase d'ordenació, comenceu amb matrius unitàries (d'un sol element). Durant cada pas apliqueu diverses operacions de fusió i el cost total és N = 8 operacions:

A la primera etapa teniu 4 fusions que costen 2 operacions cadascuna
En el segon pas teniu 2 fusions que costen 4 operacions cadascuna
En el tercer pas teniu 1 fusió que costa 8 operacions

Com que hi ha passos log(N), cost total N * operacions log(N)..

Avantatges de l'ordenació combinada

Per què aquest algorisme és tan potent?

Perquè:

Podeu canviar-lo per reduir l'empremta de memòria de manera que no creeu matrius noves sinó que modifiqueu directament la matriu d'entrada.

Nota: aquest tipus d'algorisme s'anomena in-lloc (ordenació sense memòria addicional).

Podeu canviar-lo per utilitzar espai de disc i una petita quantitat de memòria al mateix temps sense incórrer en una sobrecàrrega important d'E/S de disc. La idea és carregar a la memòria només aquelles parts que s'estan processant actualment. Això és important quan necessiteu ordenar una taula de diversos gigabytes amb només un buffer de memòria de 100 megabytes.

Nota: aquest tipus d'algorisme s'anomena tipus extern.

Podeu canviar-lo perquè s'executi en diversos processos/fils/servidors.

Per exemple, l'ordenació de combinació distribuïda és un dels components clau Hadoop (que és una estructura en big data).

Aquest algorisme pot convertir el plom en or (de veritat!).

Aquest algorisme d'ordenació s'utilitza a la majoria (si no a totes) les bases de dades, però no és l'única. Si voleu saber-ne més, podeu llegir això treball de recerca, que analitza els avantatges i els contres dels algorismes comuns d'ordenació de bases de dades.

Taula de matriu, arbre i hash

Ara que entenem la idea de la complexitat i l'ordenació del temps, us hauria de parlar de 3 estructures de dades. Això és important perquè ells són la base de les bases de dades modernes. També introduiré el concepte índex de base de dades.

Array

Una matriu bidimensional és l'estructura de dades més senzilla. Una taula es pot pensar com una matriu. Per exemple:

Aquesta matriu bidimensional és una taula amb files i columnes:

Cada línia representa una entitat
Les columnes emmagatzemen propietats que descriuen l'entitat.
Cada columna emmagatzema dades d'un tipus específic (número enter, cadena, data...).

Això és convenient per emmagatzemar i visualitzar dades, però, quan necessiteu trobar un valor específic, no és adequat.

Per exemple, si voleu trobar tots els nois que treballen al Regne Unit, hauríeu de mirar cada fila per determinar si aquesta fila pertany al Regne Unit. Us costarà N transaccionsOn N - nombre de línies, que no està malament, però podria haver-hi una manera més ràpida? Ara ens toca conèixer els arbres.

Nota: la majoria de bases de dades modernes ofereixen matrius esteses per emmagatzemar taules de manera eficient: taules organitzades per munt i taules organitzades per índexs. Però això no canvia el problema de trobar ràpidament una condició específica en un grup de columnes.

Arbre i índex de bases de dades

Un arbre de cerca binari és un arbre binari amb una propietat especial, la clau de cada node ha de ser:

més gran que totes les claus emmagatzemades al subarbre esquerre
menys que totes les claus emmagatzemades al subarbre dret

Vegem què significa això visualment

Idea

Aquest arbre té N = 15 elements. Diguem que estic buscant 208:

Començo per l'arrel la clau de la qual és 136. Des de 136<208, miro el subarbre dret del node 136.
398>208, per tant, estic mirant el subarbre esquerre del node 398
250>208, per tant, estic mirant el subarbre esquerre del node 250
200<208, per tant estic mirant el subarbre correcte del node 200. Però 200 no té cap subarbre correcte, el valor no existeix (perquè si existeix, estarà al subarbre dret 200).

Ara diguem que en busco 40

Començo per l'arrel la clau de la qual és 136. Com que 136 > 40, miro el subarbre esquerre del node 136.
80 > 40, per tant estic mirant el subarbre esquerre del node 80
40= 40, el node existeix. Recupero l'ID de fila dins del node (no es mostra a la imatge) i busco a la taula l'ID de fila donat.
Conèixer l'identificador de fila em permet saber exactament on es troben les dades a la taula, de manera que les puc recuperar a l'instant.

Al final, ambdues cerques em costaran el nombre de nivells dins de l'arbre. Si llegiu atentament la part sobre l'ordenació de combinacions, hauríeu de veure que hi ha nivells de registre(N). Resulta, registre de costos de cerca (N), no està malament!

Tornem al nostre problema

Però això és molt abstracte, així que tornem al nostre problema. En lloc d'un simple enter, imagineu una cadena que representi el país d'algú a la taula anterior. Suposem que teniu un arbre que conté el camp "país" (columna 3) de la taula:

Si voleu saber qui treballa al Regne Unit
mires l'arbre per obtenir el node que representa Gran Bretanya
a "UKnode" trobareu la ubicació dels registres dels treballadors del Regne Unit.

Aquesta cerca costarà operacions de log(N) en lloc de N operacions si feu servir la matriu directament. El que acabes de presentar va ser índex de base de dades.

Podeu crear un arbre d'índex per a qualsevol grup de camps (cadena, nombre, 2 línies, nombre i cadena, data...) sempre que tingueu una funció per comparar claus (és a dir, grups de camps) per poder configurar ordre entre les claus (que és el cas de qualsevol tipus bàsic de la base de dades).

B+TreeIndex

Tot i que aquest arbre funciona bé per obtenir un valor específic, hi ha un GRAN problema quan ho necessiteu obtenir diversos elements entre dos valors. Això costarà O(N) perquè haureu de mirar cada node de l'arbre i comprovar si es troba entre aquests dos valors (per exemple, amb un recorregut ordenat de l'arbre). A més, aquesta operació no és compatible amb E/S de disc, ja que heu de llegir tot l'arbre. Hem de trobar una manera d'executar-lo de manera eficient sol·licitud d'interval. Per resoldre aquest problema, les bases de dades modernes utilitzen una versió modificada de l'arbre anterior anomenada B+Tree. En un arbre B+Tree:

només els nodes més baixos (fulles) emmagatzemar informació (ubicació de les files a la taula relacionada)
la resta de nodes són aquí per a l'encaminament al node correcte durant la recerca.

Com podeu veure, aquí hi ha més nodes (dues vegades). De fet, teniu nodes addicionals, "nodes de decisió", que us ajudaran a trobar el node correcte (que emmagatzema la ubicació de les files a la taula associada). Però la complexitat de la cerca segueix sent O(log(N)) (només hi ha un nivell més). La gran diferència és que els nodes del nivell inferior estan connectats amb els seus successors.

Amb aquest B+Tree, si busqueu valors entre 40 i 100:

Només cal que cerqueu 40 (o el valor més proper després de 40 si 40 no existeix) com vau fer amb l'arbre anterior.
A continuació, recolliu 40 hereus mitjançant enllaços directes d'hereu fins arribar als 100.

Suposem que trobeu M successors i que l'arbre té N nodes. Trobar un node específic costa log(N) com l'arbre anterior. Però un cop obtingueu aquest node, obtindreu successors M en operacions M amb referències als seus successors. Aquesta cerca només costa M+log(N) operacions comparades amb N operacions de l'arbre anterior. A més, no cal que llegiu l'arbre complet (només M+log(N) nodes), la qual cosa significa menys ús del disc. Si M és petita (per exemple, 200 files) i N és gran (1 files), hi haurà una GRAN diferència.

Però hi ha nous problemes aquí (de nou!). Si afegiu o suprimiu una fila a la base de dades (i per tant a l'índex B+Tree associat):

heu de mantenir l'ordre entre els nodes dins d'un arbre B+, en cas contrari no podreu trobar els nodes dins d'un arbre sense ordenar.
heu de mantenir el nombre mínim possible de nivells a B+Arbre, en cas contrari, la complexitat del temps O(log(N)) es converteix en O(N).

En altres paraules, B+Tree ha de ser autoordenat i equilibrat. Afortunadament, això és possible amb operacions d'inserció i supressió intel·ligents. Però això té un cost: les insercions i les supressions en un arbre B+ costen O(log(N)). Per això alguns de vosaltres ho heu sentit utilitzar massa índexs no és una bona idea. Realment, esteu alentint la inserció/actualització/eliminació ràpida d'una fila d'una taulaperquè la base de dades necessita actualitzar els índexs de la taula mitjançant una costosa operació O(log(N)) per a cada índex. A més, afegir índexs significa més càrrega de treball gestor de transaccions (es descriurà al final de l'article).

Per a més detalls, podeu veure l'article de la Viquipèdia B+Arbre. Si voleu un exemple d'implementació de B+Tree en una base de dades, feu una ullada aquest article и aquest article d'un desenvolupador líder de MySQL. Tots dos se centren en com InnoDB (el motor MySQL) gestiona els índexs.

Nota: un lector em va dir que, a causa d'optimitzacions de baix nivell, l'arbre B+ hauria d'estar completament equilibrat.

Taula hash

La nostra darrera estructura de dades important és la taula hash. Això és molt útil quan voleu cercar valors ràpidament. A més, entendre una taula hash ens ajudarà a entendre més tard una operació comuna d'unió de base de dades anomenada hash join ( hash join). Aquesta estructura de dades també és utilitzada per la base de dades per emmagatzemar algunes coses internes (p. taula de bloqueig o piscina tampó, veurem aquests dos conceptes més endavant).

Una taula hash és una estructura de dades que troba ràpidament un element per la seva clau. Per crear una taula hash cal definir:

ключ pels teus elements
funció hash per les claus. Els hashes de clau calculats donen la ubicació dels elements (anomenats segments ).
funció de comparació de claus. Un cop hàgiu trobat el segment correcte, heu de trobar l'element que busqueu dins del segment mitjançant aquesta comparació.

Exemple senzill

Prenguem un exemple clar:

Aquesta taula hash té 10 segments. Com que sóc mandrós, només m'he imaginat 5 segments, però sé que ets intel·ligent, així que et deixaré imaginar els altres 5 pel teu compte. Vaig utilitzar una funció hash mòdul 10 de la clau. En altres paraules, emmagatzeme només l'últim dígit de la clau de l'element per trobar el seu segment:

si l'últim dígit és 0, l'element cau en el segment 0,
si l'últim dígit és 1, l'element cau en el segment 1,
si l'últim dígit és 2, l'element cau a l'àrea 2,
...

La funció de comparació que vaig utilitzar és simplement la igualtat entre dos nombres enters.

Suposem que voleu obtenir l'element 78:

La taula hash calcula el codi hash per a 78, que és 8.
La taula hash mira el segment 8 i el primer element que troba és el 78.
Ella us retorna l'article 78
La cerca només costa 2 operacions (un per calcular el valor hash i l'altre per buscar l'element dins del segment).

Ara suposem que voleu obtenir l'element 59:

La taula hash calcula el codi hash per a 59, que és 9.
La taula hash cerca al segment 9, el primer element trobat és 99. Com que 99!=59, l'element 99 no és un element vàlid.
Amb la mateixa lògica, es prenen el segon element (9), el tercer (79), ..., l'últim (29).
Element no trobat.
La cerca va costar 7 operacions.

Bona funció hash

Com podeu veure, segons el valor que busqueu, el cost no és el mateix!

Si ara canvio la funció hash mòdul 1 de la clau (és a dir, agafant els darrers 000 dígits), la segona cerca només costa 000 operació ja que no hi ha elements al segment 6. El veritable repte és trobar una bona funció hash que creï cubs que continguin un nombre molt reduït d'elements.

En el meu exemple, trobar una bona funció hash és fàcil. Però aquest és un exemple senzill, trobar una bona funció hash és més difícil quan la clau és:

cadena (per exemple, cognom)
2 línies (per exemple: cognom i nom)
2 línies i data (per exemple: cognom, nom i data de naixement)
...

Amb una bona funció hash, les cerques de taules hash costen O(1).

Taula matriu vs hash

Per què no utilitzar una matriu?

Hmm, bona pregunta.

La taula hash pot ser carregat parcialment a la memòria, i els segments restants poden romandre al disc.
Amb una matriu, heu d'utilitzar espai contigu a la memòria. Si esteu carregant una taula gran és molt difícil trobar prou espai continu.
Per a una taula hash, podeu seleccionar la clau que vulgueu (per exemple, el país i el cognom de la persona).

Per a més informació, podeu llegir l'article sobre JavaHashMap, que és una implementació eficient d'una taula hash; no cal entendre Java per entendre els conceptes tractats en aquest article.

Font: www.habr.com

Com funcionen les bases de dades relacionals (part 1)