Différences

Ci-dessous, les différences entre deux révisions de la page.

--- cnam:nfp107:seance8 [2023/04/22 15:48] – jcheron
+++ cnam:nfp107:seance8 [2023/04/22 16:20] (Version actuelle) – jcheron
@@ Ligne 52: / Ligne 52: @@
 mais ce choix peut avoir des conséquences sur :
-Les performances sur d'autres opérations
+  * Les performances sur d'autres opérations
-Le volume du stockage (espace disque)
+  * Le volume du stockage (espace disque)
-Le maintien de l'intégrité des données (ACID) ⇒ Atomicité, Cohérence, Isolation, Durabilité ⇒ principes fondateurs des transactions
+  * Le maintien de l'intégrité des données (ACID) ⇒ Atomicité, Cohérence, Isolation, Durabilité ⇒ principes fondateurs des transactions
-Les accès concurrents
+  * Les accès concurrents
-Moteurs de stockage
+==== Moteurs de stockage ====
-Non ordonné
+=== Non ordonné ===
 Le stockage non ordonné stocke généralement les enregistrements dans l'ordre où ils sont insérés. Ce type de stockage offre une bonne efficacité d'insertion O(1), mais des temps de récupération inefficaces O(n).
 Toutefois, ces temps de récupération sont généralement meilleurs, car la plupart des bases de données utilisent des index sur les clés primaires, ce qui se traduit par des temps de récupération de style O(log n) ou O(1) pour les clés qui sont identiques aux décalages des lignes de la base de données dans le système de stockage.
-Ordonné
+=== Ordonné ===
 Le stockage ordonné stocke généralement les enregistrements dans l'ordre et peut devoir les réorganiser ou augmenter la taille du fichier lorsqu'un nouvel enregistrement est inséré, ce qui réduit l'efficacité de l'insertion. Cependant, le stockage ordonné permet une extraction plus efficace, car les enregistrements sont pré-triés, ce qui se traduit par une complexité de O(log n).
-Structures
+==== Structures ====
-Heap
+=== Heap ===
 Les fichiers heap sont des listes d'enregistrements non ordonnées de taille variable.
 Bien qu'ils partagent un nom similaire, les fichiers heap sont très différents des Heap Memory. Les Heap memory sont ordonnées, contrairement aux fichiers heap.
-Principes
+  * Principes
-Les nouveaux enregistrements étant ajoutés à la fin du fichier, ce qui donne un ordre chronologique
+    * Les nouveaux enregistrements étant ajoutés à la fin du fichier, ce qui donne un ordre chronologique
-Récupération efficace lorsque l'identifiant de la mémoire est l'adresse de la mémoire.
+    * Récupération efficace lorsque l'identifiant de la mémoire est l'adresse de la mémoire.
-recherche inefficace, car la recherche doit être linéaire.
+    * recherche inefficace, car la recherche doit être linéaire.
-la suppression est accomplie en marquant les enregistrements sélectionnés comme “supprimés”.
+    * la suppression est accomplie en marquant les enregistrements sélectionnés comme “supprimés”.
-nécessite une réorganisation périodique si le fichier est très volatile (modifié fréquemment).
+    * nécessite une réorganisation périodique si le fichier est très volatile (modifié fréquemment).
-Avantages
+<WRAP info>
-efficace pour le chargement de données en masse
+  * Avantages
-efficace pour les relations relativement petites car les frais d'indexation sont évités
+    * efficace pour le chargement de données en masse
-Efficace lorsque les recherches concernent une grande partie des enregistrements stockés.
+    * efficace pour les relations relativement petites car les frais d'indexation sont évités
-Inconvénients
+    * Efficace lorsque les recherches concernent une grande partie des enregistrements stockés.
-pas efficace pour la recherche sélective à l'aide de valeurs clés, surtout si le fichier est important
+  * Inconvénients
-le tri peut prendre beaucoup de temps
+    * pas efficace pour la recherche sélective à l'aide de valeurs clés, surtout si le fichier est important
-ne convient pas aux données avec beaucoup de changements
+    * le tri peut prendre beaucoup de temps
-Hash
+    * ne convient pas aux données avec beaucoup de changements
+</WRAP>
+=== Hash ===
 Les fonctions de hachage calculent l'adresse de la page dans laquelle l'enregistrement doit être stocké en fonction d'un ou plusieurs champs de l'enregistrement.
 Elles sont choisies de manière à ce que les adresses soient réparties uniformément dans l'espace d'adressage.
@@ Ligne 90: / Ligne 98: @@
 l'adresse unique n'étant pas garantie, des mécanismes de détection et de résolution des collisions sont nécessaires.
+<WRAP info>
 Avantages et inconvénients
-efficace pour les correspondances exactes sur le champ clé
+  * efficace pour les correspondances exactes sur le champ clé
-ne convient pas à l'extraction de plages, qui nécessite un stockage séquentiel
+  * ne convient pas à l'extraction de plages, qui nécessite un stockage séquentiel
-calcule l'endroit où l'enregistrement est stocké en fonction des champs de l'enregistrement.
+  * calcule l'endroit où l'enregistrement est stocké en fonction des champs de l'enregistrement.
-les fonctions de hachage garantissent une répartition uniforme des données
+  * les fonctions de hachage garantissent une répartition uniforme des données
-des collisions sont possibles, d'où la nécessité de détecter et de restaurer les collisions.
+  * des collisions sont possibles, d'où la nécessité de détecter et de restaurer les collisions.
-B-Tree
+</WRAP>
+=== B-Tree ===
 Ce sont les plus couramment utilisés dans la pratique.
-Le temps nécessaire pour accéder à n'importe quel enregistrement est le même car le même nombre de nœuds est recherché.
+  * Le temps nécessaire pour accéder à n'importe quel enregistrement est le même car le même nombre de nœuds est recherché.
-L'index est un index complet, il n'est donc pas nécessaire d'ordonner le fichier de données.
+  * L'index est un index complet, il n'est donc pas nécessaire d'ordonner le fichier de données.
+<WRAP info>
 Avantages et inconvénients
-structure de données polyvalente - accès séquentiel ou aléatoire
+  * structure de données polyvalente - accès séquentiel ou aléatoire
-l'accès est rapide
+  * l'accès est rapide
-supporte efficacement les correspondances exactes, par plage, par clé partielle et par motif.
+  * supporte efficacement les correspondances exactes, par plage, par clé partielle et par motif.
-les fichiers volatiles sont traités efficacement car l'index est dynamique - il s'étend et se contracte au fur et à mesure que la table s'agrandit et se réduit.
+  * les fichiers volatiles sont traités efficacement car l'index est dynamique - il s'étend et se contracte au fur et à mesure que la table s'agrandit et se réduit.
-moins bien adapté aux fichiers relativement stables - dans ce cas, ISAM est plus efficace.
+  * moins bien adapté aux fichiers relativement stables - dans ce cas, ISAM est plus efficace.
+</WRAP>
+//TODO image//
-Fonctionnement des B-Tree
+  * [[https://www.javatpoint.com/b-tree|Fonctionnement des B-Tree]]
-Visualisation
+  * [[https://www.cs.usfca.edu/~galles/visualization/BTree.html|Visualisation]]
+<WRAP todo>
 Implémenter B-TREE en java pour les opérations suivantes :
-Recherche
+  * Recherche
-Insertion
+  * Insertion
-Suppression
+  * Suppression
 Vous avez 15 minutes…
 voir https://www.programiz.com/dsa/b-tree
-Variante B+Tree :
+</WRAP>
+__**Variante B+Tree :**__
 Parcours séquentiel + recherche indexée
-Fonctionnement des B+Tree
+  * [[https://www.javatpoint.com/b-plus-tree|Fonctionnement des B+Tree]]
-Visualisation
+  * [[https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html|Visualisation]]
-ISAM
+=== ISAM ===
 ISAM (acronyme de l'anglais Indexed Sequential Access Method)
@@ Ligne 137: / Ligne 157: @@
 MyISAM utilise B-Tree
-Mysql ⇒ MyISAM
+  * Mysql ⇒ MyISAM
-PostGreSQL ⇒ Unlogged tables
+  * PostGreSQL ⇒ Unlogged tables
-Oracle ⇒ Tablespaces
+  * Oracle ⇒ Tablespaces
 MyISAM ne gère ni les clés étrangères, ni les transactions. Il n'y a pas à vérifier la validité des enregistrements. Cela permet donc un précieux gain de temps sur des tables très fréquemment ouvertes en écriture/lecture.
-Lors de suppressions sur des champs de type VARCHAR, CHAR, BLOB ou TEXT, le moteur supprime le contenu mais la place précédemment supprimée est conservée et peut être réutilisée ultérieurement. L'utilisation de OPTMIZE peut défragmenter la table afin de gagner de la place et ainsi faciliter l'accès aux données.
+Lors de suppressions sur des champs de type VARCHAR, CHAR, BLOB ou TEXT, le moteur supprime le contenu mais la place précédemment supprimée est conservée et peut être réutilisée ultérieurement. L'utilisation de **OPTMIZE** peut défragmenter la table afin de gagner de la place et ainsi faciliter l'accès aux données.
 MyISAM ⇒ très utilisé pour le Web vitrine.
@@ Ligne 148: / Ligne 168: @@
 Une table MyISAM utilise trois fichiers :
-maTable.FRM : Fichier de définition de la table
+  * maTable.FRM : Fichier de définition de la table
-maTable.MYD : Fichier contenant les données de la table
+  * maTable.MYD : Fichier contenant les données de la table
-maTable.MYI : Fichier d'index
+  * maTable.MYI : Fichier d'index
 Permet les recherches en FULL-TEXT ⇒ Recherche avec retour de pertinance
-Exemple :
+__**Exemple :**__
+<sxh sql;gutter:false
 SELECT *, MATCH (Titre, Article) AGAINST ('base de données') AS Score FROM Article ORDER BY score DESC;
-Retour :
+</sxh>
+__**Retour :**__
-IdArticle  | Titre     | Article                                            | Score
+<sxh;gutter:false>
+IdArticle  | Titre     | Article                                          | Score
           | Federated | Le moteur Federated permet de déporter…          | 0,21985759722453
           | Exemple   | Ce type de table est assez particulier…          | 0,15944281721118
@@ Ligne 164: / Ligne 185: @@
           | MyIsam    | Ce moteur est une version évoluée d'ISAM avec…   | 0,068685997386924
           | Memory    | Les tables de type Memory stockent les…          | 0
-Avantages
+</sxh>
-Moteur rapide.
-Possibilité d'écrire et lire en même temps sans risque de verrouillage de table.
+<WRAP info>
-Verrouillage de table manuel.
+  * Avantages
-La mise en cache des clés.
+    * Moteur rapide.
-Gain de place sur le disque.
+    * Possibilité d'écrire et lire en même temps sans risque de verrouillage de table.
-Gain de mémoire lors des mises à jour.
+    * Verrouillage de table manuel.
-Gestion de la recherche FULL-TEXT.
+    * La mise en cache des clés.
-Inconvénients
+    * Gain de place sur le disque.
-Pas de gestion des contraintes de clés étrangères
+    * Gain de mémoire lors des mises à jour.
-Pas de gestion des transactions (pas de COMMIT / ROLLBACK possible).
+    * Gestion de la recherche FULL-TEXT.
-InnoDB
+  * Inconvénients
+    * Pas de gestion des contraintes de clés étrangères
+    * Pas de gestion des transactions (pas de COMMIT / ROLLBACK possible).
+</WRAP>
+=== InnoDB ===
 InnoDB est le moteur par défaut à partir de MySQL 5.5.52. Son principal avantage par rapport aux autres moteurs de stockage de MySQL est qu'il permet des transactions ACID (Atomiques, Cohérentes, Isolées et Durables), ainsi que la gestion des clés étrangères (avec vérification de la cohérence).
 Autrement dit, InnoDB est un moteur de bases de données relationnelles et transactionnelles, comparable à celui utilisé par PostgreSQL.
@@ Ligne 188: / Ligne 214: @@
 Depuis la version 5.6, une extension memcached peut être associée à InnoDB, permettant d'améliorer les performances.
-Avantages
+<WRAP info>
-Verrouillage de ligne.
+  * Avantages
-Gestion du COMMIT/ROLLBACK
+    * Verrouillage de ligne.
-Gestion de gros volumes de données.
+    * Gestion du COMMIT/ROLLBACK
-Gestion des clés étrangères.
+    * Gestion de gros volumes de données.
-Grande panoplie d'éléments de configuration du moteur.
+    * Gestion des clés étrangères.
-Gestion du backup sans bloquer une base en production.
+    * Grande panoplie d'éléments de configuration du moteur.
-Couramment disponible chez les hébergeurs en mutualisé.
+    * Gestion du backup sans bloquer une base en production.
-Inconvénients
+    * Couramment disponible chez les hébergeurs en mutualisé.
-Lenteur de certaines opérations telles que le SELECT COUNT(*) FROM maTable.
+  * Inconvénients
-Statistiques envoyées ne sont pas forcément précises : ce ne sont que des estimations.
+    * Lenteur de certaines opérations telles que le SELECT COUNT(*) FROM maTable.
-Choix d'organisation
+    * Statistiques envoyées ne sont pas forcément précises : ce ne sont que des estimations.
-séquentiel (HEAP)
+</WRAP>
+==== Choix d'organisation ====
+=== séquentiel (HEAP) ===
 Conditions favorables :
-chargement de données dans la base
+  * chargement de données dans la base
-petites tables (occupation de peu de pages)
+  * petites tables (occupation de peu de pages)
-requêtes manipulant des tables entières
+  * requêtes manipulant des tables entières
-pour recupérer de l'espace dû à des DELETE
+  * pour recupérer de l'espace dû à des DELETE
 Eviter :
+  * accès à 1 ou plusieurs tuples
+  * grosses tables
+=== HASH ===
-accès à 1 ou plusieurs tuples
-grosses tables
-HASH
 Conditions favorables :
-recherche sur valeur exacte de clé (le plus rapide)
+  * recherche sur valeur exacte de clé (le plus rapide)
 Eviter :
-recherche sur pattern matching (partie de clé)
+  * recherche sur pattern matching (partie de clé)
-traitement de table entière
+  * traitement de table entière
-joints naturels (systématique sans restriction)
+  * joints naturels (systématique sans restriction)
-ISAM
+=== ISAM ===
 Conditions favorables :
+  * requêtes nécessitant pattern matching ++
+  * la table grossit lentement (peu de réorg.)
+  * clé large
-requêtes nécessitant pattern matching ++
-la table grossit lentement (peu de réorg.)
-clé large
 Eviter :
-si recherche sur clé complète (→HASH)
+  * si recherche sur clé complète (→HASH)
-grosse table à croissance rapide
+  * grosse table à croissance rapide
-BTREE
+=== BTREE ===
 Conditions favorables :
-besoin de pattern matching +
+  * besoin de pattern matching +
-la table grossit vite
+  * la table grossit vite
-table trop grosse pour être souvent réorganisée (Modify)
+  * table trop grosse pour être souvent réorganisée (Modify)
-joints de tables entières
+  * joints de tables entières
 Eviter :
-table statique ou à croissance faible
+  * table statique ou à croissance faible
-large clé
+  * large clé
-si ajout de nouveaux tuples seulement en fin de table (plus grand risque de DEAD LOCK)
+  * si ajout de nouveaux tuples seulement en fin de table (plus grand risque de DEAD LOCK)
-Résumé
-Fonctionnalité	B-Tree	ISAM	Hash	Heap
-chargement de table	++	–	–	+
+=== Résumé ===
-recherche sur clé complète	++	++	+	–
-intervalles/pattern matching	+	+	–	–
+^Fonctionnalité	^B-Tree	^ISAM	^Hash	^Heap ^
-recherches séquentielles	++	++	-	+
+|chargement de table	| ++ | – | – | + |
-recherche sur clé partielle	+	+	–	–
+|recherche sur clé complète | ++ | ++ | + | – |
-accés à données triées	+	–	–	–
+|intervalles/pattern matching | + | + | – | – |
-joints sur larges tables	+	+	–	–
+|recherches séquentielles | ++ | ++ | - | + |
-index croît comme table	+	–	–	–
+|recherche sur clé partielle | + | + | – | – |
-très petite table	+	–	–	–
+|accés à données triées | + | – | – | – |
-très grande table	+	–	–	–
+|joints sur larges tables | + | + | – | – |
+|index croît comme table | + | – | – | – |
+|très petite table	| + | – | – | – |
+|très grande table	| + | – | – | – |
 Source : Bernard Espinasse
-Application
+==== Application ====
 Objectif :
-Benchmark des moteurs de stockage MySQL (InnoDB, MyISAM) et PostgreSQL.
+  * Benchmark des moteurs de stockage MySQL (InnoDB, MyISAM) et PostgreSQL.
-Tests sur petits (100) et + gros volumes de données (10 000)
+  * Tests sur petits (100) et + gros volumes de données (10 000)
-sur les 6 primitives de base
+  * sur les 6 primitives de base
-Etablir un protocole de test (nb de requêtes, concurrency level, méthode/outils utilisés)
-Créer les bases de données :
+<WRAP todo>
-Pour chaque moteur (X3)
+  * Etablir un protocole de test (nb de requêtes, concurrency level, méthode/outils utilisés)
-Pour chaque volume (X2)
+  * Créer les bases de données :
-Incorporer les données avec GenerateData
+    * Pour chaque moteur (X3)
-Mettre en place le protocole établi
+    * Pour chaque volume (X2)
-Réaliser les tests
+  * Incorporer les données avec GenerateData
-Présenter les résultats
+  * Mettre en place le protocole établi
+  * Réaliser les tests
+  * Présenter les résultats
+</WRAP>