Salut Habr ! Je présente à votre attention la traduction de l'article
"Comment fonctionne une base de données relationnelle".

En ce qui concerne les bases de données relationnelles, je ne peux m'empêcher de penser qu'il manque quelque chose. Ils sont utilisés partout. Il existe de nombreuses bases de données différentes, du petit et utile SQLite au puissant Teradata. Mais seuls quelques articles expliquent le fonctionnement de la base de données. Vous pouvez effectuer une recherche par vous-même en utilisant « comment fonctionne une base de données relationnelle » pour voir combien il y a de résultats. De plus, ces articles sont courts. Si vous recherchez les dernières technologies à la mode (BigData, NoSQL ou JavaScript), vous trouverez des articles plus approfondis expliquant leur fonctionnement.

Les bases de données relationnelles sont-elles trop anciennes et trop ennuyeuses pour être expliquées en dehors des cours universitaires, des documents de recherche et des livres ?

En tant que développeur, je déteste utiliser quelque chose que je ne comprends pas. Et si les bases de données sont utilisées depuis plus de 40 ans, il doit y avoir une raison. Au fil des années, j’ai passé des centaines d’heures à vraiment comprendre ces étranges boîtes noires que j’utilise au quotidien. Bases de données relationnelles très intéressant parce qu'ils basé sur des concepts utiles et réutilisables. Si vous souhaitez comprendre une base de données, mais que vous n’avez jamais eu le temps ou l’envie d’approfondir ce vaste sujet, vous devriez apprécier cet article.

Même si le titre de cet article est explicite, le but de cet article n'est pas de comprendre comment utiliser la base de données. Par conséquent, vous devez déjà savoir rédiger une demande de connexion simple et des requêtes de base Cru; sinon vous risquez de ne pas comprendre cet article. C'est la seule chose que vous devez savoir, je vous explique le reste.

Je vais commencer par quelques bases de l'informatique, comme la complexité temporelle des algorithmes (BigO). Je sais que certains d'entre vous détestent ce concept, mais sans lui, vous ne pourrez pas comprendre les subtilités de la base de données. Puisqu'il s'agit d'un vaste sujet, je vais me concentrer sur ce que je pense est important: comment la base de données traite SQL demande. je vais juste présenter concepts de base de base de donnéespour qu'à la fin de l'article vous ayez une idée de ce qui se passe sous le capot.

Puisqu'il s'agit d'un article long et technique qui implique de nombreux algorithmes et structures de données, prenez le temps de le lire. Certains concepts peuvent être difficiles à comprendre ; vous pouvez les ignorer tout en ayant une idée générale.

Pour les plus avertis d’entre vous, cet article est divisé en 3 parties :

Présentation des composants de base de données de bas niveau et de haut niveau
Présentation du processus d'optimisation des requêtes
Présentation de la gestion des transactions et des pools tampons

Retour aux sources

Il y a des années (dans une galaxie lointaine, très lointaine...), les développeurs devaient connaître exactement le nombre d'opérations qu'ils codaient. Ils connaissaient par cœur leurs algorithmes et leurs structures de données car ils ne pouvaient pas se permettre de gaspiller le processeur et la mémoire de leurs ordinateurs lents.

Dans cette partie, je vais vous rappeler certains de ces concepts car ils sont essentiels à la compréhension de la base de données. Je présenterai également le concept index de la base de données.

O(1) contre O(n2)

De nos jours, de nombreux développeurs ne se soucient pas de la complexité temporelle des algorithmes... et ils ont raison !

Mais lorsque vous traitez beaucoup de données (je ne parle pas de milliers) ou si vous avez du mal à gérer des millisecondes, il devient essentiel de comprendre ce concept. Et comme vous pouvez l’imaginer, les bases de données doivent faire face aux deux situations ! Je ne vous ferai pas passer plus de temps que nécessaire pour faire passer le message. Cela nous aidera à comprendre le concept d'optimisation basée sur les coûts plus tard (sables moins coûteux basé à mettre en œuvre pour gérer une entreprise rentable. Ce guide est basé sur trois décennies d'expérience).

Concept

Complexité temporelle de l'algorithme utilisé pour voir combien de temps il faudra pour exécuter un algorithme pour une quantité donnée de données. Pour décrire cette complexité, nous utilisons la notation mathématique grand O. Cette notation est utilisée avec une fonction qui décrit le nombre d'opérations dont un algorithme a besoin pour un nombre donné d'entrées.

Par exemple, quand je dis "cet algorithme a une complexité O(some_function())", cela signifie que l'algorithme nécessite des opérations some_function(a_certain_amount_of_data) pour traiter une certaine quantité de données.

Dans ce cas, Ce n'est pas la quantité de données qui compte**, sinon ** comment le nombre d'opérations augmente avec l'augmentation du volume de données. La complexité temporelle ne fournit pas un nombre exact d'opérations, mais constitue un bon moyen d'estimer le temps d'exécution.

Dans ce graphique, vous pouvez voir le nombre d'opérations par rapport à la quantité de données d'entrée pour différents types de complexités temporelles d'algorithme. J'ai utilisé une échelle logarithmique pour les afficher. Autrement dit, la quantité de données passe rapidement de 1 à 1 milliard. On voit que :

O(1) ou complexité constante reste constante (sinon on ne l'appellerait pas complexité constante).
O(enregistrer(n)) reste faible même avec des milliards de données.
Pire difficulté - O(n2), où le nombre d'opérations augmente rapidement.
Les deux autres complications augmentent tout aussi rapidement.

Exemples

Avec une petite quantité de données, la différence entre O(1) et O(n2) est négligeable. Par exemple, disons que vous disposez d’un algorithme qui doit traiter 2000 XNUMX éléments.

L'algorithme O(1) vous coûtera 1 opération
L'algorithme O(log(n)) vous coûtera 7 opérations
L'algorithme O(n) vous coûtera 2 000 opérations
L'algorithme O(n*log(n)) vous coûtera 14 000 opérations
L'algorithme O(n2) vous coûtera 4 000 000 d'opérations

La différence entre O(1) et O(n2) semble grande (4 millions d'opérations) mais vous perdrez au maximum 2 ms, juste le temps de cligner des yeux. En effet, les processeurs modernes peuvent traiter des centaines de millions d'opérations par seconde. C'est pourquoi les performances et l'optimisation ne sont pas un problème dans de nombreux projets informatiques.

Comme je l'ai dit, il est toujours important de connaître ce concept lorsque l'on travaille avec d'énormes quantités de données. Si cette fois l’algorithme doit traiter 1 000 000 d’éléments (ce qui n’est pas tant que ça pour une base de données) :

L'algorithme O(1) vous coûtera 1 opération
L'algorithme O(log(n)) vous coûtera 14 opérations
L'algorithme O(n) vous coûtera 1 000 000 d'opérations
L'algorithme O(n*log(n)) vous coûtera 14 000 000 d'opérations
L'algorithme O(n2) vous coûtera 1 000 000 000 000 d'opérations

Je n'ai pas fait le calcul, mais je dirais qu'avec l'algorithme O(n2) on a le temps de boire un café (même deux !). Si vous ajoutez un autre 0 au volume de données, vous aurez le temps de faire une sieste.

Allons plus loin

Pour votre information:

Une bonne recherche dans une table de hachage trouve un élément dans O(1).
La recherche d’un arbre bien équilibré produit des résultats en O(log(n)).
La recherche dans un tableau produit des résultats en O(n).
Les meilleurs algorithmes de tri ont une complexité O(n*log(n)).
Un mauvais algorithme de tri a une complexité O(n2).

Remarque : Dans les parties suivantes, nous verrons ces algorithmes et structures de données.

Il existe plusieurs types de complexité temporelle des algorithmes :

scénario de cas moyen
le meilleur cas de scenario
et le pire des cas

La complexité temporelle est souvent le pire des scénarios.

Je parlais seulement de la complexité temporelle de l'algorithme, mais la complexité s'applique aussi à :

consommation mémoire de l'algorithme
algorithme de consommation d'E/S disque

Bien sûr, il existe des complications pires que n2, par exemple :

n4 : c'est terrible ! Certains des algorithmes mentionnés présentent cette complexité.
3n : c'est encore pire ! L’un des algorithmes que nous verrons au milieu de cet article présente cette complexité (et il est actuellement utilisé dans de nombreuses bases de données).
factorielle n : vous n’obtiendrez jamais vos résultats même avec une petite quantité de données.
nn : Si vous rencontrez cette complexité, vous devriez vous demander si c'est vraiment votre domaine d'activité...

Remarque : je ne vous ai pas donné la définition réelle de la désignation du grand O, juste une idée. Vous pouvez lire cet article sur Wikipedia pour la définition réelle (asymptotique).

Tri par fusion

Que faites-vous lorsque vous avez besoin de trier une collection ? Quoi? Vous appelez la fonction sort()... Ok, bonne réponse... Mais pour une base de données, vous devez comprendre comment fonctionne cette fonction sort().

Il existe plusieurs bons algorithmes de tri, je vais donc me concentrer sur le plus important : tri par fusion. Vous ne comprenez peut-être pas pourquoi le tri des données est utile pour le moment, mais vous devriez le faire après la partie optimisation des requêtes. De plus, comprendre le tri par fusion nous aidera plus tard à comprendre l'opération commune de jointure de base de données appelée fusionner rejoindre (association de fusion).

Fusionner

Comme de nombreux algorithmes utiles, le tri par fusion repose sur une astuce : combiner 2 tableaux triés de taille N/2 dans un tableau trié à N éléments ne coûte que N opérations. Cette opération s'appelle la fusion.

Voyons ce que cela signifie avec un exemple simple :

Cette figure montre que pour construire le tableau final trié à 8 éléments, il vous suffit de parcourir une seule fois les 2 tableaux de 4 éléments. Puisque les deux tableaux à 4 éléments sont déjà triés :

1) vous comparez les deux éléments actuels dans deux tableaux (au début current = first)
2) puis prenez le plus petit pour le mettre dans un tableau de 8 éléments
3) et passez à l'élément suivant du tableau où vous avez pris le plus petit élément
et répétez 1,2,3 jusqu'à ce que vous atteigniez le dernier élément de l'un des tableaux.
Ensuite, vous prenez les éléments restants de l’autre tableau pour les placer dans un tableau de 8 éléments.

Cela fonctionne parce que les deux tableaux à 4 éléments sont triés et vous n'avez donc pas besoin de "revenir en arrière" dans ces tableaux.

Maintenant que nous comprenons l'astuce, voici mon pseudocode pour la fusion :

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;

Le tri par fusion divise un problème en problèmes plus petits, puis recherche les résultats des problèmes plus petits pour obtenir le résultat du problème d'origine (remarque : ce type d'algorithme est appelé diviser pour régner). Si vous ne comprenez pas cet algorithme, ne vous inquiétez pas ; Je ne l'ai pas compris la première fois que je l'ai vu. Si cela peut vous aider, je vois cet algorithme comme un algorithme en deux phases :

Phase de division, où le tableau est divisé en tableaux plus petits
La phase de tri est celle où les petits tableaux sont combinés (en utilisant l'union) pour former un tableau plus grand.

Phase de division

Lors de l'étape de division, le réseau est divisé en réseaux unitaires en 3 étapes. Le nombre formel d'étapes est log(N) (puisque N=8, log(N) = 3).

Comment je sais ça?

Je suis un génie! En un mot – les mathématiques. L'idée est que chaque étape divise la taille du tableau d'origine par 2. Le nombre d'étapes est le nombre de fois que vous pouvez diviser le tableau d'origine en deux. C'est la définition exacte d'un logarithme (base 2).

Phase de tri

Dans la phase de tri, vous commencez avec des tableaux unitaires (à un seul élément). Au cours de chaque étape, vous appliquez plusieurs opérations de fusion et le coût total est de N = 8 opérations :

Dans la première étape, vous avez 4 fusions qui coûtent 2 opérations chacune
Dans la deuxième étape, vous avez 2 fusions qui coûtent 4 opérations chacune
Dans la troisième étape vous avez 1 fusion qui coûte 8 opérations

Puisqu'il y a des étapes log(N), coût total N * opérations log(N).

Avantages du tri par fusion

Pourquoi cet algorithme est-il si puissant ?

Parce que:

Vous pouvez le modifier pour réduire l'empreinte mémoire afin de ne pas créer de nouveaux tableaux mais de modifier directement le tableau d'entrée.

Remarque : ce type d'algorithme est appelé in-endroit (tri sans mémoire supplémentaire).

Vous pouvez le modifier pour utiliser simultanément de l'espace disque et une petite quantité de mémoire sans entraîner de surcharge d'E/S disque importante. L'idée est de charger en mémoire uniquement les parties en cours de traitement. Ceci est important lorsque vous devez trier une table de plusieurs Go avec seulement une mémoire tampon de 100 Mo.

Remarque : ce type d'algorithme est appelé tri externe.

Vous pouvez le modifier pour qu'il s'exécute sur plusieurs processus/threads/serveurs.

Par exemple, le tri par fusion distribué est l'un des composants clés Hadoop (qui est une structure dans le big data).

Cet algorithme peut transformer le plomb en or (vraiment !).

Cet algorithme de tri est utilisé dans la plupart (sinon la totalité) des bases de données, mais ce n'est pas le seul. Si vous voulez en savoir plus, vous pouvez lire ceci travail de recherche, qui discute des avantages et des inconvénients des algorithmes courants de tri de bases de données.

Tableau, arbre et table de hachage

Maintenant que nous comprenons l'idée de complexité temporelle et de tri, je devrais vous parler de 3 structures de données. C'est important parce qu'ils sont la base des bases de données modernes. Je présenterai également le concept index de la base de données.

Tableau

Un tableau bidimensionnel est la structure de données la plus simple. Une table peut être considérée comme un tableau. Par exemple:

Ce tableau à 2 dimensions est un tableau avec des lignes et des colonnes :

Chaque ligne représente une entité
Les colonnes stockent les propriétés qui décrivent l'entité.
Chaque colonne stocke des données d'un type spécifique (entier, chaîne, date...).

Ceci est pratique pour stocker et visualiser des données, mais lorsque vous avez besoin de trouver une valeur spécifique, cela ne convient pas.

Par exemple, si vous souhaitez trouver tous les gars qui travaillent au Royaume-Uni, vous devrez examiner chaque ligne pour déterminer si cette ligne appartient au Royaume-Uni. Cela vous coûtera N transactionsOù N - nombre de lignes, ce qui n'est pas mal, mais pourrait-il y avoir un moyen plus rapide ? Il est maintenant temps pour nous de faire connaissance avec les arbres.

Remarque : La plupart des bases de données modernes fournissent des tableaux étendus pour stocker efficacement les tables : tables organisées en tas et tables organisées en index. Mais cela ne change rien au problème de trouver rapidement une condition spécifique dans un groupe de colonnes.

Arborescence et index de la base de données

Un arbre de recherche binaire est un arbre binaire avec une propriété spéciale, la clé à chaque nœud doit être :

supérieur à toutes les clés stockées dans le sous-arbre de gauche
moins que toutes les clés stockées dans le sous-arbre droit

Voyons ce que cela signifie visuellement

Idée

Cet arbre a N = 15 éléments. Disons que je recherche 208 :

Je commence par la racine dont la clé est 136. Puisque 136<208, je regarde le sous-arbre droit du nœud 136.
398>208 donc je regarde le sous-arbre gauche du nœud 398
250>208 donc je regarde le sous-arbre gauche du nœud 250
200<208, donc je regarde le sous-arbre droit du nœud 200. Mais 200 n'a pas de sous-arbre droit, la valeur n'existe pas (car s'il existe, il sera dans le sous-arbre droit 200).

Maintenant disons que j'en cherche 40

Je commence par la racine dont la clé est 136. Puisque 136 > 40, je regarde le sous-arbre gauche du nœud 136.
80 > 40, donc je regarde le sous-arbre gauche du nœud 80
40=40, le nœud existe. Je récupère l'ID de ligne à l'intérieur du nœud (non affiché sur l'image) et recherche dans le tableau l'ID de ligne donné.
Connaître l'ID de la ligne me permet de savoir exactement où se trouvent les données dans le tableau, afin de pouvoir les récupérer instantanément.

Au final, les deux recherches me coûteront le nombre de niveaux à l'intérieur de l'arborescence. Si vous lisez attentivement la partie sur le tri par fusion, vous devriez voir qu'il existe des niveaux log(N). Il s'avère, journal des coûts de recherche (N), pas mal!

Revenons à notre problème

Mais c’est très abstrait, revenons donc à notre problème. Au lieu d’un simple entier, imaginez une chaîne qui représente le pays d’une personne dans le tableau précédent. Disons que vous avez un arbre qui contient le champ « pays » (colonne 3) du tableau :

Si vous voulez savoir qui travaille au Royaume-Uni
vous regardez l'arbre pour obtenir le nœud qui représente la Grande-Bretagne
à l'intérieur de "UKnode", vous trouverez l'emplacement des dossiers des travailleurs britanniques.

Cette recherche coûtera des opérations log(N) au lieu de N opérations si vous utilisez le tableau directement. Ce que vous venez de présenter était index de la base de données.

Vous pouvez créer une arborescence d'index pour n'importe quel groupe de champs (chaîne, nombre, 2 lignes, nombre et chaîne, date...) à condition de disposer d'une fonction pour comparer les clés (c'est-à-dire les groupes de champs) afin de pouvoir définir ordre parmi les clés (ce qui est le cas pour tous les types de base de la base de données).

B+ArbreIndex

Bien que cet arbre fonctionne bien pour obtenir une valeur spécifique, il y a un GROS problème lorsque vous avez besoin obtenir plusieurs éléments entre deux valeurs. Cela coûtera O(N) car vous devrez regarder chaque nœud de l'arbre et vérifier s'il se situe entre ces deux valeurs (par exemple avec un parcours ordonné de l'arbre). De plus, cette opération n'est pas conviviale pour les E/S disque puisque vous devez lire l'intégralité de l'arborescence. Nous devons trouver un moyen d'exécuter efficacement demande de gamme. Pour résoudre ce problème, les bases de données modernes utilisent une version modifiée de l’arborescence précédente appelée B+Tree. Dans un arbre B+Tree :

uniquement les nœuds les plus bas (feuilles) stocker des informations (emplacement des lignes dans la table associée)
le reste des nœuds est ici pour le routage au bon nœud pendant la recherche.

Comme vous pouvez le voir, il y a plus de nœuds ici (deux fois). En effet, vous disposez de nœuds supplémentaires, des « nœuds de décision », qui vous aideront à trouver le bon nœud (qui stocke l'emplacement des lignes dans la table associée). Mais la complexité de la recherche est toujours O(log(N)) (il n'y a qu'un seul niveau supplémentaire). La grande différence est que les nœuds du niveau inférieur sont connectés à leurs successeurs.

Avec ce B+Tree, si vous recherchez des valeurs entre 40 et 100 :

Il vous suffit de rechercher 40 (ou la valeur la plus proche après 40 si 40 n'existe pas) comme vous l'avez fait avec l'arbre précédent.
Collectez ensuite 40 héritiers en utilisant des liens d'héritiers directs jusqu'à atteindre 100.

Disons que vous trouvez M successeurs et que l'arbre a N nœuds. Trouver un nœud spécifique coûte log(N) comme l’arborescence précédente. Mais une fois que vous aurez obtenu ce nœud, vous obtiendrez M successeurs dans M opérations avec des références à leurs successeurs. Cette recherche ne coûte que M+log(N) opérations par rapport aux N opérations sur l’arbre précédent. De plus, vous n'avez pas besoin de lire l'arborescence complète (uniquement les nœuds M+log(N)), ce qui signifie moins d'utilisation du disque. Si M est petit (par exemple 200 lignes) et N est grand (1 000 000 de lignes), il y aura une GRANDE différence.

Mais il y a ici de nouveaux problèmes (encore !). Si vous ajoutez ou supprimez une ligne dans la base de données (et donc dans l'index B+Tree associé) :

vous devez maintenir l'ordre entre les nœuds à l'intérieur d'un B+Tree, sinon vous ne pourrez pas trouver les nœuds à l'intérieur d'un arbre non trié.
vous devez conserver le nombre minimum possible de niveaux dans B+Tree, sinon la complexité temporelle O(log(N)) devient O(N).

En d’autres termes, B+Tree doit être auto-organisé et équilibré. Heureusement, cela est possible grâce aux opérations de suppression et d'insertion intelligentes. Mais cela a un coût : les insertions et suppressions dans un arbre B+ coûtent O(log(N)). C'est pourquoi certains d'entre vous ont entendu ça utiliser trop d'index n'est pas une bonne idée. Vraiment, vous ralentissez l'insertion/mise à jour/suppression rapide d'une ligne dans un tableaucar la base de données doit mettre à jour les index de la table à l'aide d'une opération O(log(N)) coûteuse pour chaque index. De plus, l'ajout d'index signifie une charge de travail plus importante pour gestionnaire de transactions (sera décrit à la fin de l'article).

Pour plus de détails, vous pouvez consulter l'article Wikipédia sur B+Arbre. Si vous voulez un exemple d'implémentation de B+Tree dans une base de données, jetez un oeil cet article и cet article d'un développeur MySQL leader. Ils se concentrent tous deux sur la façon dont InnoDB (le moteur MySQL) gère les index.

Remarque : Un lecteur m'a dit qu'en raison d'optimisations de bas niveau, l'arborescence B+ devrait être complètement équilibrée.

Table de hachage

Notre dernière structure de données importante est la table de hachage. Ceci est très utile lorsque vous souhaitez rechercher rapidement des valeurs. De plus, comprendre une table de hachage nous aidera plus tard à comprendre une opération courante de jointure de base de données appelée jointure par hachage ( jointure de hachage). Cette structure de données est également utilisée par la base de données pour stocker certains éléments internes (par ex. verrouiller la table ou pool tampon, nous verrons ces deux concepts plus tard).

Une table de hachage est une structure de données qui trouve rapidement un élément en fonction de sa clé. Pour construire une table de hachage, vous devez définir :

ключ pour vos éléments
fonction de hachage pour les clés. Les hachages de clés calculés donnent l'emplacement des éléments (appelés segments ).
fonction de comparaison des clés. Une fois que vous avez trouvé le bon segment, vous devez trouver l'élément que vous recherchez au sein du segment à l'aide de cette comparaison.

Exemple simple

Prenons un exemple clair :

Cette table de hachage comporte 10 segments. Parce que je suis paresseux, je n'ai imaginé que 5 segments, mais je sais que tu es intelligent, alors je te laisse imaginer les 5 autres par toi-même. J'ai utilisé une fonction de hachage modulo 10 de la clé. Autrement dit, je stocke uniquement le dernier chiffre de la clé de l'élément pour retrouver son segment :

si le dernier chiffre est 0, l'élément tombe dans le segment 0,
si le dernier chiffre est 1, l'élément tombe dans le segment 1,
si le dernier chiffre est 2, l'élément tombe dans la zone 2,
...

La fonction de comparaison que j'ai utilisée est simplement l'égalité entre deux entiers.

Disons que vous souhaitez obtenir l'élément 78 :

La table de hachage calcule le code de hachage pour 78, soit 8.
La table de hachage examine le segment 8 et le premier élément qu'elle trouve est 78.
Elle vous rend l'article 78
La recherche ne coûte que 2 opérations (un pour calculer la valeur de hachage et l'autre pour rechercher l'élément dans le segment).

Supposons maintenant que vous souhaitiez obtenir l'élément 59 :

La table de hachage calcule le code de hachage pour 59, soit 9.
La table de hachage recherche dans le segment 9, le premier élément trouvé est 99. Puisque 99!=59, l'élément 99 n'est pas un élément valide.
Selon la même logique, le deuxième élément (9), le troisième (79), ..., le dernier (29) sont prélevés.
Élément introuvable.
La recherche a coûté 7 opérations.

Bonne fonction de hachage

Comme vous pouvez le constater, selon la valeur que vous recherchez, le coût n’est pas le même !

Si je change maintenant la fonction de hachage modulo 1 000 000 de la clé (c'est-à-dire en prenant les 6 derniers chiffres), la deuxième recherche ne coûte qu'une opération puisqu'il n'y a aucun élément dans le segment 1. Le véritable défi est de trouver une bonne fonction de hachage qui créera des buckets contenant un très petit nombre d'éléments..

Dans mon exemple, trouver une bonne fonction de hachage est facile. Mais ceci est un exemple simple, trouver une bonne fonction de hachage est plus difficile lorsque la clé est :

chaîne (par exemple - nom de famille)
2 lignes (par exemple - nom et prénom)
2 lignes et date (par exemple - nom, prénom et date de naissance)
...

Avec une bonne fonction de hachage, les recherches dans les tables de hachage coûtent O(1).

Tableau vs table de hachage

Pourquoi ne pas utiliser un tableau ?

Hum, bonne question.

La table de hachage peut être partiellement chargé en mémoire, et les segments restants peuvent rester sur le disque.
Avec un tableau, vous devez utiliser un espace contigu en mémoire. Si vous chargez une grande table il est très difficile de trouver suffisamment d'espace continu.
Pour une table de hachage, vous pouvez sélectionner la clé souhaitée (par exemple, le pays et le nom de famille de la personne).

Pour plus d'informations, vous pouvez lire l'article sur JavaCarte de hachage, qui est une implémentation efficace d'une table de hachage ; vous n'avez pas besoin de comprendre Java pour comprendre les concepts abordés dans cet article.

Source: habr.com

Comment fonctionnent les bases de données relationnelles (partie 1)