132
Introduction pratique aux bases de données relationnelles
minimiser le nombre d'accès aux unités de mémoire externe lors des
opérations de lecture ou d'écriture de données dans les tables.
Choix de la
structure
arborescente
Les structures arborescentes conviennent au stockage des clés
d'accès ou des enregistrements de données. Lorsque le volume de
données devient important, nous associons les nœuds (le nœud racine
et les nœuds intermédiaires) et les feuilles d'un arbre non plus à des
clés ou des enregistrements de données, mais à des pages de données
entières (data pages, en anglais). Il faut ensuite parcourir l'arbre en
question pour localiser un enregistrement de données recherché.
Choix de l’arbre
binaire
Pour la gestion des données en mémoire centrale, nous
construisons normalement des arbres binaires dans lesquels le nœud
racine et chaque nœud intermédiaire se scinde en deux sous-arbres.
Ce type d'arbres ne peut pas être appliqué tel quel aux grandes bases
de données pour stocker des clés d'accès ou des enregistrements de
données. La profondeur de l'arbre binaire augmente particulièrement
vite s'il faut stocker des tables volumineuses. Or, les arbres de grande
taille sont inefficaces pour chercher et lire des tables stockées sur des
unités de mémoire externe, car ils demandent un nombre d'accès aux
pages important.
Comment réduire
les accès ?
La hauteur (ou la profondeur) d'un arbre qui mesure la distance
entre le nœud racine et les feuilles détermine le nombre d'accès aux
unités de mémoire externe. Pour réduire le plus possible la fréquence
des accès externes dans un système de bases de données, nous
cherchons à construire des structures de stockage arborescentes qui
vont croître en largeur plutôt qu'en profondeur. Une importante
structure arborescente de cette catégorie s'appelle arbre multiple, dit
aussi arbre B (arbre équilibré) (Figure 4-11).
Un arbre multiple
comporte plus de
deux sous-arbres
Dans un arbre multiple, le nombre de sous-arbres partant du
nœud racine ou d'un nœud intermédiaire est généralement supérieur à
deux. Les pages de données associées aux nœuds intermédiaires ou
aux feuilles ne doivent pas rester vides. Il faut autant que possible les
remplir de valeurs d'une clé d'accès ou d'enregistrements de données.
C'est pourquoi le taux de remplissage des pages, requis la plupart du
temps, est d'au moins 50% (à l'exception de la page associée au nœud
racine).
Introduction pratique aux bases de données relationnelles
minimiser le nombre d'accès aux unités de mémoire externe lors des
opérations de lecture ou d'écriture de données dans les tables.
Choix de la
structure
arborescente
Les structures arborescentes conviennent au stockage des clés
d'accès ou des enregistrements de données. Lorsque le volume de
données devient important, nous associons les nœuds (le nœud racine
et les nœuds intermédiaires) et les feuilles d'un arbre non plus à des
clés ou des enregistrements de données, mais à des pages de données
entières (data pages, en anglais). Il faut ensuite parcourir l'arbre en
question pour localiser un enregistrement de données recherché.
Choix de l’arbre
binaire
Pour la gestion des données en mémoire centrale, nous
construisons normalement des arbres binaires dans lesquels le nœud
racine et chaque nœud intermédiaire se scinde en deux sous-arbres.
Ce type d'arbres ne peut pas être appliqué tel quel aux grandes bases
de données pour stocker des clés d'accès ou des enregistrements de
données. La profondeur de l'arbre binaire augmente particulièrement
vite s'il faut stocker des tables volumineuses. Or, les arbres de grande
taille sont inefficaces pour chercher et lire des tables stockées sur des
unités de mémoire externe, car ils demandent un nombre d'accès aux
pages important.
Comment réduire
les accès ?
La hauteur (ou la profondeur) d'un arbre qui mesure la distance
entre le nœud racine et les feuilles détermine le nombre d'accès aux
unités de mémoire externe. Pour réduire le plus possible la fréquence
des accès externes dans un système de bases de données, nous
cherchons à construire des structures de stockage arborescentes qui
vont croître en largeur plutôt qu'en profondeur. Une importante
structure arborescente de cette catégorie s'appelle arbre multiple, dit
aussi arbre B (arbre équilibré) (Figure 4-11).
Un arbre multiple
comporte plus de
deux sous-arbres
Dans un arbre multiple, le nombre de sous-arbres partant du
nœud racine ou d'un nœud intermédiaire est généralement supérieur à
deux. Les pages de données associées aux nœuds intermédiaires ou
aux feuilles ne doivent pas rester vides. Il faut autant que possible les
remplir de valeurs d'une clé d'accès ou d'enregistrements de données.
C'est pourquoi le taux de remplissage des pages, requis la plupart du
temps, est d'au moins 50% (à l'exception de la page associée au nœud
racine).