Organisation séquentielle indexée

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir ISAM.

L'organisation séquentielle indexée, aussi appelée ISAM, 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 ne comporte pas d'index. En lieu et place, 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[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 disque 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]

  1. a, b, c, d, e et f Database Systems: Concepts, Design and Applications,Pearson Education India - 2011, (ISBN 9788131760925)
  2. a, b, c et d Jae K. Shim,Information Systems and Technology for the Noninformation Systems Executive: An Integrated Resource Management Guide for the 21st Century,CRC Press - 2000, (ISBN 9781420025651)
  3. a, b, c et d S. Krishna,Introduction to Database and Knowledge-base Systems,World Scientific - 1992, (ISBN 9789810206208)
  4. a, b, c, d et e (en) Ph.D. Ruknet Cezzar, COBOL II essentials, Piscataway (New Jersey), Research & Education Assoc., coll. « The essencials of », (ISBN 9780738670522)
  5. a, b et c Peter Smith,Applied Data Structures with C++,Jones & Bartlett Learning - 2004, (ISBN 9780763725624)
  6. a et b Betty Joan Salzberg,An Introduction to Data Base Design,Academic Press - 2014, (ISBN 9781483270487)

Article connexe[modifier | modifier le code]