La question générale

Quelles sont les différences entre les algorithmes utilisant des structures de données et les algorithmes utilisant des bases de données?

Un certain contexte

C'est une question qui m'écoute depuis un certain temps et je n'ai pas pu trouver de réponse convaincante.

Actuellement, je travaille à renforcer ma compréhension des algorithmes qui, bien sûr, impliquent fortement les structures de données. Ce sont des structures de base telles que Bag, Queue, Stack, Priority Queue et Heap.

J'utilise également quotidiennement des bases de données pour stocker les données qui ont été traitées et soumises par l'utilisateur final ou traitées par le programme. Je récupère et soumets les données via un DAL, qui a ses propres structures de données qui sont générées en fonction des tables de la base de données.

Mes questions surviennent lorsque j'ai la possibilité de trier les données à l'aide de la base de données pour me les renvoyer ordonnées de manière ascendante / descendante ou de récupérer et de charger les données dans ma logique, de traiter ces données dans une file d'attente prioritaire et de trier par tas tout. Ou un autre serait de rechercher des enregistrements à l'aide de la base de données plutôt que de charger un sous-ensemble des enregistrements et d'utiliser quelque chose comme la recherche binaire pour trouver l'enregistrement ou les enregistrements qui m'intéressent.

Dans mon esprit, j'essaierais d'avoir autant d'opérations sur l'extrémité de la base de données avant de l'envoyer car la communication coûte cher. Cela me fait également me demander quand utilisez-vous des algorithmes et des structures de données strictement définis dans votre propre logique plutôt que pour traiter des données que celles de la base de données?

Voici donc les questions ...

Des questions

1. Quelles sont les différences entre les structures de données et les bases de données?
2. Quand utilisons-nous des algorithmes qui utilisent des structures de données définies uniquement dans votre propre logique et non celle de la base de données?
3. @Harvey post: Quand les méthodes de la base de données deviennent-elles moins efficaces à utiliser que les méthodes de votre propre logique?
   • @mirculixx post: Qu'est - ce qui rend une méthode efficace?
4. @Harvey post: Comment le traitement des données avec des structures de données est-il plus rapide que de le faire dans la base de données?

Clarifications

1. @Grant post: Les bases de données avec lesquelles je travaille normalement sont relationnelles et ces questions découlent de leur travail avec elles. Cependant, je pense que ces questions sont applicables à tout cadre de persistance (quand je dis cadre, je le pense dans le sens le plus général).

Je sais que les réponses sans contexte spécifique sont difficiles. Des éléments de réflexion, des conseils ou des points de discussion sont principalement ce que je recherche et seraient les plus appréciés!

Les structures de données sont, pour la plupart:

1. Résident de la mémoire,
2. Transitoire,
3. De taille limitée,
4. Pas rentrant sans ajouter des mécanismes de concurrence comme les verrous ou l'immuabilité,
5. Non conforme à ACID ,
6. Rapide, si choisi avec soin.

Les bases de données sont, pour la plupart:

1. Lié au disque,
2. Persistant,
3. Grand,
4. En toute sécurité simultanée,
5. Conforme ACID, avec des capacités transactionnelles ,
6. Plus lent que les structures de données

Les structures de données sont destinées à être transmises d'un endroit à un autre et utilisées en interne dans un programme. À quand remonte la dernière fois que vous avez envoyé des données d'une page Web à un serveur Web à l'aide d'une base de données, ou effectué un calcul sur une base de données entièrement résidente en mémoire?

Les systèmes de base de données utilisent des structures de données dans le cadre de leur implémentation interne. C'est une question de taille et de portée; vous utilisez des structures de données dans votre programme, mais un système de base de données est un programme à part entière.

Quelles sont les différences entre les structures de données et les bases de données?

À un niveau abstrait, il n'y en a pas - une base de données est une structure de données.

À un niveau spécifique, les bases de données ont généralement pour but de conserver les données, généralement dans un format optimisé pour les insertions, les mises à jour, la récupération, la jonction ou pour tout autre but (ou une combinaison).

Par exemple, si vous comparez une table dans un SGBDR pour dire un tableau de données, la différence peut être dans l'exécution de l'algorithme, la quantité de code que vous devez écrire, la quantité de mémoire dont vous avez besoin pour exécuter l'algorithme, ou la flexibilité de travailler / accéder aux données de l'extérieur de votre programme / algorithme.

Quand utilisons-nous des algorithmes qui utilisent des structures de données définies uniquement dans votre propre logique et non celle de la base de données?

Dans la tendance, je dirais

a) d'utiliser une base de données si vous avez besoin de conserver des données de manière accessible au-delà de l'exécution ou de l'objectif de l'algorithme spécifique.

b) d'utiliser votre propre structure de données (en mémoire) si la vitesse d'exécution est importante ou si la persistance n'est pas requise

Par exemple, si votre algorithme traite les enregistrements client, vous pouvez vouloir stocker ces enregistrements client (par exemple pour trouver tous les clients dans une zone particulière) pour une utilisation ultérieure par un autre programme / algorithme et dans un but entièrement différent (par exemple, pour trouver les clients les plus précieux ). Dans ce cas, l'utilisation d'une base de données pour conserver les données est probablement une bonne idée.

Notez, cependant, qu'il existe le concept de bases de données en mémoire qui ne conservent pas nécessairement les données, pour des raisons de performances. Par exemple, Redis ou HANA .

Quand les méthodes de la base de données deviennent-elles moins efficaces à utiliser que les méthodes de votre propre logique?

La réponse dépend beaucoup des circonstances et du (type de) base de données utilisée. Je reformulerais la question en "qu'est-ce qui rend une méthode efficace?" Cela devient alors un exercice d'évaluation des méthodes (= algorithme) que vous utiliseriez pour votre propre structure de données par rapport aux méthodes utilisées par la base de données. Voir également le point suivant.

Comment le traitement des données avec des structures de données est-il plus rapide que de le faire dans la base de données?

Encore une fois, cela dépend des détails. En général, le traitement des données en mémoire, directement accessibles au processus qui exécute votre algorithme, est plus rapide que d'envoyer une demande à un autre processus (sur le même ordinateur ou sur un réseau) et de lui demander de renvoyer les résultats . Cependant, si les données résident déjà dans la base de données, lui envoyer une commande - par exemple, une instruction SQL pour joindre deux tables et calculer une fonction d'agrégation - et récupérer uniquement un petit résumé ou un sous-ensemble des données peut être beaucoup plus efficace que le premier transfert de tous les et calculer les résultats localement (en utilisant vos propres structures de données).

L'accès au disque est principalement ce qui coûte le plus cher dans cette opération, plus souvent que l'accès au réseau (http://serverfault.com/questions/238417/are-networks-now-faster-than-disks). À moins que votre base de données ne se trouve sur au moins un réseau à 1 Gbit / s et le même réseau que votre serveur Web \ application, les performances du réseau n'auront pas autant d'importance que les performances du disque pour les ensembles de données plus volumineux. Ou si vos données résident sur des disques SSD très rapides, ce qui sera plus rapide qu'un accès réseau classique. De plus, les bases de données fournissent généralement un mécanisme IPC comme des canaux nommés au lieu d'utiliser TCP / IP si la base de données réside sur le même serveur que votre serveur d'applications.

Si vous pouvez conserver la plupart de la \ structure de données enire en mémoire entre les requêtes, ce sera généralement votre meilleur pari. Si vous ne le pouvez pas, il est difficile de battre une bonne structure de base de données avec des tables normalisées et des indices appropriés pour les performances de recherche et de mise à jour sur autre chose que de petits ensembles d'enregistrements, en particulier dans un système avec des millions d'enregistrements.

Les bases de données relationnelles utilisent généralement une arborescence B + ou une variante de celle-ci sous le capot et comportent de nombreuses optimisations telles que l'alignement des données sur le disque et les pools de mémoire tampon pour les enregistrements fréquemment consultés. Cela les rend excellents dans le traitement rapide de grands ensembles de données, surtout si l'agrégation ou le filtrage sont impliqués.

Qu'entendez-vous par une base de données? Voulez-vous dire une base de données relationnelle comme MySQL ou SQL Server? Une base de données relationnelle est une structure de métadonnées qui prend en charge un sous-ensemble des opérations définies par le modèle relationnel . La théorie du modèle relationnel qui a été principalement élaborée par Edgar Codd dans les années 60.

Le modèle relationnel est très polyvalent et flexible, mais cela signifie qu'il ne peut tirer aucun avantage de la structure des données ou des modèles d'accès. Les structures de données sont utiles lorsque vous savez quelque chose sur les données et comment elles seront accessibles. Par exemple, si vous savez que les dernières données que vous mettez dans une structure de données seront les premières données que vous souhaitez retirer, vous pouvez utiliser une pile.

J'ai appelé la base de données relationnelle une structure de métadonnées car il s'agit généralement d'une grosse liasse de logiciels qui utilise de nombreuses structures de données telles que des piles, des files d'attente, des arbres et des listes pour créer la structure de données abstraite d'une table relationnelle.