| ★ CODING ★ RESTAURATION DE LA MEMOIRE BASIC ★ |
| Basic - Tout sur les Fichiers (CPC Revue) |
Index - généralités Principe Un des procédés utilisés pour trouver l'adresse (le rang) d'une fiche sur disque est celui de l'index. Le Principe en est analogue à celui des index figurant à la fin de certains ouvrages :
Dans un ouvrage, on pourrait avoir :
Mais dans un index d'accès direct, on aura :
Les index dont nous parlons n'ont presque rien à voir avec les tables d'indice utilisées pour l'adressage indirect. Ces tables d indices ou de "pointeurs" qu'on appelle parfois index permettent de modifier l'ordre logique d'éléments dont on ne veut pas changer l'emplacement réel. Ces index d'adressage indirect peuvent être par exemple :
Le premier type contient des adresses RELATIVES, le second des adresses ABSOLUES. Mais revenons à nos index d'accès direct . Les index que l'on trouve à la fin des livres sont toujours triés sur la clé, car l'homme ne peut pas exploiter un fichier en désordre, sauf si ce fichier est de très faible longueur. En informatique, on peut (parfois) avoir des index non triés, mais la distinction principale se fait d'après l'emplacement de l'index en cours d'utilisation. D'après ce critère, on distingue :
Index entièrement sur disque Un index non trié serait inutilisable, la lecture séquentielle sur disque étant beaucoup trop lente. Sur un index trié, on pourra utiliser la recherche dichotomique. Nous avons dit ce qu'il faut penser de la dichotomie sur disque : méthode très valable, surtout avec de petits enregistrements, mais se heurtant à la lourdeur des aécalages entraînés par les suppressions et les additions. On sera donc amené a faire les mises à jour en TEMPS DIFFERE. On peut rendre cet index trié sur disque, très performant, de la façon suivante . Supposons que nous nous trouvions dans la situation ci-après :
Lorsqu il n'y a pas un nombre entier d'enregistrements par secteur, le rang du dernier enregistrement (même partie) du même secteur est donné par la formule :Rang = INT((N * long.Secteur) -1 )/long.elem.) + 1 Ici, nous notons les clés du 64e, 128e, etc. enregistrements (de I index), ce qui nous donne la table suivante : 64 BRUNO (fin du 1er secteur de l'index) Cette table, enregistrée sur disque lors de la mise à jour périodique, est chargée en mémoire en début de travail. Elle y occupera : 32 x (2 + (6 + 3)) soit 352 octets (dérisoire !) Si nous cherchons un nommé DENIS., la lecture dichotomique ou séquentielle de cette table nous montre qu'il convient de lancer une recherche dichotomique dans l'index sur disque avec les bornes externes suivantes : Basse = 64, Haute = 128+1 Le 1er ordre de lecture concernera l'enregistrement INDEX médian, c est-à-dire celui de rang 96. Le 2e secteur sera alors chargé "UNE FOIS POUR TOUTES" et le reste de la dichotomie se passera en mémoire. Cette méthode garantit les performances suivantes :
La lecture des homonymes se fait ensuite par lecture séquentielle de l'index. Il y aura un nouvel accès à l'index seulement lors d'un franchissement de secteur. Notons au passage que rien n'interdit de mettre index et fichier principal sur des lecteurs de disquettes séparés. On y gagnerait un peu en vitesse (optimisation des déplacements de la tête de lecture). On y perdrait probablement en temps passé à la nécessaire mise à jour de la documentation d'exploitation. Le cas ne se pose pas avec un disque dur. Comme nous l'avons dit, un index séquentiel trié sur disque se prêtera mal aux opérations de mise à jour en temps réel, même si les décalages sont plus rapides qu'avec le fichier principal, puisque les enregistrements de l'index sont plus petits. En effet, la suppression du 1er enregistrement ou bien la création d'une clé de valeur faible entraîne la réécriture de tous les secteurs index. Compte tenu de ces réserves, c'est une solution tout à fait opérationnelle, comme nous allons le voir. Un exemple d'index entièrement sur disque Nous avons tous remarqué que beaucoup de pharmacies possèdent des ordinateurs "de comptoir". Le travail de ces machines est le suivant : A - Imprimer les factures subrogatoires (imprimés jaunes en 3 exemplaires) qui permettront à la pharmacie de récupérer les sommes non payées par l'assuré social. Cet imprimé doit recevoir des informations fort diverses : Nom, adresse, n° de sécurité sociale Nom et NUMERO du médecin Caisse assurance maladie Mutuelle Régime de remboursement particulier (100 % vieillesse ou invalidité). Les médicaments vendus (prix, avec ventilation et cumul des montants remboursables et non remboursables). B - A titre accessoire, renseigner la plus grande partie de la feuille de soins (nom, adresse, n° de sécurité sociale). C - Créer un fichier Factures et un fichier Ordonnancier. L'application repose sur les fichiers DIRECTS suivants :
A la lecture de ces chiffres, qui ne tiennent pas compte de la place prise par les fichiers factures et ordonnancier, on voit qu'un disque dur est nécessaire, pour une simple question de capacité. De plus, la rapidité d'accès du disque dur le rend bien préférable aux disquettes pour l'application considérée. Les fichiers Index Il y en a un par fichier direct principal, à l'exception du fichier médicaments qui en a deux. En effet, on peut avoir à chercher un médicament soit par son nom, soit par son numéro d'identification inscrit, pour certains d'entre eux, sur l'emballage sous forme de code-barre. L'index alphabétique du fichier articles ainsi que les index des autres fichiers sont constitués d'éléments de 12 caractères (10 caractères + 2 octets pour l'adresse). Ces index sont triés sur l'ensemble de l'élément (clé en majeur, adresse en mineur). La clé de recherche comprend de 1 à 10 caractères au maximum Principes de mise à jour et d'accès La mise à jour du fichier principal est immédiate. Celle de l'index (ou des index pour les articles) est différée. Prenons la situation initiale suivante où le fichier principal est symbolisé par des "a", le fichier index par des "i".
La recherche d un assure se tait par recherche dichotomique dans l'index. Le nombre d'itérations sera au maximum : Log2 (nbre fiches) + 1Pour 8000 fiches, cela donnerait 14 itérations au maximum. Chaque fiche "Index" faisant 12 octets, chaque secteur en contient environ 42. L'index tient donc sur 190 secteurs. Au pire, il faudra log2(190) + 1 accès pour charger le secteur intéressant, soit 8 accès environ. Les 6 autres accès ne sont plus des accès disque, mais des accès en mémoire. Les performances du disque dur font que l'arrivée de l'information sur l'écran paraît, à l'opérateur humain, quasi instantanée. Ajouts au fichier Le nouveau client est identifié par la "clé" suivante : nom + 2 premières lettres du prénom (par exemple MARTINJE) Cette clé est enregistrée dans chacune des fiches du fichier principal. La fiche nouvellement saisie est écrite en fin de fichier. Nous supposerons qu'il y a déjà 3027 enregistrements.
Recherche d'une fiche non représentée à l'Index représentée La recherche est faite dans l'index avec les premières lettres du nom. Si cette recherche ne donne rien, une recherche séquentielle est lancée dans le fichier principal à partir de l'enregistrement 3028. L'argument de recherche utilisé est alors la clé "NOM + 2 lettres du prénom". Technique de mise à jour des index après ajouts En temps différé, les éléments d'index supplémentaires sont créés, triés et, par fusion avec l'ancien index, donnent un index à jour qui a, ae nouveau, le même nombre d'enregistrements que le fichier principal. Suppressions Les suppressions sont faites par marquage de l'enregistrement principal, l'index n'étant pas modifié. Quana cela devient nécessaire, une réorganisation des fichiers est faite. Sont recopiés les enregistrements principaux validés et les enregistrements index correspondants. Langage de programmation L'application, que nous avons vu tourner, a été proqrammée en BASIC compilé. Index en partie en memoire Ils sont basés sur une structure de données en ARBRE. Résident en mémoire un certain nombre de couples clé/adresse ainsi que l'adresse du "secteur" à charger lorsque la clé n'a pas été trouvée dans le secteur "racine". Leur avantage est de permettre une mise à jour en temps réel de l'index et du fichier, avec une place mémoire limitée. L'index peut croître indéfiniment, dans les limites du disque, tout au moins. Seules les performances en souffriront, car il faudra descendre plusieurs niveaux de l'arbre avant de trou-ver, pour le charger, le secteur intéressant. Nous y reviendrons, mais auparavant, nous allons parler plus en détail des index tout en mémoire. Index entièrement en memoire centrale Généralités C'est le plus simple à concevoir et à mettre en œuvre. C'est aussi le plus rapide (de très loin) si on met à part le temps nécessaire au chargement initial de l'index à partir du disque. Malheureusement, la taille de ce genre d'index est limitée par la place disponible en mémoire. Aussi, risque-t-on de se heurter aux difficultés suivantes :
En conclusion, ce genre d'index ne peut être envisagé qu'avec une mémoire confortable et des fichiers qui voudront bien rester de taille raisonnable. Avec ces restrictions, il peut être extrêmement utile. Index "CLE SEULE' Le principe en est le suivant. Partons du mini-fichier ci-après sur disque, auquel nous voulons accéder par le nom. Rang | Numéro de secu Nom Prenom Profession Rappelons que le rang, analogue à un indice, est l'endroit où est la fiche, mais ne figure pas dans la fiche elle-même. Les points figurent les espaces inutilisés (la taille de la rubrique NOM ne change pas quelle que soit la longueur de celui-ci). Le numéro de sécurité sociale ASCII prend 13 octets, mais on peut le condenser sur 6 octets comme nous le verrons. Nous lisons le fichier et ne retenant que les 6 premiers caractères de la zone NOM, nous construisons la table suivante : 1 DUPONT etc. 309 ARBOGA Notons les points suivants : 1 - La taille en mémoire de la table sera au maximum : 311 x (6 + 3) 3 étant pour le descripteur de chaîne. Ce qui fait 2799 octets. La place restant en mémoire dépend évidemment du nombre d'octets pris par le programme proprement dit et les autres données. II est possible, par un traitement particulier de condenser 3 lettres dans deux octets (un entier), et par voie de conséquence, 6 lettres dans 4 octets. Nous aurions alors un index de 311 x4 = 1244 octets seulement. Nous essayerons de reparler de cette question. 2-6 caractères sont largement suffisants en règle générale. Mais dans les grands fichiers, le nombre d'homonymes peut être très grand (il y a environ 2400 MARTIN à Paris). Dans le cas de ces grands fichiers, une clé composite sur 6 caractères pourrait être constituée par le début du nom + initiale prénom + n° dans la rue. Par exemple : MARF12 serait certainement plus efficace que : MARTIN pour trouver M. François MARTIN habitant 12, rue... 3 - On note deux homonymes dans l'index (VALMON en 2, VALMON en 311). L'index n'étant pas trié, ils n'ont aucune raison particulière d'être à côté l'un de l'autre. Utilisation d'un index "Clé seule" Le principal intérêt de cet index est son faible encombrement. En effet, l'adresse est implicite, chaque élément de l'index ayant pour rang (indice) celui de la fiche dans le fichier principal. On gagne donc deux octets par élément d'index. En l'absence de tri, la recherche ne peut être que séquentielle. La lenteur du BASIC oblige pratiquement à programmer cette recherche en langage machine. Les additions, suppressions et modifications se font très facilement : 1 - Additions On cherche le premier enregistrement vide dans l'index. Ici, il a le rang 4. On y écrit la clé. On écrit la fiche concernée au rang 4 du fichier principal. Notons qu'il est toujours sage de réutiliser en priorité les places vides de rang le plus bas. S'il n'y a pas de place récupérable, on ajoutera la fiche et sa clé en extrémité de fichier et d'index. Si la table index est pleine, il faudra sauvegarder celle-ci sur disque, puis la recharger après modification de la DIM (si c'est possible). 2 - Suppressions On efface la clé dans l'index, la fiche correspondante dans le fichier (par des zéros binaires, par exemple). 3 - Modifications Un changement de nom (par mariage, par décision parue au Journal Officiel) ne pose pas non plus de problème de décalage, les changements se faisant en parallèle dans l'index et le fichier. Les défauts de ce type d'index Les homonymes ne sont pas consécutifs, mais répartis, de façon aléatoire, sur toute la longueur de la table. Connaître leur nombre nécessite une exploration complète de celle-ci. Passer d'un homonyme au suivant implique qu'on relance la recherche alors que sur une table triée, il suffirait de faire INDICE = INDICE + 1 ou -1 suivant qu'on veut traiter la fiche suivante, ou revenir à la précédente. De plus, il va de soi que le temps d'accès DANS L'INDEX croît du début à la fin de la table. En bref, ce type d'index n'est recommandable que dans les cas suivants : — clé : indicatif (pas d'homonymes) ; — recherche : programme en langage machine. On trouvera en listing 1 le programme de validation d'une routine en langage machine (méthode de la sentinelle), pour une table d'entiers. Cette table est valorisée 1,2... N (N étant la Dim - 1). Comparée à celle du BASIC, la rapidité est saisissante.
La "médiocre" performance pour trouver la clé 1 tient au fait qu'une seule itération porte le poids (ou plutôt la durée) du lancement de la routine, passage des paramètres par l'instruction CALL etc. La clé ne va pas de -35768 à 32767. Elle est saisie dans une variable réelle entre 0 et 65536 et cette valeur convertie en entier par la fonction : DEF FN n65(n!) = n! + (n!>32767)*65536La fonction inverse étant : DEF FN n!(n65) = n65 - (n65<0)# 65336La valeur 0 de la clé correspond aux enregistrements vides. 0 n'est jamais attribué comme indicatif de fiche en cours. Numéro de sécurité sociale Le listing 2 présente une routine de recherche séquentielle analogue, mais sur le numéro de sécurité sociale. On notera que ce numéro peut être contenu dans 3 entiers, soit 6 octets au lieu de 8 avec une variable réelle double précision, ou 13 (sans compter les descripteurs de chaînes) sous forme de chaîne ASCII. Le contrôle de la saisie par NOMBRE (on dit souvent "clé") de contrôle est effectué. Cette vérification est basée sur la comparaison du nombre de contrôle et du reste de la division du numéro de sécu par 97 (plus exactement le complément à 97 de ce reste). Un point important à noter à propos de la saisie d'un numéro aussi long. Des espaces ou séparations sont indispensables sur le bordereau ae saisie. L'opérateur doit pouvoir frapper avec (cela facilite la relecture), ou sans espace./.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
