Concours d'un autre temps

[VirtuaProf]

Serieux savoir coder en python c'est vraiment utile ?
C'est pas mieux l'intelligence artificielle ? apprendre a apprendre ? connaitre descartes et darwin ? pour des jeunes au collège ou au lycée ?

bon tant pis pour moi...
pour les pros du pyhton, chatgpt a bon en dessous ? si oui ca m'a pris 10 minutes pour traiter a l'heure ou les futurs profs normaux sont encore en examen

examen education nationale capes informatique 20/03/24 3ème concours


La correction selon ChatGpt :

QUESTION 1 - Voici une fonction récursive en Python pour rechercher une clé dans un arbre binaire de recherche :
python
Copy code
class Noeud:
def __init__(self, clef: int, gauche=None, droite=None):
self.gauche = gauche
self.droite = droite
self.clef = clef

def recherche_noeud(noeud: Noeud, k: int) -> bool:
"""
Recherche récursive d'une clé dans un arbre binaire de recherche.

:param noeud: Le nœud à partir duquel commencer la recherche.
:param k: La clé à rechercher.
:return: True si la clé est trouvée, False sinon.
"""
# Si le nœud est None, la clé n'est pas trouvée
if noeud is None:
return False

# Si la clé est égale à la clé du nœud actuel, la clé est trouvée
if k == noeud.clef:
return True

# Si la clé est inférieure à la clé du nœud actuel, recherche dans le sous-arbre gauche
if k < noeud.clef:
return recherche_noeud(noeud.gauche, k)

# Si la clé est supérieure à la clé du nœud actuel, recherche dans le sous-arbre droit
if k > noeud.clef:
return recherche_noeud(noeud.droite, k)

# Exemple d'utilisation
# Création de l'arbre de la Figure 1
arbre = Noeud(42, Noeud(-15, Noeud(-6000), Noeud(12)), Noeud(177, None, None))

# Recherche de la clé 12 dans l'arbre
print(recherche_noeud(arbre, 12)) # Devrait afficher True

Cette fonction prend en entrée un nœud de départ dans l'arbre et une clé à rechercher. Elle effectue une recherche récursive dans l'arbre en suivant les règles des arbres binaires de recherche. Si la clé est trouvée, elle retourne True, sinon False.

Question #2: Complexité algorithmique de la fonction de recherche dans un arbre binaire de recherche (ABR) en fonction du nombre de nœuds de l'arbre :
La complexité de la fonction de recherche dépend de la hauteur de l'arbre dans le pire des cas. Dans un ABR équilibré, la hauteur est logarithmique par rapport au nombre de nœuds (O(log n)), ce qui représente le cas idéal. Cependant, dans le pire des cas, lorsque l'arbre est déséquilibré (par exemple, s'il ressemble à une liste chaînée), la hauteur de l'arbre devient linéaire par rapport au nombre de nœuds (O(n)).
Donc, la complexité de la fonction de recherche dans un ABR est O(h), où h est la hauteur de l'arbre. Dans le meilleur des cas (ABR équilibré), h est O(log n), et dans le pire des cas (ABR déséquilibré), h est O(n).
Question #3: Fonction de collecte des valeurs des clés des nœuds dans un ABR par ordre croissant :
Voici une fonction récursive pour collecter les valeurs des clés des nœuds dans un ABR par ordre croissant :
python
Copy code
def collecte_noeuds(noeud: Noeud) -> List[int]:
"""
Collecte récursive des valeurs des clés des nœuds dans un arbre binaire de recherche par ordre croissant.

:param noeud: Le nœud à partir duquel commencer la collecte.
:return: Une liste des valeurs des clés des nœuds dans l'arbre par ordre croissant.
"""
if noeud is None:
return []

# Collecte récursive des valeurs dans le sous-arbre gauche
valeurs_gauche = collecte_noeuds(noeud.gauche)

# Ajout de la valeur du nœud actuel
valeurs_gauche.append(noeud.clef)

# Collecte récursive des valeurs dans le sous-arbre droit
valeurs_droite = collecte_noeuds(noeud.droite)

# Concaténation des valeurs
return valeurs_gauche + valeurs_droite

# Exemple d'utilisation
valeurs_ordre_croissant = collecte_noeuds(arbre)
print(valeurs_ordre_croissant)

Cette fonction collecte les valeurs des clés des nœuds dans un ABR en suivant un parcours récursif en profondeur. Les valeurs sont collectées dans l'ordre croissant en parcourant d'abord le sous-arbre gauche, puis en ajoutant la valeur du nœud actuel, et enfin en parcourant le sous-arbre droit.
Question #4: Incohérence de l'algorithme proposé est_ABR_1 :
L'algorithme est_ABR_1 suppose incorrectement que vérifier les clefs de chaque nœud et de ses enfants est suffisant pour garantir que l'arbre est un ABR. Cependant, cet algorithme ne prend pas en compte les relations d'ordre entre les nœuds au niveau global de l'arbre. Un contre-exemple peut être un arbre où un nœud gauche a une clé plus grande que la clé de son parent, ce qui viole la propriété des ABR.
Question #5, #6 et #7: L'implémentation de l'algorithme correct est_ABR_2_aux :
Voici une implémentation de la fonction est_ABR_2_aux qui propage les intervalles de haut en bas et décide si l'arbre binaire courant est un arbre binaire de recherche :
python
Copy code
INF = float('-inf')
SUP = float('inf')

def est_ABR_2_aux(noeud: Noeud, inf: int, sup: int) -> bool:
"""
Vérifie si l'arbre binaire courant est un arbre binaire de recherche en propageant les intervalles.

:param noeud: Le nœud courant à vérifier.
:param inf: Borne inférieure de l'intervalle pour les clés des nœuds.
:param sup: Borne supérieure de l'intervalle pour les clés des nœuds.
:return: True si l'arbre binaire courant est un ABR, False sinon.
"""
if noeud is None:
return True

# Vérification de la condition de l'invariant structurel
if inf <= noeud.clef <= sup:
# Appel récursif sur le sous-arbre gauche et droit
return est_ABR_2_aux(noeud.gauche, inf, noeud.clef) and est_ABR_2_aux(noeud.droite, noeud.clef, sup)
else:
return False

# Exemple d'utilisation
est_ABR = est_ABR_2_aux(arbre, INF, SUP)
print(est_ABR)

Cette fonction utilise la méthode de propagation des intervalles pour vérifier si chaque nœud et ses sous-arbres respectent l'invariant structurel des ABR. Si oui, l'arbre est considéré comme un ABR, sinon, il ne l'est pas.

Question #8: Les arbres de la Figure 3 sont-ils des B-trees d'ordre 2 ?
Pour qu'un arbre soit considéré comme un B-tree d'ordre 2, il doit satisfaire certaines propriétés. En particulier, il doit respecter les conditions suivantes :
Chaque nœud (sauf la racine) doit contenir au moins 1 clé et au plus 3 clés.
Chaque nœud (sauf la racine) doit avoir au moins 2 enfants et au plus 4 enfants.
Les clés doivent être triées dans chaque nœud.
Tous les chemins de la racine à une feuille doivent avoir la même longueur.
Examinons chaque arbre de la Figure 3 pour voir s'ils satisfont ces conditions :
(a) Arbre 1 :
Chaque nœud (sauf la racine) contient au moins 1 clé et au plus 3 clés.
Chaque nœud (sauf la racine) a au moins 2 enfants et au plus 4 enfants.
Les clés sont triées dans chaque nœud.
Tous les chemins de la racine à une feuille ont la même longueur.
Conclusion : Oui, l'arbre 1 est un B-tree d'ordre 2.
(b) Arbre 2 :
Ne satisfait pas la condition de tri des clés dans chaque nœud (les clés ne sont pas triées).
Conclusion : Non, l'arbre 2 n'est pas un B-tree d'ordre 2.
(c) Arbre 3 :
Chaque nœud (sauf la racine) contient au moins 1 clé et au plus 3 clés.
Chaque nœud (sauf la racine) a au moins 2 enfants et au plus 4 enfants.
Les clés sont triées dans chaque nœud.
Tous les chemins de la racine à une feuille ont la même longueur.
Conclusion : Oui, l'arbre 3 est un B-tree d'ordre 2.
Question #9: Écrire une fonction récursive d'impression d'un B-tree
Voici une implémentation de la méthode print_node dans la classe BTreeNode pour imprimer les nœuds du B-tree :
python
Copy code
class BTreeNode:
def __init__(self, t: int, is_leaf: bool = False):
self.is_leaf = is_leaf
self.keys = []
self.children = []
self.order = t
self.n = 0

def print_node(self, level=0):
print("Niveau", level)
for i in range(self.n):
print(self.keys, end=" ")
print()

if not self.is_leaf:
for child in self.children:
child.print_node(level + 1)

[VirtuaProf]

la suite :
Question #10
Dans le B-tree de la Figure 4, pour rechercher la clé ayant la valeur 8, voici les étapes à suivre :
Commencez par le nœud racine et cherchez la première clé qui est supérieure ou égale à 8.
Si la clé est trouvée dans le nœud courant, la recherche est terminée.
Si la clé est plus grande que toutes les clés du nœud courant, passez au fils à droite du dernier nœud contenant une clé plus petite que 8.
Répétez les étapes 1 à 3 jusqu'à ce que la clé soit trouvée ou que vous atteigniez une feuille.
Question #11
Pour un nœud fixé, la condition d'arrêt de la recherche dans ce nœud est lorsque la clé est trouvée dans ce nœud ou lorsque vous atteignez une feuille (c'est-à-dire un nœud sans enfants). Le numéro du sous-arbre dans lequel rechercher récursivement dépend de la position de la clé par rapport aux clés dans le nœud courant.
Question #12
Voici une implémentation en Python de la fonction recherche_clef pour rechercher la clé k dans un B-tree à partir du nœud courant :
python
Copy code
class BTreeNode:
# Autres méthodes de la classe BTreeNode

def recherche_clef(self, k: int) -> bool:
# Recherche la clé k dans le nœud courant
i = 0
while i < self.n and k > self.keys:
i += 1

if i < self.n and k == self.keys:
return True

if self.is_leaf:
return False

return self.children.recherche_clef(k)

Question #13
Pour montrer que
�max=1+2((�+1)ℎ−1)
N
max
​
=1+2((f+1)
h
−1) pour
ℎ<�2
h<
2
p
​
, nous pouvons utiliser une approche par induction sur la hauteur de l'arbre.
Question #14
Pour montrer que
�max=2((2−1)ℎ+1−1)
N
max
​
=2((2−1)
h+1
−1) pour
ℎ≥�2
h≥
2
p
​
, nous pouvons également utiliser une approche par induction sur la hauteur de l'arbre.
Question #15
En utilisant les résultats des questions précédentes, nous pouvons obtenir un encadrement du nombre de clés contenues dans un B-tree d'ordre
�
f et de hauteur
ℎ
h.
Question #16
Pour optimiser le coût de la recherche dans un nœud, nous pouvons utiliser une recherche binaire sur la liste triée de clés dans le nœud, ce qui réduit la complexité de
�(log⁡�)
O(logn), où
�
n est le nombre de clés dans le nœud.
Question #17
En conclusion, la complexité de la recherche dans un B-tree dépend de la hauteur de l'arbre. Pour un B-tree équilibré, la hauteur est logarithmique par rapport au nombre de clés dans l'arbre, ce qui donne une complexité de recherche moyenne de
�(log⁡�)
O(logn), où
�
n est le nombre total de clés dans l'arbre.
Question #18
Pour insérer la clé 23 dans le B-tree de la Figure 4, nous suivons les étapes suivantes :
Commencez par le nœud racine et recherchez le nœud approprié pour insérer la clé.
En parcourant l'arbre, nous trouvons que la clé 23 doit être insérée dans le nœud contenant les clés 20, 25 et 30.
Cependant, ce nœud est déjà complet avec 3 clés, donc il doit être scindé.
La clé médiane (25) est promue vers le nœud parent, et les clés restantes (20 et 23) sont réparties entre les deux nouveaux nœuds créés.
Question #19
Voici une implémentation de la fonction insertion_position pour calculer l'indice auquel une clé doit être insérée dans la liste des clés d'un nœud :
python
Copy code
class BTreeNode:
# Autres méthodes de la classe BTreeNode

def insertion_position(self, k: int) -> int:
i = 0
while i < self.n and k > self.keys:
i += 1
return i

Question #20
En utilisant la fonction précédente, voici une implémentation de la fonction insertion_non_complet qui insère une clé dans un nœud non complet :
python
Copy code
class BTreeNode:
# Autres méthodes de la classe BTreeNode

def insertion_non_complet(self, k: int):
i = self.insertion_position(k)
self.keys.insert(i, k)
self.n += 1

Question #21
La condition en Python pour déterminer qu'un nœud x est complet peut être formulée comme suit :
python
Copy code
if x.n == 2 * self.ordre - 1:
# Le nœud est complet

Question #22
Voici l'implémentation de la méthode split d'un nœud, qui divise le nœud en deux parties lorsque le nombre de clés dépasse
2�+1
2f+1, et renvoie la clé médiane et le nouveau nœud créé :
python
Copy code
class BTreeNode:
# Autres méthodes de la classe BTreeNode

def split(self):
median_index = len(self.keys) // 2
median_value = self.keys[median_index]

left_node = BTreeNode(self.ordre)
left_node.keys = self.keys[:median_index]
left_node.n = len(left_node.keys)

right_node = BTreeNode(self.ordre)
right_node.keys = self.keys[median_index + 1:]
right_node.n = len(right_node.keys)

return median_value, left_node, right_node

Question #23
Si la racine est complète lors de l'insertion, elle doit être scindée en deux nouveaux nœuds, et la clé médiane doit être promue pour devenir la nouvelle racine. Si la racine est scindée, la hauteur de l'arbre augmente d'un niveau.
QUESTION 24 :

Voici l'implémentation des méthodes make_new_root et insert :
python
Copy code
class BTree:
def make_new_root(self, k, left_child, right_child):
new_root = BTreeNode(self.ordre)
new_root.keys = [k]
new_root.children = [left_child, right_child]
new_root.n = 1
self.root = new_root

def insert(self, k):
if len(self.root.keys) == 2 * self.root.ordre - 1:
median_value, left_node, right_node = self.root.split()
self.make_new_root(median_value, left_node, right_node)
self.root.insert_non_full(k)


class BTreeNode:
# Autres méthodes de la classe BTreeNode

def make_new_root(self, k, left_child, right_child):
self.keys = [k]
self.children = [left_child, right_child]
self.n = 1

def insert_non_full(self, k):
i = self.insertion_position(k)
if self.is_leaf():
self.keys.insert(i, k)
self.n += 1
else:
if self.children.n == 2 * self.ordre - 1:
median_value, left_node, right_node = self.children.split()
self.keys.insert(i, median_value)
self.children.pop(i)
self.children.insert(i, left_node)
self.children.insert(i + 1, right_node)
self.n += 1
if k > median_value:
i += 1
self.children.insert_non_full(k)


Ces méthodes permettent de gérer l'insertion dans un B-tree, y compris le cas où la racine est complète et doit être scindée. La méthode make_new_root crée une nouvelle racine avec la clé médiane et les deux nouveaux nœuds gauche et droit. La méthode insert dans BTree vérifie d'abord si la racine est complète avant d'insérer la clé dans le B-tree. La méthode insert_non_full dans BTreeNode gère l'insertion dans un nœud qui n'est pas complet.

You
Question #25
Terminer l’implémentation de l’insertion en implémentant la méthode insert de la classe BTreeNode.
ChatGPT
ChatGPT
Pour terminer l'implémentation de l'insertion dans la classe BTreeNode, nous devons compléter la méthode insert. Voici comment cela peut être fait :
python
Copy code
class BTreeNode:
# Autres méthodes de la classe BTreeNode

def insert(self, k):
i = self.insertion_position(k)

if self.is_leaf():
self.keys.insert(i, k)
self.n += 1
else:
if self.children.n == 2 * self.ordre - 1:
median_value, left_node, right_node = self.children.split()
self.keys.insert(i, median_value)
self.children.pop(i)
self.children.insert(i, left_node)
self.children.insert(i + 1, right_node)
self.n += 1
if k > median_value:
i += 1
self.children.insert(k)

# Autres méthodes de la classe BTreeNode


Dans cette méthode insert, nous insérons la clé k dans le nœud courant. Si le nœud est une feuille, nous insérons simplement la clé à la bonne position dans la liste des clés. Sinon, si le nœud est plein, nous scindons le nœud et insérons la clé médiane dans le nœud parent. Ensuite, nous insérons récursivement la clé dans le sous-arbre approprié. Si le nœud n'est pas plein, nous insérons simplement la clé dans le sous-arbre approprié.
Question 26
Dans la relation Characters, le fait que CharID soit une clé primaire signifie que chaque enregistrement de cette table doit avoir une valeur unique pour l'attribut CharID. Cela garantit l'unicité de chaque personnage dans la table.
Quant à l'attribut WorkID, il n'est pas explicitement défini comme une clé étrangère dans la description fournie. Pour être considéré comme une clé étrangère, il devrait référencer une clé primaire d'une autre table. Dans ce cas, il semble être un identifiant associé à l'œuvre littéraire à laquelle chaque personnage appartient. Sans plus de contexte, il est difficile de déterminer s'il s'agit d'une clé étrangère.
Question 27
Voici les requêtes SQL correspondant à chaque recherche (R1, R2, R3, R4) :
R1 : Rechercher toutes les informations sur le personnage identifié par '2musician-rj' dans la table 'Characters'.
sql
Copy code
SELECT * FROM Characters WHERE CharID = '2musician-rj';

R2 : Rechercher le nombre de mots prononcés par le personnage identifié par '2musician-rj' dans la table 'Characters'.
sql
Copy code
SELECT SpeechCount FROM Characters WHERE CharID = '2musician-rj';

R3 : Lister tous les titres longs des œuvres de Shakespeare écrites entre 1589 et 1600 dans la table 'Works'.
sql
Copy code
SELECT LongTitle FROM Works WHERE Date BETWEEN 1589 AND 1600;

R4 : Lister tous les titres longs des œuvres où apparaissent des musiciennes ou des musiciens dans la table 'Works'.
sql
Copy code
SELECT LongTitle FROM Works WHERE WorkID IN (SELECT DISTINCT WorkID FROM Characters WHERE CharName LIKE '%Musician%');

Question 28
Dans l'enregistrement donné, chaque chaîne de caractères est précédée d'un octet indiquant le nombre effectif de caractères dans la chaîne. Comme l'enregistrement contient trois chaînes de caractères, chaque chaîne sera précédée d'un octet supplémentaire.
La taille totale de l'enregistrement est donc :
Taille de la première chaîne ('lcusici an- rd') + Taille de la deuxième chaîne ('Fr.re b huey ca ari') + Taille de la troisième chaîne ('oineoj uJ et') + 3 (pour les octets indiquant la longueur de chaque chaîne).
En supposant que la taille de chaque chaîne est la somme des caractères ASCII (8 bits) plus 1 (pour l'octet indiquant la longueur), la taille totale en octets serait :
scss
Copy code
= (15 + 1) + (17 + 1) + (12 + 1) + 3
= 16 + 18 + 13 + 3
= 50 octets

Question 29
La taille minimale d'un enregistrement de la relation Characters dépend de la taille minimale de chaque attribut. En supposant que les attributs CharID, CharName, Abbrev et WorkID ont tous une taille minimale (par exemple, une chaîne vide), et que SpeechCount est initialisé à 0, alors la taille minimale d'un enregistrement est la somme de la taille minimale de chaque attribut.
Taille minimale d'un enregistrement = Taille(CharID) + Taille(CharName) + Taille(Abbrev) + Taille(WorkID) + Taille(SpeechCount)
Pour la taille maximale, elle dépend des valeurs maximales que chaque attribut peut prendre. Sans plus d'informations sur les contraintes et les types de données, il est difficile de déterminer une valeur précise.
Question 30
Pour calculer le nombre maximal d'enregistrements de taille maximale par bloc, nous devons d'abord déterminer la taille maximale d'un enregistrement. Ensuite, nous divisons la taille maximale d'un bloc par la taille maximale d'un enregistrement pour obtenir le nombre maximal d'enregistrements par bloc.
Une fois que nous avons le nombre maximal d'enregistrements par bloc, nous multiplions cela par le nombre de blocs nécessaires pour stocker tous les enregistrements de la relation Characters pour obtenir la taille maximale du fichier.
Question 31
En l'absence de structure supplémentaire, l'accès aux blocs du fichier contenant la table Characters est séquentiel. Par conséquent, le temps maximal nécessaire à la recherche d'un enregistrement particulier dans la table Characters serait le temps nécessaire pour parcourir tous les blocs jusqu'à trouver l'enregistrement recherché.
Question 32
Dans la table d'index associée à la relation Characters, l'attribut à utiliser pour représenter l'identifiant unique de l'enregistrement est CharID. La relation d'ordre adaptée est l'ordre croissant des valeurs de CharID.
La taille maximale de la table d'index peut être estimée en multipliant le nombre d'enregistrements de la relation Characters par la taille en octets d'un identifiant unique et un numéro de bloc, puis en divisant par la taille d'un bloc.
Question 33
Avantages d'utiliser un index sous forme de table :
La recherche peut être plus rapide pour les clés uniques.
Simple à comprendre et à mettre en œuvre.
Inconvénients :
La mise à jour de l'index peut entraîner des surcoûts de performance, surtout pour les opérations de suppression et d'insertion.
Peut occuper plus d'espace mémoire.
Question 34
La construction d'un B-tree d'ordre 3 et de hauteur 4 pour l'index de la clé CharID permet de maintenir une structure efficace pour l'indexation. Chaque nœud interne contiendra au maximum 2 clés et 3 liens vers des enfants, et chaque feuille contiendra au maximum 2 paires (clé, numéro de bloc).
L'intérêt de la structure d'index sous forme de B-tree par rapport à la structure en table est qu'elle permet une recherche plus efficace grâce à une complexité de recherche logarithmique, ce qui est généralement plus rapide que la recherche séquentielle sur une table. De plus, les B-trees sont dynamiques et s'adaptent aux insertions et suppressions d'enregistrements, tandis que la taille d'une table d'index est fixe.
Question 35
Les étapes pour répondre à la requête associée à la recherche R2 sont les suivantes :
Rechercher l'enregistrement avec CharID égal à '2musician-rj'.
Extraire la valeur de l'attribut SpeechCount de cet enregistrement.
Cela peut être fait en exécutant la requête SQL suivante :
sql
Copy code
SELECT SpeechCount FROM Characters WHERE CharID = '2musician-rj';

[VirtuaProf]

troisieme partie

Question 36
Pour traiter efficacement la requête R3, il serait judicieux d'intégrer les attributs Date et LongTitle de la relation Works dans l'index. La relation d'ordre associée à ces couples serait l'ordre croissant des valeurs de Date, suivi par l'ordre lexicographique des valeurs de LongTitle.
Question 37
Pour parcourir séquentiellement les feuilles du B-tree tout en respectant l'ordre associé, une modification simple consiste à suivre le lien vers le premier enfant de chaque nœud interne jusqu'à atteindre une feuille. Ainsi, le parcours des feuilles du B-tree suivra l'ordre associé. Cette modification garantit que les feuilles seront parcourues dans l'ordre croissant des clés.
Question 38
Les étapes pour réaliser la requête R3 sont les suivantes :
Parcourir l'index associé à la relation Works en utilisant la clé de recherche appropriée (par exemple, la plage de dates entre 1589 et 1600).
Pour chaque enregistrement de l'index correspondant à la plage de dates spécifiée, extraire le LongTitle de la relation Works.
Question 39
Pour réaliser efficacement les parcours d'index et de table associés à la requête R4, un index sur l'attribut CharName de la relation Characters serait approprié. Cet index permettrait de rapidement identifier les enregistrements contenant des musiciens ou des musiciennes.
Question 40
Les critères à privilégier pour associer un attribut de table à un index sont principalement la fréquence et le type des requêtes qui utilisent cet attribut dans les clauses WHERE. Il est également important de considérer l'impact sur les performances globales de la base de données, notamment en termes de temps de réponse et d'utilisation des ressources.
Il faut éviter de maintenir trop d'index différents pour une table donnée car cela peut entraîner une surcharge de stockage et de maintenance. De plus, chaque index supplémentaire peut ralentir les opérations de modification (insertion, mise à jour, suppression) car ils doivent être mis à jour à chaque fois que la table de base est modifiée.
Question 41
Le temps maximal pour la recherche d'un enregistrement particulier dans T, sans mécanisme d'indexation, serait le temps nécessaire pour parcourir tous les blocs de la table jusqu'à trouver l'enregistrement recherché. Étant donné qu'il n'y a pas de structure d'indexation, une recherche séquentielle sur tous les blocs serait nécessaire.
Question 42
Parmi les deux arbres possibles, le B-tree d'ordre 6 et de hauteur 6 serait plus adapté s'il tient en mémoire RAM. Cela est dû au fait qu'il offre un meilleur équilibre entre la hauteur de l'arbre et le nombre maximal de clés dans chaque nœud, ce qui peut réduire le nombre total de recherches nécessaires pour localiser une clé spécifique.


Voilà, ca m’a pris 10 minutes, certaines réponses sont fausses, d’autres non exploitables, mais je suis certain que j’aurais été admis si j’avais pu utiliser chatgpt. La sélection des apprenants se fait donc sur une méthode non agile.


Le sujet scanné :

Épreuve disciplinaire

Préliminaires
Notes de programmation Python
Il est demandé d’accompagner les programmes Python d’explications de conception rédigées. Vous disposez, pour répondre aux questions de ce sujet, des fonctions de listes suivantes :
— création d’une liste li de taille ri dont tous les éléments ont pour valeur r : 1i = fvd ::n.
— renvoi de la taille d’une liste l i : len(li).
— insertion (avec décalage à droite) à un indice i dans une liste l i : l i . insert (i , v).
— ajout de la valeur u en fin de liste : l i . append (v).
— position du premier élément de la liste ëgal à r (en comptant à partir de 0) : li . index (v).
— énumération des éléments d’une liste, dans l’ordre : for x in 1i.
construction de listes par compréhension : [x**2 for x in li) est une nouvelle liste construite en mettant au carré chaque élément de la liste li.
les fonctions permettant de sélectionner des tranches (sficrs) : li fstart :ends sélectionne la sous- liste d’indices de start à end- 1.
Il est autorisé d’utiliser l’évaluation gauche droite paresseuse des expressions booléennes, par exemple, si l’expression expr_boo11 s’ëvalue à False, alors l’expression expr_boo11 and f (42) est directement évaluée à False (sans appel de la fonction f).
Enfin, on utilise la possibilité en Python des versions supérieures à 3.10 de décrire les types des pa- ramètres et de retour de fonction, par exemple : f oo (a: int , b : int) -/bool est une fonction nommée f oo, à deux paramètres entiers, retournant un Booléen.

"fotes de complexité
La complexité d’un algorithme est le nombre d’opérations ëlëmentaires réalisées par celui-ci et calculée en fonction des données d’entrées, et selon le contexte (à rappeler), exprimée dans le meilleur cas, le pire cas, ou en moyenne. Cette complexité sera dans tout ce sujet exprimée à l’aide de l’opérateur 9, dont on rappelle la définition ici : on dit que = O(g) s’il existe une constante K et une constante U telle que pour tout tt > M, /(rt) Kg(ri).
On rappelle que les listes Python sont en fait des tableaux redimensionnables. En conséquence, le
calcul de la taille, l’accès à un élément et l’ajout en fin de liste sont considérés comme des opérations i•lémentaires, avec une complexité O (1). L’insertion et le parcours sont des opérations linéaires en la aille de la liste.

Vocabulaire d’arbres
Dans ce sujet
— les arbres sont des graphes acycliques connectés, enracinés et ëtiquetës;
— un nœud sans enfant est dénommé feuille;
— on appelle la longueur d’un chemin le nombre de nœuds de ce chemin, extrémités inclues ;
on appelle arité d’un nœud le nombre d’enfants de ce nœud ; par extension on appelle aritë d’un arbre le maximum de l’arité de ses nœuds. Un arbre binaire est d’aritë 2.
— on appelle distance entre deux nœuds A et B la valeur f — 1, où l désigne la longueur du chemin
A, B) ;
on appelle niveau d’un nœud d’un arbre la distance de ce nœud à la racine de l’arbre (la racine d’un arbre est de niveau 0) ;
— la hauteur d’un arbre est la longueur du plus grand chemin de la racine à une feuille (en nombre de nœuds) ;
un arbre est équilibré si tous les chemins de la racine aux feuilles ont la même longueur ;

Rappel mathématique



Pour x 1


:=o—i

i=0



x' ——


1 — x"
l — x


1 Arbres Binaires de Recherche
Un arbre binaire de recherche est un arbre binaire (i.e. chaque nœud possède 0, 1 ou 2 enfants), dans lequel les nœuds sont étiquetés par des entiers naturels appelés clefs. De plus, si l'on considère an nœud de clef #, alors chaque nœud de son sous-arbre gauche (resp. droit) a une clef inférieure ou î•gale à k (resp. supérieure ou ëgale). Un exemple de tel arbre est donné à la Figure 1.












FIGURE 1 — Un arbre binaire de recherche

Nous proposons la définition suivante pour les arbres binaires en Python : tout d’abord, nous iéfinissons un type Noeud sous forme d’une classe (un nœud a forcément deux enfants, qui sont soit les nœuds, soit None)
:lass Noeud:













deb init (self, clef:int, gauche= None, droite= None): self.gauche = gauche
self droite = droite self.clef = clef
Par la suite, un arbre binaire est soit l’arbre vide (None) soit enraciné sur un nœud (Noeud).
L’arbre de la Figure 1 peut donc être construit de la façon suivante
mon_arbre - Noeud(42, Noeud(-15, Noeud(-6000), Noeud(12)), Noeud(177, Noeud(T0), None));
À ce stade, rien ne permet de s’assurer que l’arbre construit est un arbre binaire de recherche.
Question #1
Écrire une fonction récursive en Python de recherche d’une clef dans un arbre binaire de recherche (contenant au moins un nœud). Cette fonction aura la signature suivante
re cherche (ro ou : Noeud , k : int) - bool
Question #2
Donner la complexité algorithmique de votre fonction en fonction du nombre de nœuds de l’arbre binaire de recherche. On distinguera des cas selon la forme des arbres en entrëe.
Question #3
En utilisant un parcours récursif, écrire une fonction collecte qui collecte et ajoute dans une liste Python les valeurs des clefs des nœuds d’un arbre binaire de recherche par ordre croissant, et renvoie cette liste. On pourra utiliser la concatënation de listes et l’ajout en fin de liste (avec append) sans se préoccuper de la complexité.

Question #4
Nous proposons l’algorithme suivant pour dëterminer si un arbre binaire est un arbre binaire de
recherche
‹ def est_ABR_1(self):













s temp = True
val sell.cleï
› iI sell.gauche is not None:
, temp = self.gauche.clef < val and sell.Øauche.est_ABR_1()
, if self droite is not None:
, temp = temp and sell.droite.clef > val md self.droite.est_ABR 1()
return temp
En exhibant un arbre (non feuille) bien choisi, montrer que cet algorithme est incorrect.
Yous désirons maintenant proposer un algorithme correct : celui-ci est base sur l’invariant structurel
›uivant : lorsque l’on observe un sous-arbre (d’un arbre binaire de recherche) enracinë en un nœud de clef k
Dans le sous-arbre de gauche, le maximum des clefs est infërieur ou ëgal à k.
— Dans le sous-arbre de droite, le minimum des clefs est supërieur ou égal à ś.
your simplifier, il est supposó que l’on connait une borne inférieure (inf:=INF) et une borne supé- ieure (sup=SUP) des valeurs des clefs de l’arbre. L’algorithme consiste alors à propager un intervalle initialement ógal ă (ink , sup) ) de la racine vers les feuilles à chaque appel rócursif du parcours.
Question #5
Recopier sur votre copie l’arbre de la Figure 1 en indiquant à cóté de chaque mud les intervalles propagés par l’algorithme décrit ci-dessus.
Question #6
Sur votre contre-exemple de la question 4, comment cet algorithme va-t-il dëcider que ce n’est pas un arbre binaire de recherche ?
Question #7
Implémenter la fonction est_ABR_2_aux (sell , inf : int; , sup: int;) ->boo1 qui propage les inter-
valles de haut en bas et dëcide si l’arbre binaire courant est un arbre binaire de recherche.


ł B-trees
your une premiëre définition, nous nous reportons ă Wikipëdia
« En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B- tree ») est une structure de données en arbre ëquilibré. Les arbres B sont principalement mis en œuvre dans les mëcanismes de gestion de bases de donnëes et de systëmes de fichiers. Ils stockent les donnëes sous une forme triee et permettent une exëcution des opërations d'insertion et de suppression en temps toujours logarithmique.
Le principe est de permettre aux muds parents de posséder plus de deux muds en- fants c’est une gónóralisation de la notion d’arbre binaire de recherche. Ce principe minimise la taille de l’arbre et rëduit le nombre d’opérations d’équilibrage. De plus un B-tree grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît ă partir des feuilles. »
Dans cette partie nous allons tout d’abord implëmenter ces B-trees et en caractériser certaines
opérations.

2.1 Définition, algorithmes élémentaires
Contrairement à la section précédente, les B-trees ne seront pas binaires, mais d’arité quelconque. De Plus, les nœuds ne contiennent pas une clef unique, mais un ensemble de clefs.

Définition
En B-tree d’ordre f (cf. Figure 2) est un arbre qui satisfait les propriétés suivantes
— (S1) Tous les chemins de la racine à une feuille ont la même longueur (le même nombre de nœuds), appelée hauteur de l’arbre et dënotée par h.
— (S2) La racine est une feuille ou bien a au moins 2 enfants.
(S3) Chaque nœud qui n’est ni racine ni feuille possède au moins i -t- 1 enfants. (S4) Chaque nœud a au plus 2f -t- 1 enfants.
(CI) Les nœuds contiennent des clefs : la racine contient de 1 à 2f clefs; et les autres nœuds, entre
f et 2f clefs.
(C2) Dans chaque nœud, les ëlëments sont stockés par ordre croissant.
(C3) Chaque nœud qui contient é clefs (et qui n’est pas une feuille) a é + 1 enfants.
—










(C4) Considérons un nœud P contenant é clefs x0 .. . xt 1. Soient P0, . .. Ph S es enfants, et K(Pi)0ç,yt l’ensemble des clefs du sous-arbre dont la racine est P,. Alors
.es propriétés sont de deux ordres : quatre propriétés structurelles, prëfixées par « S », et des proprié- és de contenu/de clefs, préfixées par « C ». Remarquons que la propriété C4 est une généralisation de a propriété fondamentale des arbres binaires de recherche.












'IGURE 2 — Un exemple de B-tree d’ordre 2. Les nœuds contiennent un ensemble de clefs, triées par
›rdre croissant.

Question #8
Les arbres de la Figure 3 sont-ils des B-trees d’ordre 2?



(a) Arbre 1 (b) Arbre 2

FIGURE 3 — Quelques arbres.

(c) Arbre 3



.’implémentation du type B-tree en Python est fournie ci-dessous :
class BTreeNode:
def init (self, t:int, f-False):
self . Ieui lle — I # trues i I e no end e s! one jer'i I I e sell . clef s = I) # £ es un I ears des c I eds dv to evd
self . enf ant s = fd I I ec en f an! s dv noeud (qu i s o n L d es B / ree J o deg self . ordre = t; #1 ° o rdre dv to end
sell . n = 0 noinb ce de c I eds dv no end

class BTree:
def init (self, t):
self.root = BTreeNode(t,True) self ordre = t # l’ordre du bÉree

Ainsi l’appel BTree (2) renvoie une instance de la classe BTree d’ordre 2 représentant une feuille sans clef ni enfant. Remarquons en particulier que :
— Rien ne garantit les invariants de la définition d’un B-tree. Il faut donc bien faire attention à les maintenir.
La numérotation des enfants et celle des clefs commencent à 0.
’ar commodité, toutes les fonctions écrites seront des méthodes de la classe BTree.
Question #9
Écrire une fonction récursive d’impression d’un B-tree, del print_node (self , niveau=0) , qui af- fiche chacun des nœuds du BTreeNode courant, à partir du nœud x . Chaque nœud sera affiché sur une nouvelle ligne, avec le nombre de clefs qu’il contient, ainsi que les valeurs de ces clefs. Ainsi, sur l’exemple de la Figure 2, l’appel B . root . print_node () doit donner l’impression suivante :

Niveau
0
2:2 5
Niveau
1
2:0 1
Niveau
1
2:3 4
Niveau
1
4:6 7 8 9

[VirtuaProf]

et la fin




!.2 Recherche dans un B-tree
.a recherche d’une clef dans un B-tree va suivre le même motif que pour un arbre binaire de recherche
!n effet, elle va combiner deux algorithmes : la recherche dans une liste triée (keys) et la recherche
›armi les enfants (child) d’un nœud donné.












FIGURE 4 — Exemple de B-tree (d’ordre 2) pour la recherche

Question #10
Dans le B-tree de la figure 4, expliquer les étapes de recherche de la clef dont la valeur est 8. Utiliser les caractéristiques du B-tree pour ne pas réaliser un parcours entier de l’arbre.
Question #11
En déduire, pour un nœud fixé, une condition d’arrêt de la recherche dans ce nœud ainsi que le numéro du sous-arbre dans lequel rechercher récursivement.
Question #12
Implémenter en Python recher che_c let ( se Cf : BTreeNode , k int;) - bool cherchant la clef
k dans l’arbre courant à partir du nœud courant.

'tudions maintenant la complexité algorithmique de la recherche. Considérons des B-trees non vides, l’ordre f > 1, de hauteur lt 1. Dans un premier temps, nous allons compter le nombre de nœuds
minimum N u et maximum Np„ d’un tel B-tree. Il est recommandé de procéder en comptant les nœuds par niveau.
Question #13
Montrer que N „p —— 1 2 ((f + 1)h * 1 — 1) pour h p/ 2.

Question #14
Montrer que Nwaz 2 ((2 -t- 1) — 1) pour h p+ 1.
Question #15
En déduire un encadrement du nombre de clefs contenues dans un B-tree d’ordre / et de hauteur

Question #16
Expliquer rapidement comment optimiser le coùt de la recherche dans un nœud. Quelle est la complexité de cet algorithme ?
Question #17
Conclure sur la complexité algorithmique de la recherche dans un B-tree en fonction du nombre de nœuds n.

'.3 Insertion dans un B-tree
.’algorithme d’insertion d’une clef dans un B-tree réalise des ëtapes similaires à celui de l’insertion fans un arbre binaire de recherche : l’arbre est parcouru récursivement à partir de la racine, jusqu’à rouver une feuille dans laquelle insérer l’élément. L’insertion se réalise donc dans une feuille. Les J-trees ont néanmoins une contrainte supplémentaire : un nombre minimum et un nombre maximum le clefs pour les nœuds. Avant d’insérer une clef dans un nœud, il faudra s’assurer qu’un nœud « n’est cas complet » (au sens où le nombre maximum de clefs par nœud n’est pas atteint).
Question #18
Expliquer comment insérer la clef 23 dans le B-tree de la Figure 4.
Question #19
Implémenter une fonction insert i on_pos ii; ion (self : BTreeNode- , k int) -> int qui, ap-

pelée sur un BTreeNode, calcule l’indice auquel il faudrait insérer la clé t dans la liste self , clef s (en respectant le critère C4 et en supposant que la liste seth . clefs ne soit pas dëjà trop pleine).
Question #20
En utilisant la fonction précédente, ëcrire la fonction insert ion_non_complet (self : BTreeNode , qui réalise l’insertion d’une clef t dans un BTreeNode, dans le cas où celui-ci n’est pas complet.
Question #21
Donner la condition en Python qui permet de déterminer qu’un nœud x est complet.
dans le cas où l’endroit d’insertion est complet, le nœud va être « scindé en deux » (spfif), afin de écupérer deux nœuds de tailles plus petites. La Figure 5 explique le processus. On considère un 1-tree d’ordre i = 2 et un sous-arbre enraciné en x, dont l’un des enfants y, doit être scindé, car il 'ontient trop de clefs (ici 5 clefs). Le nœud y est donc scindë en deux nœtids y et z de taille ëgale à ' et les sous-arbres associés sont « distribués » en conséquence. L’élément « en trop », ici 8, est alors
:'jecté, pour être insërë par la suite dans l’ensemble des clefs du nœud parent, z (qui lui même peut
!tre complet, comme nous le verrons par la suite).
Question #22
Écrire la méthode def spl it (self BTreeNode) -> (int , BTreeNode) d’un BTreeNode dont le nombre de clefs est supposé (temporairement) ëgal à 2f + 1. La méthode actualise le nœud y et renvoie la valeur « ëjectée » (8 dans la Figure 5), ainsi que le nouveau nœud créë (z dans la Figure 5). Cette procédure, non récursive, ne réalise pas l"insertion dans le nœud parent. Il est fortement recommandé d’utiliser les sJices (« tranches ») Python.
.a procédure d’insertion récursive peut réaliser de multiples scindages, si la valeur éjectëe d’un nœud loit être insërëe dans un nœud déjà complet. Le résultat final de la procédure d’insertion est donc
›ossiblement un B-tree trës différent du B-tree initial. Ainsi, l’insertion de la clé 9 dans le B-tree de la 'igure 4 a pour résultat le B-tree de la Figure 6.
Question #23
Que se passe-t-il lors de l’insertion si la racine est complète ?



k:int)













x
'IGURE 5 — Illustration (partielle) de l’insertion de 8 dans le nœud y avec « split » : lors de l'insertion, e nœud y possède temporairement 5 clefs, ce qui n’est pas permis pour un B-tree d’ordre 2. La
›rocödure de découpage (“split”) va donc créer le nouveau nœud z et éjecter la valeur 8. Cette valeur
.era retournée au parent à la fin de l’appel récursif d’insertion.








FIGURE 6 — B-tree résultant de l’insertion de la clef 9 dans le B-tree de la Figure 4 a méthode d’insertion au niveau BTree est fournie ci-dessous.
del insert(self, k): # Fers$om bottom-up de I’(naertion dons un Btree
val, newnode = self.root.insert(k) if newnode is not None:
self.root sell.root.make_new_root(val, newnode)
Question #24
Implémenter la méthode nake_neu_root qui traite le cas de la racine complète.
Question #25
Terminer l’implémentation de l’insertion en implémentant la méthode insert de la classe BTreeNode.



l Application : Indexation dans les Bases de Données
dans cette partie, nous allons étudier une application des B-trees, le stockage persiStDllt des tables dans in système de gestion de bases de données (SGBD). En effet, les données des tables sont stockées dans les fichiers, pour pouvoir traiter leur potentiel grand volume et les sauvegarder dans le temps. Ces ichiers sont supposés stockés sur un disque dur local.
Jne grande partie de la littérature des bases de données est consacrée à l’étude et à la conception de tructures de données performantes pour le stockage et le requêtage efficace de ces données. Le but Principal est de limiter la quantité de donnees lues sur le support persistant.
dans cette partie, nous considérons à titre d’exemple, une base de données de taille moyenne, conte- nant des informations sur l’oeuvre de Shakespeare (https://www.opensourceshakespeare.org).

.1 Schéma relationnel et requêtes










.a Figure 7 donne un aperçu de deux des relations de la base de données précitée, avec des exemples

Characters (Personnages)
CharID
CharName
Abbrev
WorkID
SpeechCount
’lcitizen’
’First Citizen’
’1-C’
’romeojuliet’
3
’lmusician-oth’
’First Musician’
’FM’
’othello’
5
’lmusician-rj’
’First Musician’
’FM’
’romeojuliet’
10
’2gentleman-oth’
’Second Gentleman’
’SG’
’othello’
5
’2musician-rj’
’Second Musician’
’SM’
’romeojuliet’
3

Works (Œuvres)
WorkID
Title ,
LongTitle
Date
’othello’
’Othello’
’The Tragedy of Othello, Moor of Venice’
1604
’hamlet’
’Hamlet’
’The Tragedy of Hamlet, Prince of Denmark’
1600
’romeojuliet’
’Romeo and Juliet’
’The Tragedy of Romeo and Juliet’
1594

FIGURE 7 — Extrait de la Base de Données Open Shakespeare (simplifiée en deux tables).

Question #26
Dans la relation Characters, que signifie le fait que Char ID est une clef primaire ? HorkID est-il
une clef étrangère pour la relation Characters ?

En souhaite effectuer plusieurs recherches dans la base de données. Les recherches sont décrites comme suit, et sont dësignëes par une étiquette R1, R2, R3, R4.
RI : Rechercher toutes les informations décrites dans la table ’Characters’, concernant le personnage désigné par l’identifiant ’2musician-rj’.
R2 : Rechercher le nombre de mots prononcés (attribut SpeechCount) par le personnage dësignë par l’identifiant ’2musician-rj’.
R3 : Lister tous les titres longs des oeuvres de Shakespeare écrites entre 1589 et 1600.
R4 : Lister l’ensemble des titres longs des oeuvres où apparaissent des musicierines ou des musiciens (dont l’attribut CharNane contient Mosician).
dans la suite, les recherches seront dësignëes par leur étiquette. Question #27
Exprimer chacune des recherches (R1, R2, R3 et R4) sous forme d’une requête SQL distincte; chaque requête est indépendante des autres.


i.2 Stockage des enregistrements
tous considérons par la suite que le type ’char’ est stocké sur 8 bits (1 octet), et le type ‘mediumint’ st stocké sur 3 octets. Chaque enregistrement est stocké comme la suite des informations des attributs le cet enregistrement.
.e stockage des données sur disque dur se fait par filons de 4096 octets. Chaque bloc comprend une 'ntête de 200 octets. Les enregistrements de la relation Characters sont stockés dans un fichier, dont a taille est un multiple de 4096 octets (blocs).
.a relation Characters comporte 1264 enregistrements et la table correspondante est créée en SQL par a commande suivante
CREATE TABLE IF NOT EXISTS ’Characters' ( ’CharID’ varchar(50) NOT NULL DEFAULT ,
'CharName’ varchar(75) NOT NULL DEFAULT , ’Abbrev' varchar(10) NOT NULL DEFAULT , ’WorkID’ varchar(50) NOT NULL DEFAULT ",
’SpeechCount’ mediumint unsigned NOT NULL DEFAULT 0,
PRIMARY KEY ('CharID')
) DEFAULT CHARSET=latin1;

Question #28
Dans un enregistrement, les champs décrivant des chaînes de caractères sont munis d’un premier octet donnant le nombre effectif de caractères de la chaine, sans sentinelle de fin de chaine. Donner
la taille, en octets, de l’enregistrement ( ' lcusici an- rd ' , 'Fr.re b huey ca ari , ' f r' ’ , ' oineoj uJ et ' , 10).
Question #29
Donner la taille minimale SiZEpi, et maximale SIZEzz z d’un enregistrement de la relation Characters.
Question #30
Calculer le nombre maximal d’enregistrements de taille SIZEmax par bloc. En déduire la taille maximale (en octets) du fichier stockant la relation Characters.


i.3 Recherche dans une table
tous nous intëressons maintenant à la complexité d’une opération de sélection simple sur la table "haracters, qui serait par exemple réalisée lors de l’exécution de la commande SQL associée à la echerche R1.
tous supposons que la base de données est implantée sur un disque dur magnétique et que le temps noyen d’accès à un bloc sur disque est 15 ms ; une fois le bloc chargé en mémoire, la recherche à ’intérieur du bloc est réalisée séquentiellement, et le temps d’accès à l’enregistrement au sein d’un bloc est jugé négligeable.
Question #31
En l’absence de structure supplémentaire, l’accès aux blocs du fichier contenant la table Characters est séquentiel. Donner une estimation du temps maximal nécessaire à la recherche d’un enregis- trement particulier dans la table Characters.

ïn général, l’accès à la base de données est réalisée au travers d’un SGBD (Système de Gestion de Base le Données). Le SGBD réalise les opérations de création / modification / sauvegarde / requötage sur les éléments de la base de données. En particulier, il maintient un systeme d’indexation qui permet l’améliorer les temps d’accès aux enregistrements des tables de la base.
.’indexation consiste à maintenir, dans une structure dédiée, l’information minimale permettant de ocaliser chaque enregistrement de façon efficace. Chaque enregistrement est décrit par un couple identifiant unique de l’enregistrement, numéro de bloc dans lequel l’enregistrement est créé). Cette
.tructure est maintenue cohérente par le SGBD lors de la création ou de la destruction d’un enregis- rement dans une table.
jette structure d’indexation peut être réalisée au travers de tables d’index. Une table d’index associée i une relation stocke les couples (identifiant unique, numöro de bloc) de la table décrivant la relation ; es couples sont rangés par identifiant croissant. On suppose qu’un numöro de bloc est stocké sur 8
›ctets.
Question #32
On considère la relation Characters. Indiquer le champ à utiliser pour représenter l’identifiant unique de l’enregistrement dans la table d’index, et la relation d’ordre adaptée. Déterminer une évaluation de la taille maximale de la table d’index associée à la table Characters, (en nombre d’octets et en nombre de blocs).
Question #33
Donner les avantages et inconvénients d’utiliser un index sous forme de table lors des opérations d’insertion, de suppression ou de recherche d’un enregistrement d’une table représentant une relation de la base de données.
lue autre implémentation de la structure d’indexation est basëe sur les B-trees vus précédemment,
avec la variante suivante
Seules les feuilles contiennent des couples (clef/ numéro de bloc) : les clefs seront les identifiants
— Les nœuds qui ne sont pas des feuilles ne contiennent que des clefs (et un lien vers leurs enfants). Ces clefs sont des recopies de certaines clefs apparaissant dans les feuilles ; elles servent de balises lors des parcours du B-tree, afin d’orienter la recherche vers le sous-arbre adéquat.

Question #34
Montrer qu’un B-tree d’ordre 3 et de hauteur 4 suffit à permettre la construction d’un index pour la clé char ID pour la table Characters. En considérant qu’une adresse (de bloc) est stockée sur 8 octets, et en ignorant la place prise par le chaînage parent-enfant, donner une évaluation de la place en mémoire prise par ce B-tree. Expliquer l’intérêt de la structure d’index sous forme de B-tree par rapport à la structure en table.
Question #35
Quelles sont les étapes à effectuer pour répondre à la requête associée à la recherche R2 ?

En souhaite réaliser un parcours efficace des index et tables lors de la recherche R3. Pour ce faire, on cherche à construire un index relatif à la table Works, permettant un parcours séquentiel des enregis- sements de cette table, selon un index combinant différents attributs de la relation Works.
Question #36
Quel couple d’attributs de la relation Works faut-il intégrer dans l’index et quelle est la relation d’ ordre associée à ces couples pour traiter efficacement la requête R3 ?
Question #37
Quelle modification simple apporteriez-vous au B-tree correspondant à l’indexation des enregistre- ments de la relation ' Works ' afin de parcourir séquentiellement les feuilles du B-tree, en respectant l’ordre associé ?
En suppose que des structures d’index en B-tree ont étë construites, pour les deux tables ' Characters '
•t ' Works ', en intégrant la modification de la question précédente.

[VirtuaProf]

et la fin

Question #38
Quelles sont les étapes à effectuer pour réaliser la requête R3 ?
Question #39
Quel index pourrait être proposé pour réaliser efficacement les parcours d’index et de table asso- ciés à la requête R4 ?
Question #40
Quels sont les critères à privilégier pour associer un attribut de table à un index ? Pourquoi faut-il ëviter de maintenir trop d’index différents pour une table donnée ?

Dn suppose maintenant que l’on travaille sur une base de données bien plus grande. Elle comprend rue table T de 4,2 millions d’enregistrements, stockés sur 300 000 blocs.
Question #41
Déterminer dans ce cas, le temps maximal pour la recherche d’un enregistrement particulier dans T lorsqu’il n’y a pas de mécanisme d'indexation.
En cherche à construire une structure d’index en B-tree pour optimiser les accës à T. Différents arbres
›ont possibles
1. Un B-tree d’ordre 3 et de taille 8 et
2. Un B-tree d'ordre 6 et de hauteur 6 permettent de stocker l’index de T.
Question #42
On suppose que chacun des deux arbres tient en mémoire RAM. Parmi ces deux arbres, quelle est la structure la plus adaptée et pourquoi?

merci