Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

2 1 Techniques de stockage Caractéristique Performance Taille d’un secteur 512

2 1 Techniques de stockage Caractéristique Performance Taille d’un secteur 512 octets Nbre de plateaux 5 Nbre de têtes 10 Nombre de cylindres 100 000 Nombre de secteurs par piste 4 000 Temps de positionnement moyen 10 ms Vitesse de rotation 7 400 rpm Déplacement de piste à piste 0,5 ms Taux de transfert max. 120 Mo/s TABLE 1 – Spéciﬁcations d’un disque magnétique Exercice 1. Le tableau 1 donne les spéciﬁcations partielles d’un disque magnétique. Répondez aux questions suivantes. 1. Quelle est la capacité d’une piste ?, d’un cylindre ? d’une surface ? du disque ? 2. Quel est le temps de latence maximal ? Quel est le temps de latence moyen ? 3. Quel serait le taux de transfert (en Mo/sec) nécessaire pour pouvoir transmettre le contenu d’une piste en une seule rotation ? Est-ce possible ? Solution : 1. – Capacité d’une piste = nbre de secteurs par piste x taille d’un secteur = 4 000 x 512 = 2 048 000 octets (soit approx 2 Mo) – Capacité d’un cylindre = taille d’une piste x nombre de têtes = 2 048 000 x 10 = 20 480 000 octets (soit approx 20 Mo) – Capacité d’une surface = capacité d’une piste x nombre de cylindres = 2 048 000 x 100 000 = 204 800 000 000 octets (soit approx 204 Go) – Capacité du disque = capacité d’un cylindre x nombre de cylindre = 20 480 000 x 100 000 octets = approx 2 To 2. Le temps de latence maximal est le temps pour une rotation. Ici on a 7400 60 = 123 rotations par seconde, soit une rotation toutes les 1/123=8 ms. Le temps moyen est de 4 ms. 3. Il faut donc pouvoir transférer 2 048 000 octets en 8 ms, soit 250 Mo par seconde. Ce taux dépasse les capacités de transfert du disque. Exercice 2. Étant donné un disque contenant C cylindres, un temps de déplacement entre deux pistes adjacentes de sms ms, donner la formule exprimant le temps de positionnement moyen. On décrira une demande de déplacement par une paire [d, a] où d est la piste de départ et a la piste d’arrivée, et on supposera que toutes les demandes possibles sont équiprobables. Attention, on ne peut pas considérer que les têtes se déplacent en moyenne de C/2 pistes. C’est vrai si la tête de lecture est au bord des plateaux ou de l’axe, mais pas si elle est au milieu du plateau. Philippe Rigaux (philippe.rigaux@cnam.fr), Cours de bases de données 3 Il faut commencer par exprimer le temps de positionnement moyen en fonction d’une position de départ donnée, puis généraliser à l’ensemble des positions de départ possibles. On pourra utiliser les deux formules suivantes : 1. Σn i=1(i) = n×(n+1) 2 2. Σn i=1(i2) = n×(n+1)×(2n+1) 6 et commencer par exprimer le nombre moyen de déplacements en supposant que les têtes de lecture sont en position p. Il restera alors à effectuer la moyenne de l’expression obtenue, pour l’ensemble des valeurs possibles de p. Solution : On commence par calculer le temps en supposant connue la position courante des têtes de lecture, p, avec 1 < p < C. Le nombre moyen de déplacements à effectuer vers une piste i avec 1 ≤i < p est : 1 + 2 + . . . + (p −1) p −1 = p × (p −1) 2 × (p −1) = p 2 De même, le nombre moyen de déplacements à effectuer vers une piste j avec p ≤j ≤C est : 1 + 2 + . . . + (C −p −1) C −p = (C −p) × (C −p + 1) 2 × (C −p) = C −p 2 Noter que pour p = C/2, le nombre moyen de déplacements, dans un sens ou dans l’autre, est de C/4, alors que quand p = 1, le temps de déplacement moyen est de C/2. Pour une position p donnée, la probabilité d’aller en i < p est p/C, et celle d’aller en j > p est (C −p)/C. On obtient donc le nombre de déplacements moyen pour une position p : p2 2 × C + (C −p)2 2 × C Il reste à effectuer la moyenne de cette expression pour l’ensemble des positions de départs pos- sibles, ce qui donne : 1 C × ΣC i=1(i2 + (C −i)2 2 × C ) = 1 2 × C2 × 2 × ΣC i=1(i2) = 1 C2 × C × (C + 1) × (2C + 1) 6 On en déduit que le nombre de déplacements moyen est de l’ordre du tiers du nombre total de pistes (ou cylindres). Exercice 3. Soit un disque de 5 000 cylindres tournant à 12 000 rpm, avec un temps de déplacement entre deux pistes adjacentes égal à 0,2 ms et 500 secteurs de 512 octets par piste. Quel est le temps moyen de lecture d’un bloc de 4 096 ? Solution : Calculer le temps de transfert (8/400 de rotation). Calculer le délai de latence : 12000 rotations pour 60s, donc une rotation en 60/12000= 5 ms. Temps moyen de latence=2,5 ms. Temps moyen de positionnement : environ 1/3 du temps total de balayage du disque, soit 0,5×5000 3 = 1/3s Philippe Rigaux (philippe.rigaux@cnam.fr), Cours de bases de données 4 Exercice 4. On considère un ﬁchier de 1 Go et un buffer de 100 Mo. – quel est le hit ratio en supposant que la probabilité de lire les blocs est uniforme ? – même question, en supposant que 80 % des lectures concernent 200 Mo, les 20 % restant étant répartis uniformément sur 800 Mo ? – avec l’hypothèse précédente, jusqu’à quelle taille de buffer peut-on espérer une amélioration signiﬁcative du hit ratio ? Solution : – Pour la première question le hit ratio est évidemment de 0,1. – Appelons A la partie de la base correspondant aux 200 Mo les plus lus, et B le reste. On remarque tout d’abord que le cache contient 80 % d’enregistrements de A, et 20 % d’enregis- trements de B. Si on fait une lecture d’un enregistrement de A, le hit ratio est de 80 200. Pour B, le hit ratio est de 20 800. On pondère ces valeurs par la probabilité de demander la lecture, respectivement, d’un enregistrement A ou B, soit : 0, 8 × 80 200 + 0, 2 × 20 800 Ce qui est déjà mieux de que le 0,1 obtenu à la première question. – Jusqu’où peut-on espérer une amélioration ? Notons C la taille du cache. La formule qui donne le hit ratio est : 0, 8 × Max(|A|, 0, 8 × C) 200 + 0, 2 × Max(800, 0, 2 × C) 800 Une fois que toutes les données de A (ou de B) sont en mémoire, le hit ratio ne s’améliore plus. Le premier terme de l’équation bénéﬁcie rapidement d’un accroissement de C, jusqu’à C = 250. Tout le ﬁchier A sera alors en mémoire. Ensuite, la petite amélioration du hit ratio en fonction de C devient beaucoup plus faible. Exercice 5. Soit l’ordre SQL suivant : DELETE FROM Film WHERE condition La table est stockée dans un ﬁchier de taille n blocs, sans index. Donner le nombre moyen de blocs à lire, en fonction de n, pour l’exécution de l’ordre SQL dans les cas suivants : – aucun enregistrement ne satisfait la condition ; – la condition porte sur une clé unique et affecte donc un seul enregistrement ; – la condition ne porte pas sur une clé unique (et on ne connaît donc pas à priori le nombre d’enregistrements concernés). Exercice 6. Soit la table de schéma suivant : CREATE TABLE Personne (id INT NOT NULL, nom VARCHAR(40) NOT NULL, prenom VARCHAR(40) NOT NULL, adresse VARCHAR(70), dateNaissance DATE) Cettte table contient 300 000 enregistrements, stockés dans des blocs de taille 4 096 octets. Un enre- gistrement ne peut pas chevaucher deux blocs, et chaque bloc comprend un entête de 200 octets. Philippe Rigaux (philippe.rigaux@cnam.fr), Cours de bases de données 5 1. Donner la taille maximale et la taille minimale d’un enregistrement. On suppose par la suite que tous les enregistrements ont une taille maximale. 2. Quel est le nombre maximal d’enregistrements par bloc ? 3. Quelle est la taille du ﬁchier ? 4. En supposant que le ﬁchier est stocké sur le disque de l’exercice 1, combien de cylindres faut-il pour stocker le ﬁchier ? 5. Quel est le temps moyen de recherche d’un enregistrement dans les deux cas suivants : (a) les blocs sont stockés le plus contigument possible et (b) les blocs sont distribués au hasard sur le disque. 6. On suppose que le ﬁchier est trié sur le nom. Quel est le temps d’une recherche dichotomique pour chercher une personne avec un nom donné ? Solution : 1. Taille minimale : 4 + 1 + 1 + 0 (null) + 0 (null). Taille maximale : 4+ 41+ 41+ 71+ 8 uploads/Litterature/ ed-nfp107-corr-orgaphys-indexation-pdf.pdf