Organisation séquentielle indexée

Séquentiel-indexé est une organisation de fichier de données qui permet aussi bien d'accéder aux données l'une après l'autre - séquentiel[1], que d'accéder directement à un enregistrement dont la clé a une certaine valeur via un index - accès indexé[2]. L'index permet de rapidement localiser l'enregistrement[1].

Les trois types d'organisation des fichiers de données sont : séquentiel, indexé-séquentiel et direct[2].

• dans un fichier séquentiel les enregistrements sont stockés l'un après l'autre selon un ordre prédéfini et seront lus dans le même ordre[2].
• Dans un fichier séquentiel-indexé, les enregistrements sont stockés dans l'ordre de la clé primaire et un index renseigne sur l'emplacement de chaque enregistrement[1]. L'index permet de rapidement localiser l'enregistrement[1]. Lorsqu'il y a beaucoup de données, l'index peut atteindre une taille trop grande pour résider en mémoire centrale. Il est alors enregistré dans un fichier, et accompagné d'un index de deuxième niveau (index de l'index) qui renseigne sur l'emplacement de son contenu[3].
• un fichier direct peut avoir un index, mais, le plus souvent, l'emplacement de chaque enregistrement est déterminé par hachage: une formule de calcul transforme la valeur à rechercher en un nombre, et ce nombre est l'emplacement de l'enregistrement[2].

ISAM est le nom d'un service de manipulation de fichiers séquentiel-indexé lancé par IBM en 1966[4]^,[5]. Il était populaire dans les années 1970[3]. Les fichiers en organisation séquentielle indexée sont couramment appelés ISAM[4] - ils ont cependant souvent une organisation différente de celle de IBM et utilisent les arbres B[6].

Un fichier ISAM est divisé en trois sections : données, index et zone de débordement - pour permettre l'ajout d'enregistrements[1]. La zone de données est l'endroit où sont enregistrées les données lorsque le fichier est créé[4], le contenu initial est ajouté dans l'ordre de la clé primaire[4]. La zone de débordement sert pour les enregistrements ajoutés ultérieurement[4], l'enregistrement ajouté est accompagné de pointeur qui permet de retrouver l'enregistrement suivant dans l'ordre de la clé primaire[1].

Il y a plusieurs niveaux d'index, qui reflètent la mécanique des disques durs : un index par piste, puis chaque piste est classée dans un index de cylindre et chaque cylindre est classé dans un index maître[5]. Dans l'index maître est indiquée la valeur maximale de la clé pour chaque cylindre. Puis les indexes de chaque cylindre indiquent la valeur maximale de la clé pour chaque piste[6].

ISAM utilise deux algorithmes d'ajout de données. Tout d'abord le contenu initial est ajouté trié, puis un autre algorithme est utilisé pour les ajouts ultérieurs, contrairement aux fichiers à arbre B où les ajouts initiaux se font selon les mêmes algorithmes que les ajouts ultérieurs[5].

À mesure des ajouts, les opérations de manipulation du fichiers deviennent de plus en plus complexes et longues, raison pour laquelle les fichiers doivent être régulièrement réorganisés[3]. Les organisations de fichiers plus récentes utilisent des structures en arbre B, une structure qui se réorganise continuellement[3].

• MyISAM, l'ancien format de table dans MySQL, encore disponible dans MariaDB.