Exercice sur les indexes dans une base de données
Bonsoir,
Je travaille sur un exercice traitant sur les indexes en base de donné. J'ai essayer de le faire mais je ne suis pas sur de mes réponses. Pouvez-vous me dire mes erreurs s'il-vous-plait?
Voici l'énoncé:
Citation:
On considère une base de données relationnelle contenant une relation E dont le schéma relationnel est (id, nom, age, salaire). Le champ id est la clé primaire et E contient 1000 tuples avec des valeurs pour id allant de 1 a 1000. Les enregistrements de E sont stockés séquentiellement (en ordre croissant sur le champ id). Chaque bloc de données stocke 5 enregistrements de E.
La base de données contient un index traditionnel (autre qu’un B tree) pour le fichier séquentiel de E. Chaque bloc de l’index contient 10 entrées du type valeur/pointeur où le pointeur permet d’identifier un bloc ou un enregistrement. Les entrées de l’index sont triées par valeur. Pour chercher une clé dans l’index, on considère que le système traverse les blocs de l’index en séquence en démarrant du premier bloc.
a. On considère un index dense (dénoté index1) sur id de E. Combien de blocs le système doit lire pour récupérer le contenu de l’enregistrement dont l’id est 566 ?
b. On souhaite améliorer l’accès aux données de E. Pour cela, on va créer un index (index2) sur index1. Pour être le plus efficace possible, index2 doit-il être dense ou non-dense (épars) ? Justifiez votre Réponse.
c. Une fois que index2 est créé, combien de blocs faudra-t-il traverser pour accéder à l’enregistrement dont l’id est 566.
d. De nombreuse recherches dans la base de données sont réalisées sur le champ salaire. Un index est donc créé sur ce champ. Cet index doit être de préférence : (cochez votre réponse)
° primaire et dense
° primaire et non dense
° secondaire et dense
° secondaire et non dense
e. On considère qu’il y a des 50 valeurs distinctes pour le champ salaire avec un nombre égal d’enregistrements par valeur de salaire. Une approche naïve de l’index sur le salaire stocke les valeurs dupliquées dans l’index. C’est-à-dire que s’il y a x valeurs d’un salaire = 2000, alors il y a x entrées du type (2000, pointeur) dans l’index (celui-ci est toujoours trié par valeur de salaire). Nous souhaitons lire le contenu des enregistrements dont le salaire correspond au salaire maximum de E. Dans le pire des cas, combien de blocs vont être lus ?
f. On considère maintenant une structure moins naïve de l’index sur le champ salaire : il n’y a plus de duplicat des valeurs. Donc s’il y a x valeurs pour le salaire = 2000, il n’y aura qu’une seule entrée dans l’index qui pointera sur un ensemble contigu de blocs stockant les x pointeurs d’enregistrements. Les salaires sont toujours triés dans l’index.
On ignorera l’espace nécessaire au décompte des pointeurs et aux liens entre blocs de pointeurs. Dans le pire des cas, combien de blocs faut-il lire pour lire le contenu des enregistrements dont le salaire est maximum ?
Voici mes réponses:
a) Le bloc doit parcourir : parti sup(566/10) = 57 blocs à parcourir par le système.
b) Index2 doit être non-dense car index 1 est trié et le fichier aussi. Ainsi les recherches seront faites avec moins d’accès.
c) On a 1000 enregistrement (r)
B = 1000/5 = 200 blocs pour stocker tous les enregistrements
Il faut donc faire parti sup(log2 B) = parti sup(log2 200) = 8
8 accès pour faire une recherche binaire à partir d’une clé.
d) J’hésite entre Primaire et non-dense où Secondaire et dense (car salaire pas trié d’après ce que j’ai compris)
e) Je ne sais pas
