Ehi Habr! Presento alla vostra attenzione la traduzione dell'articolo
"Come funziona un database relazionale".

Quando si parla di database relazionali non posso fare a meno di pensare che manchi qualcosa. Sono usati ovunque. Sono disponibili molti database diversi, dal piccolo e utile SQLite al potente Teradata. Ma ci sono solo pochi articoli che spiegano come funziona il database. Puoi cercare tu stesso utilizzando "howdoesarelationaldatabasework" per vedere quanti pochi risultati ci sono. Inoltre, questi articoli sono brevi. Se stai cercando le ultime tecnologie interessanti (BigData, NoSQL o JavaScript), troverai articoli più approfonditi che spiegano come funzionano.

I database relazionali sono troppo vecchi e noiosi per essere spiegati al di fuori dei corsi universitari, degli articoli di ricerca e dei libri?

Come sviluppatore, odio usare qualcosa che non capisco. E se i database vengono utilizzati da più di 40 anni un motivo ci sarà. Nel corso degli anni, ho trascorso centinaia di ore per comprendere veramente queste strane scatole nere che utilizzo ogni giorno. Database relazionali molto interessante perché loro basato su concetti utili e riutilizzabili. Se sei interessato a comprendere un database, ma non hai mai avuto il tempo o la voglia di approfondire questo ampio argomento, dovresti goderti questo articolo.

Sebbene il titolo di questo articolo sia esplicito, lo scopo di questo articolo non è capire come utilizzare il database. di conseguenza, dovresti già sapere come scrivere una semplice richiesta di connessione e query di base CRUDELE; altrimenti potresti non capire questo articolo. Questa è l'unica cosa che devi sapere, il resto ti spiego io.

Inizierò con alcune nozioni di base dell'informatica, come la complessità temporale degli algoritmi (BigO). So che alcuni di voi odiano questo concetto, ma senza di esso non sarete in grado di comprendere le complessità all'interno del database. Poiché questo è un argomento enorme, Mi concentrerò su quello che penso sia importante: come viene elaborato il database SQL inchiesta. Mi limiterò a presentarlo concetti base delle basi di datiin modo che alla fine dell'articolo tu abbia un'idea di cosa sta succedendo sotto il cofano.

Poiché si tratta di un articolo lungo e tecnico che coinvolge molti algoritmi e strutture dati, prenditi il tempo necessario per leggerlo. Alcuni concetti potrebbero essere difficili da comprendere; puoi saltarli e avere comunque un'idea generale.

Per i più informati tra voi, questo articolo è diviso in 3 parti:

Panoramica dei componenti del database di basso e alto livello
Panoramica del processo di ottimizzazione delle query
Panoramica della gestione delle transazioni e del pool di buffer

Ritorno alle basi

Anni fa (in una galassia lontana lontana...), gli sviluppatori dovevano sapere esattamente il numero di operazioni che stavano codificando. Conoscevano a memoria i loro algoritmi e le strutture dati perché non potevano permettersi di sprecare la CPU e la memoria dei loro computer lenti.

In questa parte ti ricorderò alcuni di questi concetti poiché sono essenziali per comprendere il database. Introdurrò anche il concetto indice della banca dati.

O(1) vs O(n2)

Al giorno d'oggi, molti sviluppatori non si preoccupano della complessità temporale degli algoritmi... e hanno ragione!

Ma quando hai a che fare con molti dati (non sto parlando di migliaia) o se lavori in pochi millisecondi, diventa fondamentale comprendere questo concetto. E come puoi immaginare, i database devono affrontare entrambe le situazioni! Non ti farò spendere più tempo del necessario per far capire il punto. Questo ci aiuterà a comprendere in seguito il concetto di ottimizzazione basata sui costi (costo basato ottimizzazione).

Concetto

Complessità temporale dell'algoritmo utilizzato per vedere quanto tempo impiegherà un algoritmo per essere completato per una determinata quantità di dati. Per descrivere questa complessità, utilizziamo la notazione matematica Big O. Questa notazione viene utilizzata con una funzione che descrive quante operazioni richiede un algoritmo per un dato numero di input.

Ad esempio, quando dico "questo algoritmo ha complessità O(qualche_funzione())", significa che l'algoritmo richiede alcune_funzioni(a_certain_amount_of_data) operazioni per elaborare una certa quantità di dati.

In questo caso, Non è la quantità di dati che conta**, Altrimenti ** come aumenta il numero di operazioni all'aumentare del volume di dati. La complessità temporale non fornisce un numero esatto di operazioni, ma è un buon modo per stimare il tempo di esecuzione.

In questo grafico puoi vedere il numero di operazioni rispetto alla quantità di dati di input per diversi tipi di complessità temporale dell'algoritmo. Per visualizzarli ho utilizzato una scala logaritmica. In altre parole, la quantità di dati aumenta rapidamente da 1 a 1 miliardo e possiamo vedere che:

O(1) o complessità costante rimane costante (altrimenti non sarebbe chiamata complessità costante).
O(ceppo(n)) rimane basso anche con miliardi di dati.
Peggiore difficoltà - O(n2), dove il numero di operazioni cresce rapidamente.
Le altre due complicazioni aumentano altrettanto rapidamente.

Примеры

Con una piccola quantità di dati, la differenza tra O(1) e O(n2) è trascurabile. Ad esempio, supponiamo che tu abbia un algoritmo che deve elaborare 2000 elementi.

L'algoritmo O(1) ti costerà 1 operazione
L'algoritmo O(log(n)) ti costerà 7 operazioni
L'algoritmo O(n) ti costerà 2 operazioni
L'algoritmo O(n*log(n)) ti costerà 14 operazioni
L'algoritmo O(n2) ti costerà 4 di operazioni

La differenza tra O(1) e O(n2) sembra grande (4 milioni di operazioni) ma perderai un massimo di 2 ms, giusto il tempo di battere le palpebre. In effetti, i processori moderni possono elaborare centinaia di milioni di operazioni al secondo. Questo è il motivo per cui prestazioni e ottimizzazione non sono un problema in molti progetti IT.

Come ho detto, è comunque importante conoscere questo concetto quando si lavora con enormi quantità di dati. Se questa volta l'algoritmo deve elaborare 1 di elementi (che non è tanti per un database):

L'algoritmo O(1) ti costerà 1 operazione
L'algoritmo O(log(n)) ti costerà 14 operazioni
L'algoritmo O(n) ti costerà 1 di operazioni
L'algoritmo O(n*log(n)) ti costerà 14 di operazioni
L'algoritmo O(n2) ti costerà 1 di operazioni

Non ho fatto i conti, ma direi che con l'algoritmo O(n2) hai il tempo di bere un caffè (anche due!). Se aggiungi un altro 0 al volume dei dati, avrai tempo per fare un pisolino.

Andiamo più in profondità

Per il vostro riferimento:

Una buona ricerca nella tabella hash trova un elemento in O(1).
La ricerca di un albero ben bilanciato produce risultati in O(log(n)).
La ricerca in un array produce risultati in O(n).
I migliori algoritmi di ordinamento hanno complessità O(n*log(n)).
Un algoritmo di ordinamento errato ha complessità O(n2).

Nota: nelle parti seguenti vedremo questi algoritmi e strutture dati.

Esistono diversi tipi di complessità temporale dell'algoritmo:

scenario medio
scenario migliore
e lo scenario peggiore

La complessità temporale è spesso lo scenario peggiore.

Stavo parlando solo della complessità temporale dell'algoritmo, ma la complessità si applica anche a:

consumo di memoria dell'algoritmo
algoritmo di consumo I/O del disco

Naturalmente, ci sono complicazioni peggiori di n2, ad esempio:

n4: questo è terribile! Alcuni degli algoritmi citati hanno questa complessità.
3n: questo è anche peggio! Uno degli algoritmi che vedremo nel mezzo di questo articolo ha questa complessità (ed è effettivamente utilizzato in molti database).
fattoriale n: non otterrai mai risultati anche con una piccola quantità di dati.
nn: Se ti imbatti in questa complessità dovresti chiederti se questo è davvero il tuo campo di attività...

Nota: non ti ho dato la definizione effettiva della designazione della grande O, solo un'idea. Puoi leggere questo articolo su Wikipedia per la definizione reale (asintotica).

UnisciOrdina

Cosa fai quando devi ordinare una collezione? Che cosa? Chiami la funzione sort()... Ok, buona risposta... Ma per un database, devi capire come funziona questa funzione sort().

Esistono diversi buoni algoritmi di ordinamento, quindi mi concentrerò sui più importanti: unisci ordinamento. Potresti non capire perché l'ordinamento dei dati è utile in questo momento, ma dovresti capirlo dopo la parte di ottimizzazione delle query. Inoltre, comprendere il merge sort ci aiuterà in seguito a comprendere l'operazione comune di unione al database chiamata unire join (associazione di fusione).

Unisci

Come molti algoritmi utili, il merge sort si basa su un trucco: combinare 2 array ordinati di dimensione N/2 in un array ordinato con N elementi costa solo N operazioni. Questa operazione si chiama fusione.

Vediamo cosa significa con un semplice esempio:

Questa figura mostra che per costruire l'array finale ordinato di 8 elementi, è necessario eseguire solo un'iterazione sui 2 array di 4 elementi. Poiché entrambi gli array da 4 elementi sono già ordinati:

1) confronti entrambi gli elementi correnti in due array (all'inizio corrente = primo)
2) quindi prendi quello più piccolo per inserirlo in un array di 8 elementi
3) e passa all'elemento successivo nell'array in cui hai preso l'elemento più piccolo
e ripeti 1,2,3 finché non raggiungi l'ultimo elemento di uno degli array.
Quindi prendi gli elementi rimanenti dell'altro array per inserirli in un array di 8 elementi.

Funziona perché entrambi gli array di 4 elementi sono ordinati e quindi non è necessario "tornare indietro" in quegli array.

Ora che abbiamo capito il trucco, ecco il mio pseudocodice per l'unione:

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'ordinamento per unione suddivide un problema in problemi più piccoli e quindi trova i risultati dei problemi più piccoli per ottenere il risultato del problema originale (nota: questo tipo di algoritmo è chiamato divide et impera). Se non capisci questo algoritmo, non preoccuparti; Non l'ho capito la prima volta che l'ho visto. Se può aiutarti, vedo questo algoritmo come un algoritmo a due fasi:

Fase di divisione, in cui l'array viene diviso in array più piccoli
La fase di ordinamento è quella in cui piccoli array vengono combinati (usando l'unione) per formare un array più grande.

Fase di divisione

Nella fase di divisione, l'array viene suddiviso in array unitari in 3 passaggi. Il numero formale di passaggi è log(N) (poiché N=8, log(N) = 3).

Come faccio a saperlo?

Sono un genio! In una parola: matematica. L'idea è che ogni passaggio divida la dimensione dell'array originale per 2. Il numero di passaggi è il numero di volte in cui puoi dividere l'array originale in due. Questa è la definizione esatta di logaritmo (base 2).

Fase di cernita

Nella fase di ordinamento, si inizia con array unitari (a elemento singolo). Durante ogni passaggio applichi più operazioni di unione e il costo totale è N = 8 operazioni:

Nella prima fase hai 4 fusioni che costano 2 operazioni ciascuna
Nel secondo passaggio hai 2 fusioni che costano 4 operazioni ciascuna
Nel terzo passaggio hai 1 fusione che costa 8 operazioni

Poiché ci sono log(N) passi, costo totale n * operazioni log(N)..

Vantaggi del merge sort

Perché questo algoritmo è così potente?

perché:

Puoi modificarlo per ridurre l'impronta di memoria in modo da non creare nuovi array ma modificare direttamente l'array di input.

Nota: questo tipo di algoritmo si chiama in-posto (ordinamento senza memoria aggiuntiva).

È possibile modificarlo per utilizzare contemporaneamente lo spazio su disco e una piccola quantità di memoria senza incorrere in un sovraccarico significativo di I/O del disco. L'idea è di caricare in memoria solo le parti attualmente in fase di elaborazione. Ciò è importante quando è necessario ordinare una tabella multi-gigabyte con solo un buffer di memoria da 100 megabyte.

Nota: questo tipo di algoritmo si chiama ordinamento esterno.

È possibile modificarlo per l'esecuzione su più processi/thread/server.

Ad esempio, il merge sort distribuito è uno dei componenti chiave Hadoop (che è una struttura in big data).

Questo algoritmo può trasformare il piombo in oro (davvero!).

Questo algoritmo di ordinamento viene utilizzato nella maggior parte dei database (se non in tutti), ma non è l'unico. Se vuoi saperne di più, puoi leggere questo lavoro di ricerca, che discute i pro e i contro dei comuni algoritmi di ordinamento dei database.

Array, albero e tabella hash

Ora che abbiamo compreso il concetto di complessità e ordinamento temporale, dovrei parlarvi di 3 strutture dati. Questo è importante perché loro sono la base dei moderni database. Introdurrò anche il concetto indice della banca dati.

schieramento

Un array bidimensionale è la struttura dati più semplice. Una tabella può essere pensata come un array. Per esempio:

Questo array bidimensionale è una tabella con righe e colonne:

Ogni riga rappresenta un'entità
Le colonne memorizzano le proprietà che descrivono l'entità.
Ogni colonna memorizza dati di un tipo specifico (intero, stringa, data...).

Ciò è utile per memorizzare e visualizzare i dati, tuttavia, quando è necessario trovare un valore specifico, non è adatto.

Ad esempio, se volessi trovare tutti i ragazzi che lavorano nel Regno Unito, dovresti esaminare ciascuna riga per determinare se appartiene al Regno Unito. Ti costerà N transazioniDove N - numero di righe, il che non è male, ma potrebbe esserci un modo più veloce? Ora è il momento di fare conoscenza con gli alberi.

Nota: la maggior parte dei database moderni fornisce array estesi per archiviare le tabelle in modo efficiente: tabelle organizzate nell'heap e tabelle organizzate nell'indice. Ma ciò non cambia il problema di trovare rapidamente una condizione specifica in un gruppo di colonne.

Albero e indice del database

Un albero di ricerca binario è un albero binario con una proprietà speciale, la chiave in ciascun nodo deve essere:

maggiore di tutte le chiavi memorizzate nel sottoalbero di sinistra
meno di tutte le chiavi memorizzate nel sottoalbero destro

Vediamo cosa significa visivamente

Idea

Questo albero ha N = 15 elementi. Diciamo che sto cercando 208:

Inizio dalla radice la cui chiave è 136. Poiché 136<208, guardo il sottoalbero destro del nodo 136.
398>208 quindi sto guardando il sottoalbero sinistro del nodo 398
250>208 quindi sto guardando il sottoalbero sinistro del nodo 250
200<208, quindi sto guardando il sottoalbero destro del nodo 200. Ma 200 non ha un sottoalbero destro, il valore non esiste (perché se esiste, sarà nel sottoalbero destro 200).

Ora diciamo che ne sto cercando 40

Inizio dalla radice la cui chiave è 136. Poiché 136 > 40, guardo il sottoalbero sinistro del nodo 136.
80 > 40, quindi sto guardando il sottoalbero sinistro del nodo 80
40= 40, nodo esiste. Recupero l'ID della riga all'interno del nodo (non mostrato nell'immagine) e cerco nella tabella l'ID della riga specificato.
Conoscere l'ID della riga mi consente di sapere esattamente dove si trovano i dati nella tabella, in modo da poterli recuperare immediatamente.

Alla fine, entrambe le ricerche mi costeranno il numero di livelli all'interno dell'albero. Se leggi attentamente la parte relativa al merge sort, dovresti vedere che ci sono livelli di log (N). Si scopre, registro dei costi di ricerca(N), non male!

Torniamo al nostro problema

Ma questo è molto astratto, quindi torniamo al nostro problema. Invece di un semplice numero intero, immagina una stringa che rappresenta il paese di qualcuno nella tabella precedente. Supponiamo che tu abbia un albero che contiene il campo "paese" (colonna 3) della tabella:

Se vuoi sapere chi lavora nel Regno Unito
guardi l'albero per ottenere il nodo che rappresenta la Gran Bretagna
all'interno di "UKnode" troverai la posizione dei registri dei lavoratori del Regno Unito.

Questa ricerca costerà operazioni log(N) anziché N operazioni se si utilizza direttamente l'array. Quello che hai appena presentato è stato indice della banca dati.

È possibile creare un albero dell'indice per qualsiasi gruppo di campi (stringa, numero, 2 righe, numero e stringa, data...) purché si disponga di una funzione per confrontare le chiavi (ad esempio i gruppi di campi) in modo da poter impostare ordine tra le chiavi (che è il caso di tutti i tipi di base nel database).

B+Indicealbero

Sebbene questo albero funzioni bene per ottenere un valore specifico, c'è un GRANDE problema quando è necessario ottenere più elementi tra due valori. Questo costerà O(N) perché dovrai guardare ogni nodo dell'albero e verificare se è compreso tra questi due valori (ad esempio con un attraversamento ordinato dell'albero). Inoltre, questa operazione non è agevole per l'I/O del disco poiché è necessario leggere l'intero albero. Dobbiamo trovare un modo per eseguire in modo efficiente richiesta di portata. Per risolvere questo problema, i database moderni utilizzano una versione modificata dell'albero precedente chiamata B+Tree. In un albero B+Tree:

solo i nodi più bassi (foglie) informazione di magazzino (posizione delle righe nella tabella correlata)
il resto dei nodi sono qui per l'instradamento al nodo corretto durante la ricerca.

Come puoi vedere, ci sono più nodi qui (due volte). In effetti, hai nodi aggiuntivi, "nodi decisionali", che ti aiuteranno a trovare il nodo corretto (che memorizza la posizione delle righe nella tabella associata). Ma la complessità della ricerca è ancora O(log(N)) (c'è solo un livello in più). La grande differenza è questa i nodi al livello inferiore sono collegati ai loro successori.

Con questo B+Tree, se cerchi valori compresi tra 40 e 100:

Devi solo cercare 40 (o il valore più vicino dopo 40 se 40 non esiste) come hai fatto con l'albero precedente.
Quindi raccogli 40 eredi utilizzando i collegamenti eredi diretti fino a raggiungere 100.

Diciamo che trovi M successori e l'albero ha N nodi. Trovare un nodo specifico costa log(N) come l'albero precedente. Ma una volta ottenuto questo nodo, otterrai M successori in M operazioni con riferimenti ai loro successori. Questa ricerca costa solo M+log(N) operazioni rispetto alle N operazioni dell'albero precedente. Inoltre, non è necessario leggere l'intero albero (solo i nodi M+log(N)), il che significa un minore utilizzo del disco. Se M è piccolo (ad esempio 200 righe) e N è grande (1 di righe), ci sarà una GRANDE differenza.

Ma qui ci sono nuovi problemi (di nuovo!). Se aggiungi o cancelli una riga nel database (e quindi nell'indice B+Tree associato):

devi mantenere l'ordine tra i nodi all'interno di un B+Tree, altrimenti non sarai in grado di trovare i nodi all'interno di un albero non ordinato.
è necessario mantenere il numero minimo possibile di livelli in B+Tree, altrimenti la complessità temporale O(log(N)) diventa O(N).

In altre parole, B+Tree deve essere auto-ordinante ed equilibrato. Fortunatamente, questo è possibile con operazioni intelligenti di eliminazione e inserimento. Ma questo ha un costo: gli inserimenti e le cancellazioni in un albero B+ costano O(log(N)). Ecco perché alcuni di voi lo hanno sentito utilizzare troppi indici non è una buona idea. Veramente, stai rallentando l'inserimento/aggiornamento/eliminazione veloce di una riga in una tabellaperché il database deve aggiornare gli indici della tabella utilizzando un'operazione costosa O(log(N)) per ciascun indice. Inoltre, l'aggiunta di indici comporta un carico di lavoro maggiore per gestore delle transazioni (sarà descritto alla fine dell'articolo).

Per maggiori dettagli potete consultare l'articolo di Wikipedia su B+Albero. Se vuoi un esempio di implementazione di B+Tree in un database, dai un'occhiata questo articolo и questo articolo da uno sviluppatore leader di MySQL. Entrambi si concentrano su come InnoDB (il motore MySQL) gestisce gli indici.

Nota: un lettore mi ha detto che, a causa delle ottimizzazioni di basso livello, l'albero B+ dovrebbe essere completamente bilanciato.

Tabella hash

La nostra ultima struttura dati importante è la tabella hash. Questo è molto utile quando vuoi cercare rapidamente i valori. Inoltre, comprendere una tabella hash ci aiuterà in seguito a comprendere un'operazione comune di unione al database chiamata hash join ( join hash). Questa struttura dati viene utilizzata anche dal database per memorizzare alcune cose interne (ad es. tavolo con serratura o pool buffer, vedremo entrambi questi concetti più avanti).

Una tabella hash è una struttura dati che trova rapidamente un elemento tramite la sua chiave. Per costruire una tabella hash è necessario definire:

ключ per i tuoi elementi
funzione hash per le chiavi. Gli hash delle chiavi calcolati forniscono la posizione degli elementi (chiamati segmenti ).
funzione per confrontare le chiavi. Una volta trovato il segmento corretto, devi trovare l'elemento che stai cercando all'interno del segmento utilizzando questo confronto.

Semplice esempio

Facciamo un esempio chiaro:

Questa tabella hash ha 10 segmenti. Siccome sono pigro, ho immaginato solo 5 segmenti, ma so che sei intelligente, quindi ti lascio immaginare gli altri 5 da solo. Ho usato una funzione hash modulo 10 della chiave. In altre parole, memorizzo solo l'ultima cifra della chiave dell'elemento per trovare il suo segmento:

se l'ultima cifra è 0, l'elemento rientra nel segmento 0,
se l'ultima cifra è 1, l'elemento rientra nel segmento 1,
se l'ultima cifra è 2, l'elemento rientra nell'area 2,
...

La funzione di confronto che ho usato è semplicemente l'uguaglianza tra due numeri interi.

Diciamo che vuoi ottenere l'elemento 78:

La tabella hash calcola il codice hash per 78, ovvero 8.
La tabella hash esamina il segmento 8 e il primo elemento che trova è 78.
Ti restituisce l'articolo 78
La ricerca costa solo 2 operazioni (uno per calcolare il valore hash e l'altro per cercare l'elemento all'interno del segmento).

Ora diciamo che vuoi ottenere l'elemento 59:

La tabella hash calcola il codice hash per 59, ovvero 9.
La tabella hash cerca nel segmento 9, il primo elemento trovato è 99. Poiché 99!=59, l'elemento 99 non è un elemento valido.
Utilizzando la stessa logica si prende il secondo elemento (9), il terzo (79), ..., l'ultimo (29).
Elemento non trovato.
La ricerca è costata 7 operazioni.

Buona funzione hash

Come puoi vedere, a seconda del valore che cerchi, il costo non è lo stesso!

Se ora cambio la funzione hash modulo 1 della chiave (cioè prendendo le ultime 000 cifre), la seconda ricerca costa solo 000 operazione poiché non ci sono elementi nel segmento 6. La vera sfida è trovare una buona funzione hash che crei bucket contenenti un numero molto ridotto di elementi.

Nel mio esempio, trovare una buona funzione hash è facile. Ma questo è un esempio semplice, trovare una buona funzione hash è più difficile quando la chiave è:

stringa (ad esempio - cognome)
2 righe (ad esempio: cognome e nome)
2 righe e data (ad esempio: cognome, nome e data di nascita)
...

Con una buona funzione hash, le ricerche nella tabella hash costano O(1).

Array e tabella hash

Perché non utilizzare un array?

Hmm, bella domanda.

La tabella hash può esserlo parzialmente caricato in memoriae i segmenti rimanenti possono rimanere sul disco.
Con un array è necessario utilizzare spazio contiguo in memoria. Se stai caricando una tabella di grandi dimensioni è molto difficile trovare abbastanza spazio continuo.
Per una tabella hash, puoi selezionare la chiave desiderata (ad esempio, paese e cognome della persona).

Per maggiori informazioni potete leggere l'articolo su JavaMappa hash, che è un'implementazione efficiente di una tabella hash; non è necessario conoscere Java per comprendere i concetti trattati in questo articolo.

Fonte: habr.com

Come funzionano i database relazionali (Parte 1)