Organisation séquentielle indexée
Pour les articles homonymes, voir ISAM.
L'organisation séquentielle indexée, aussi appelée ISAM (Indexed Sequential Access Method), est une manière d'organiser le contenu des fichiers de données qui permet un accès séquentiel et un accès direct aux enregistrements. Ces fichiers comportent un index qui permet l'accès direct aux enregistrements, lors d'opérations de recherche.
Cette technique a été popularisée par le service ISAM des ordinateurs IBM en 1966. Les fichiers manipulés par ce service doivent d'abord être remplis avec des données triées. Une zone de débordement sert aux ajouts ultérieurs; ils comportent plusieurs index. Des fichiers séquentiel-indexés ayant une organisation différente sont aussi parfois dénommés ISAM.
Accès séquentiel ou indexé[modifier | modifier le code]
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].
ISAMe[modifier | modifier le code]
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].
Voir aussi[modifier | modifier le code]
Notes et références[modifier | modifier le code]
- (en) Shio Kumar Singh, Database systems : concepts, design and applications, Delhi, Dorling Kindersley, , 2e éd. (ISBN 978-8-131-78891-2 et 978-8-131-76092-5, OCLC 810454464, lire en ligne)
- (en) Jae K. Shim, Information systems and technology for the noninformation systems executive : an integrated resource management guide for the 21st century, Boca Raton, St. Lucie Press, , 278 p. (ISBN 978-1-420-02565-1, OCLC 173504278, lire en ligne)
- (en) Krishna Shenai, Introduction to database and knowledge-base systems, Singapore, World Scientific Singapore, coll. « Series in computer science » (no 28), , 328 p. (ISBN 978-9-810-20619-2 et 978-9-810-20620-8, OCLC 25282788, lire en ligne)
- (en) Ph.D. Ruknet Cezzar, COBOL II essentials, Piscataway (New Jersey), Research & Education Assoc., coll. « The essencials of », (ISBN 978-0-7386-7052-2, lire en ligne)
- (en) Peter Smith, Applied data structures with C++, Sudbury, Mass., Jones and Bartlett, , 692 p. (ISBN 978-0-763-72562-4, OCLC 53138521, lire en ligne)
- (en) Betty Joan Salzberg, An Introduction to Data Base Design, Saint Louis, Elsevier Science, , 297 p. (ISBN 978-1-483-27048-7, OCLC 1041189771, lire en ligne)
