L3 MIAGE BD – FOAD 1
Exercice à faire par groupes de 2 binômes officiels (donc 4 étudiants en général). A
rendre en PDF à l’adresse dga@[Link] en mettant comme sujet
FOAD1 GROUPE DE TD <ici votre groupe de td>
Ne pas oublier d’indiquer tous vos noms et prénoms dans le PDF.
Date limite : le lendemain de votre FOAD (minuit).
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)
Cette table contient 100 000 enregistrements, stockés dans des blocs (pages) de taille
2048 octets. Un enregistrement ne peut pas chevaucher deux blocs, et chaque bloc
comprend un entête de 300 octets. Un INT est stocké sur 4 octets, un VARCHAR(x) entre
1 et x octets, et une date sur 7 octets. Une valeur NULL prend 1 octet.
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 fichier ?
4. On suppose le fichier stocké sur un disque dont le temps d’accès à un bloc au hasard est
de 1ms. De même, passer d’un bloc au bloc contigu prends 0,1 ms. 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.
5. On suppose que le fichier est trié sur le nom. Quel est le temps d’une recherche
dichotomique pour chercher une personne avec un nom donné ?
6. On suppose maintenant que le fichier est stocké dans un arbre B d’ordre 4 construit sur
l’attribut nom. On supposera que les autres attributs ne prennent pas de place.
Donnez une estimation de la profondeur de l’arbre.
7. En supposant le même disque que précédemment, et en supposant que les pages de
l’arbre sont stockées au hasard, donnez une estimation du temps de recherche d’un
élément.
8. Proposer une stratégie de hachage du fichier sur le nom (fonction de hachage, nombre
de pages à réserver).
9. Donnez le temps de recherche d’un élément sur un nom donné, toujours pour le même
disque.
10. Donnez le temps de recherche des éléments dans un intervalle de noms donné,
toujours pour le même disque.
