Glossaire

Fragmentation interne

Le bloc logique est la plus petite unité d'allocation visible d'un système de fichiers à travers les appels systèmes. Cela signifie que le stockage d'un fichier dont la taille en octets est inférieure à la taille d'un bloc logique occupera sur disque la taille du bloc logique.

De même, si la taille d'un fichier n'est pas divisible de façon entière par la taille du bloc logique (ie. taille_fichier modulo taille_bloc != 0), le système de fichiers allouera un nouveau bloc qui ne sera pas rempli entièrement, gaspillant ainsi de l'espace disque. Ce gaspillage d'espace disque est ce que l'on appelle la fragmentation interne. Remarquons que plus la taille du bloc logique est importante, plus importante sera la fragmentation interne.

Fragmentation externe

La fragmentation externe d'un fichier est le fait d'avoir les blocs constituant le fichier répartis de façon non contiguë sur tout le disque, réduisant ainsi les performances d'accès à ce fichier, du fait de l'augmentation des mouvements des têtes de lecture du disque nécessaire à l'accès à ce fichier.

Extent[1]

Les extents sont des ensembles de blocs logiques contigus, utilisés dans divers systèmes de fichiers voire même dans certains SGBD. Le descripteur d'un extent ressemble à début, taille, offset, où début est l'adresse du premier bloc de l'extent, taille est la taille en nombre de blocs, offset est l'offset dans le fichier où se situe l'extent.

Extent

L'utilisation des extents améliore l'utilisation de l'espace, puisque tous les blocs d'un extent sont contigus. Cette amélioration amènera de meilleures performances en lecture séquentielle, car moins de mouvements de tête de lecture seront nécessaires. Remarquons ainsi que l'utilisation des extents réduit le problème de la fragmentation externe, puisque les blocs sont rassemblés. Mais l'utilisation d'extent n'est pas toujours la panacée. Par exemple, si nos applications demandent des extents d'une taille proche de celle des blocs logiques, tous les bénéfices seront perdus, puisque ces extents ressembleront à autant de blocs logiques.

Pour clore le chapitre amélioration des performances, l'utilisation d'extents améliore aussi les transferts simultanés de plusieurs blocs et améliore les taux de réussite des mémoires tampons des disques durs.

Arbres B+

Arbre B+[2] : les clés des noeuds sont ordonnées dans l'arbre, ce qui améliore les temps de recherche, recherche qui n'est plus séquentielle. Les feuilles sont chaînées entre elles.

1. Pour localiser le fichier resolv.conf, nous commençons à la racine de l'arbre, lisons séquentiellement, et trouvons qu'il n'y a pas de clé supérieure à celle de resolv.conf, donc nous suivons le dernier pointeur (en rouge).

2. Nous sommes redirigés sur un autre noeud de l'arbre. On fait de même qu'avant, on lit les clés jusqu'à "securetty", qui est supérieure à "resolv.conf". On suit donc le lien associé (en bleu).

3. Nous arrivons ainsi à une feuille de l'arbre. Il est temps de lire séquentiellement par ordre ascendant les clés présentes. Nous trouvons enfin la clé désirée, nous permettant d'utiliser le pointeur associé vers les données du fichier "resolv.conf"

La structure de données de type arbre B+ est depuis longtemps utilisée pour l'indexation de bases de données.

Cette structure apporte aux SGBD une manière rapide et stable dans les performances pour accéder à leurs enregistrements. Le terme arbre B+ vient de «arbre balancé», équilibré en français. Le signe «+» signifie que la structure arbre B+ est une version modifiée de l'arbre B. [3] original, modification qui consiste en le maintien de pointeurs entre les différentes feuilles de l'arbre, ce afin de ne pas pénaliser les accès séquentiels de feuille en feuille. Puisque les arbres B et B+ sont issus des bases de données, nous utiliserons des analogies avec celles-ci pour les expliquer.

Les arbres B+ sont constitués de deux types d'éléments : les noeuds et les feuilles. Les deux sont une paire (clé, pointeur), ordonnées de façon ascendante par les valeurs de clés, avec un pointeur final qui n'a pas de clé correspondante. Alors que les pointeurs des noeuds pointent sur d'autres noeuds ou feuilles, les pointeurs des feuilles pointent directement sur l'information utilisable. Chaque paire (clé, pointeur) organise l'information au sein de l'arbre B. En base de données, chaque enregistrement possède un champ-clé, un champ qui sert à distinguer un enregistrement particulier des tous les autres enregistrements de même type. Les B-arbres utilisent ces champs-clés pour indexer les enregistrements d'une base de données pour améliorer les temps d'accès à l'information.

Ainsi que nous l'avons vu, un noeud (clé, pointeur) est utilisé pour pointer sur un autre noeud ou sur une feuille. Dans les deux cas, la clé associée au pointeur aura une valeur supérieure à toutes les valeurs de clés stockées dans les noeuds cibles. De plus, les enregistrements ayant des valeurs de clés identiques devront être adressés par la paire suivante dans le noeud. Ce point est la principale raison de l'existence du pointeur de fin qui n'a aucune valeur de clé correspondante. Notons qu'à partir du moment où une clé est utilisée dans une paire, il doit exister un autre pointeur pour atteindre les enregistrements ayant cette même valeur de clé. Ce pointeur de fin est utilisé dans les feuilles pour pointer sur la feuille suivante. On peut ainsi passer les contenus en revue aussi de façon séquentielle.

Les arbres B+ doivent être équilibrés. Cela signifie que la longueur du chemin nous menant de la racine de l'arbre à chacune des feuilles doit toujours être la même. En plus, les feuilles doivent contenir un nombre minimal de paires pour exister. Quand le contenu d'une feuille tombe sous le seuil, les paires seront intégrées à une autre feuille.

Pour rechercher un enregistrement particulier, nous procéderons ainsi :

Supposons que nous recherchons un enregistrement ayant une clé K. Nous partons du noeud racine, et passons en revue séquentiellement les clés qu'il contient, jusqu'à ce que nous trouvions une clé de valeur supérieure à celle de K. Nous passons ensuite au noeud (ou feuille, nous ne savons pas encore) pointé par le pointeur associé à la clé. A ce stade, nous répétons la même opération si nous ne sommes pas arrivés à une feuille. Arrivé sur une feuille, nous criblons séquentiellement les paires contenues jusqu'à la valeur K. Moins de blocs sont nécessaires d'être lus pour arriver au bloc désiré, ce qui qualifie cette technique comme étant de moindre complexité qu'une recherche purement séquentielle, où dans le plus mauvais cas, nous devons lire tous les enregistrements pour trouver celui que nous recherchons.

Unix File System (UFS)

C'est le nom du système de fichiers utilisé au début par SCO, System V[4], et d'autres Unix. Le noyau Linux inclut le support optionnel d'UFS. La plupart des Unix continuent à utiliser UFS, avec néanmoins quelques améliorations mineures.

Virtual File System (VFS)

VFS est la couche logicielle du noyau[5] qui fournit une interface de programmation applicative [API en anglais] unifiée pour accéder aux services des systèmes de fichiers, quel que soit le système de fichier particulier utilisé derrière. Tous les pilotes de systèmes de fichiers (VFAT, Ext2FS, JFS) doivent ainsi fournir un certain nombre de routines à la couche VFS pour être utilisables sous Linux. VFS est la couche qui permet aux applications de comprendre et d'utiliser tant de systèmes de fichiers différents, même les systèmes de fichiers commerciaux.

Notes