5. Tableau
5.1 Séquentiel indexé

Retour au thème fichiers

5. Tableau

ableau comparatif
 

type d'adressage	Avantages	Inconvénients
Fonctionnel (accès direct)	Les clés ne sont pas stockées, Les temps d'accès sont très rapides	Il n'est pas évident de trouver une fonction bijective permettant de relier une clé à un seul enregistrement
Associatif (accès indexé)	la bijection entre la clé et le n° de l'enregistrement est immédiate après parcours de la table	Limitations imposées par la place en mémoire centrale, Il faut un algorithme de parcours de la table

'est un cas particulier d'organisation indexée hybridée avec un parcours séquentiel.
Il y a une table d'index, mais l'ensemble des clés est ordonné et partitionné en plusieurs plages distinctes ne se recouvrant pas et ce sont ces plages de clés aui sont entrées dans la table. Chaque plage est associée à un numéro d'enregistrement unique : celui de la première clé (la borne inférieure de la plage).

Lorsque l'on entre une clé, l'algorithme consiste à chercher dans quelle plage elle se situe puis de rechercher cette plage dans la table d'index, enfin de positionner le pointeur sur l'enregistrement de départ (partie accès indexé). A partir de cet instant la recherche continue séquentiellement depuis la clé minimale jusqu'à la clé maximale.

Le schéma ci-dessous résume le fonctionnement :
 

• Kpj est la clef entrée dans la table d'index.
• Une plage Kp1 .. Kpn est trouvée contenant Kpj (Kp1 < Kpj < Kpn).
• Cette plage est associée au bloc (enregistrement) Kp1
• à partir du bloc Kp1 la recherche se fait en séquence jusqu'à Kpj.

Afin de remédier aux limitations dûes aux très grands fichiers (problème de taille de la table d'index en mémoire centrale), le séquentiel indexé partitionne la table d'index en plusieures sous-tables. Une table principale nommée table d'index principal qui permet d'accéder à un instant donné à une sous-table de taille plus petite (table d'index secondaire) qui réside en mémoire centrale. Les tables dans les bases de données sont généralement architecturées autour de cette configuration.

On partitionne l'intervalle de toutes les clefs et la table d'index principal ne contient que la borne inférieure des intervalles, une table secondaire contient toutes les clefs comprises entre deux bornes inférieures consécutives (toutes les clefs de l'intervalle) et l'on peut réitérer ce partitionnement si nécessaire.

Un exemple d'un tel partionnement (d'autres sont possibles) :