Brevet FR2047949A1 — publié le 19710319

La présents invention concerne d'une manière générale la recherche d'information et plus particulièrement une technique nouvelle à commande électronique pour effectuer une recherche dans des index à plusieurs niveaux lisibles à la machine. Les procédés et moyens fondamentaux pour la formation et la 5 recherche automatique dans des index comprimés à un seul niveau sont décrits dans les demandes de brevets français n° 6945785, 6945786, 6945787 déposées par la demanderesse en France le 30 Décembre 1969. Actuellement les informations de toute sorte sont engendrées à une vitesse sans cesse croissante. Il y a un inconvénient par le fait que l'on ne peut 10 rechercher rapidement un bloc d'information dans la masse d'information dans laquelle il est enfoui. Bien que l'on ait réalisé beaucoup de travaux sur la recherche d'information, on n'a pas trouvé jusqu'ici de solution, bien que de nombreuses techniques de recherche d'information compliquées aient été conçues pour accéder à une source d'information comprenant un grand nombre 15 de documents ou d'enregistrements. □ans le domaine de la recherche d'information, l'invention concerne un dispositif permettant de commander une machine pour localiser des documents indexés par des clés. Tout type de clé alphanumérique disposée suivant une séquence ordonnée peut être converti en une forme comprimée et recherché 20 par la présente invention. Chaque clé comprimée représente une limite (soit supérieure, soit inférieure] pour la clé non comprimée qu'elle représente. A chaque clé comprimée peuvent Stre associées des données au l'emplacement d'un ou de plusieurs blocs d'information qu'elle représente. L'information d'emplacement peut Stre une adresse, un indicateur ou peut être obtenue à 25 partir de la clé elle même par un moyen qui ne fait pas partie de la présente invention. La présente invention concerne un procédé pour effectuer une recherche dans un index comprimé à plusieurs niveaux afin d'augmenter de façon importante la vitesse dB la recherche par rapport à la vitesse de recherche dans 30 l'index non comprimé. On connaît de nombreux procédés et moyens pour effectuer une recherche dans un index non comprimé à plusieurs niveaux. La recherche dans un index non comprimé, est réalisée électroniquement avec des ordinateurs ên utilisant des procédés d'accès spéciaux, des moyens de commande et des techniques utili-35 sant des catalogues. On pourra se référer aux brevets français n° 1 412 027 déposé par la demanderesse en France le 25 Septembre 1964 et n° 1 455 173 déposé par la demanderesse en France le 25 Juin 1965 et aux brevets américains n° 3 242 470 et 3 030 609. La recherche d'information par ordinateur est limitée d'un certain nombre 40 de façons parmi lesquelles on peut fixer la très grande capacité de mémoire 7G 17710 2 2047949 nécessaire. Il résulte du format des clés non comprimées dans un index à plusieurs niveaux, que l'on doit balayer un grand nombre de multiplets dans chaque clé pour chaque argument de recherche. Cette opération prend du temps et est coûteuse lorsqu'on effectue une recherche dans un index très long, 5 ou lorsqu'on effectue une recherche de façon répétée dans un index court. C'est ce problème que résout la présente invention qui permet de réduire ' de beaucoup le nombre des multiplets balayés par entrée de cïês: dahs un index exploré. Il en résulte que la mémoire peut avoir une capacité plus petite et que la recherche est plus rapide étant donné qu'il y a moins de multiplets 10 qui doivent être détectés par la machine. Il en résulte une augmentation importante de la vitesse de recherche sans changer la vitesse de l'ordinateur. Dans les techniques actuelles de recherche par ordinateur, telles que celles décrites dans les brevets cités, il y a des clés non comprimées qui accompagnent les enregistrements sur un disque, ou un tambour pour indexer 15 l'information contenue dans l'enregistrement associé. La recherche de l'enregistrement associé peut être réalisée soit par la clé, soit par l'adresse de l'enregistrement. Par exemple dans les brevets américains n° 3 350 693, 3 343 134, 3 344 402, 3 344 403, et dans les brevets français n° 1 460 694 déposés par la demanderesse en France le 23 Septembre 1965 et 1 512 392 déposé 20 par la demanderesse en France le 22 Février 1967, une clé non comprimée peut être indexée.sur un disque d'enregistrement magnétique. Une clé dans un index à plusieurs niveaux peut être balayée électroniquement par un argument de recherche pour trouver une condition d'égalité, Lorsqu'on a trouvé la condition d'égalité, un indicateur associé à la clé non comprimée respective est obtenu 25 et utilisé pour rechercher l'enregistrement à un niveau inférieur représenté par la clé qui peut être quelque part sur le même dispositif ou un dispositif différent. Par exemple, les indicateurs peuvsnt être 1'emplacement sur le disque ou autre dispositif où est enregistré l'enregistrement suivant de niveau inférieur. Le niveau le plus bas de 1'.index localise l'enregistrement 30 des données recherchées et l'enregistrement peut être-recherché et utilisé dans n'importe quel but. • Cette invention concerne la recherche dans un index comprimé à plusieurs niveaux. La compression supprime la redondance" qui■peut être attribuée à la nature ordonnée de l'index, c'est-à-dire elle-supprime" la redondance pro-35 venant du classement et ne conserve que l'information minimum nécessaire pour la recherche. La recherche correcte dansun index comprimé à plusieurs niveaux implique des subtilités: etdes cas critiques qui n'apparaissent pas dans les index non comprimés à plusieurs niveaux. L'identification de ces caractéristiques non évidentes est essentiel pour ï-échBrcher correctement 40 un enregistrement dans le niveau suivant inférieur de l'index'avant que 70 17710 3 2047949 l'enregistrement de donnée correct puisse être recherché. Par conséquent, un objBt de cette invention est de réaliser un système qui permette d'effectuer une recherche dans un index comprimé à plusieurs niveaux en supprimant la redondance résultant du classement et qui permette 5 cependant la recherche de l'enregistrement correct dans le niveau inférieur suivant. Un autre objet de cette invention est de réaliser un système pour effectuer une recherche dans un index comprimé à plusieurs niveaux pour réduire le nombre des multiplets de l'index qui doit être balayé par la machine pendant 10 une recherche comparé au nombre dymultiplets nécessaire dans une recherche analogue dans un index non comprimé correspondant è plusieurs niveaux. Ceci augmente de façon appréciable la vitesse de recherche par rapport à la vitesse de recherche dans l'index non comprimé d'origine ordonné pour une même vitesse d8 lecture des multiplets dans la machine. 15 Un autre objet de cette invention est d'effectuer une recherche dans un index comprimé dans lequel la dimension des entrées de clés à plusieurs niveaux ne dépend pas de la dimension des clés non comprimées correspondantes. Par exemple, un indicateur a un index de niveau inférieur est accompagné par deux clés comprimées ne comportant que quelques multiplets qui représentent 20 une clé non comprimée qui peut avoir 100 ou 1000 multiplets. La valeur de la compression dépend principalement du resserrement de l'index, c'est-à-dire de l'importance des variations dans la relation ordonnée parmi les clés non comprimées de l*index. Des objets plus particuliers de cette invention sont: 25 A. Effectuer une recherche dans un index de niveau haut ayant un format de blocs comprimés qui lui permet d'être exploré par un argument de recherche non comprimé. B. Effectuer une recherche dans tous les niveaux de l'index par un argument de recherche qui ne se trouve pas dans l'index non comprimé 30 initial à partir duquel l'index comprimé est réalisé, l'argument de recherche pouvant tomber entre des clés non comprimées adjacentes représentées (1) à l'intérieur d'un seul bloc d'index comprimé, ou (2) dans deux blocs d'index comprimés. C. Effectuer une recherche dans chaque bloc d'index comprimé à plusieurs 35 niveaux qui est indépendant des autres blocs comprimés. Ceci évite d'avoir à reporter l'information recherchée d'un bloc de niveau supérieur dans l'opération de recherche de clé d'un bloc de niveau inférieur. La seule information antérieure nécessaire est l'adresse du bloc à rechercher. 40 D. Effectuer une recherche daBs un index à plusieurs niveaux en intro "0 177"0 2047949 duisant un bloc d'index, le compteur d'égalité étant mis à 0. E. Effectuer une recherche dans un bloc de niveau haut ayant un format CK, R pour chaque entrée, R étant l'indicateur et CK étant une clé comprimée. La recherche peut comprendre un niveau d'index le 5 plus bas avec une telle clé CK par indicateur. F. Effectuer une recherche à partir du niveau le plus haut dans l'index comprimé à plusieurs niveaux pour trouver un bloc de données dans lequel: (1) on accède qu'à un bloc comprimé par niveau d'index, 10 [2) le bloc de données correct est trouvé s'il est dans l'index initial à partir duquel l'index comprimé est obtenu, ou (3) l'argument de recherche n'est pas dans l'index et la recherche indique un emplacement dans l'index qui est adjacent à l'index où l'argument de recherche aurait été placé s'il avait été 15 dans l'index initial. G. Effectuer une recherche dans un index à plusieurs niveaux dans lequel on entre dans l'index comprimé au début d'un niveau inférieur au niveau le plus haut. H. Pouvoir faire une recherche complète d'un argument de recherche 20 en entrant dans l'index au début d'un niveau quelconque et en explo rant ce niveau en série jusqu'à ce qu'une clé correcte soit trouvée après quoi on peut accéder è un seul bloc par niveau. Dans l'invention on effectue une recherche de blocs ayant deux clés comprimées par indicateur aux niveaus d'index supérieure au niveau le plus 25 bas. Deux clés comprimées par indicateur sont engendrées à partir des dsux clés non comprimées JJK sur les cptés opposés de la limite entre des blocs comprimés adjacents au niveau de l'index le plus bas. Dans cette invention la terminologie "bloc" et "enregistrement" signifie la même chose. Les blocs dans les réalisations peuvent être séparés physique-30 ment ou ce peut être des blocs logiques différents dans le même bloc physique. L'invention fait la distinction entre la recherche au niveau le plus bas dans l'index à plusieurs niveaux et la recherche aux autres niveaux. Le terme "niveau bas" signifiera le niveau le plus bas de l'index à plusieurs niveaux et le terme "niveau haut" représentera un niveau quelconque au-dessus 35 du niveau bas. Avec cette invention, des blocs de l'index de niveau haut dans lesquels est effectuée une recherche ont un format différent des blocs de l'index de niveau bas. Le format de niveau haut associé a un couple de clés comprimées CK avec un seul indicateur qui adresse un bloc d'index de niveau inférieur 40 suivant tandis que le format de niveau bas associe une seule clé'comprimée 70 17710 5 2047949 à chaqus indicateur qui adresse un bloc de données. Dans le format de niveau haut, la première clé comprimée d'un couple indique le changement d'index dans le bloc référencé par l'indicateur associé et la seconda clé comprimée indique le changement d'index entre la dernière clé du bloc référencée par 5 l'indicateur associé et la première clé du bloc suivant dans la séquence. Les deux clés comprimées d'un couple sont nécessaires pour effectuer une recherche correcte avec un argument de recherche possible qui doit retrouver l'indicateur associé. Ainsi, la première clé CK du couple est la première clé CK "haute" (c'est-à-dire placée après l'argument de recherche dans l'ordre 10 de classement choisi) lorsque l'argument de recherche tombe dans la zône d'index du bloc de l'index adressé par l'indicateur, et la seconde clé CK du couple est la première-clé CK haute lorsque l'argument de recherche correspond à la dernière clé du bloc ou tombe entre cette clé et les blocs d'index suivants. Par suite un argument de recherche qui tombe entre deux blocs d'index 15 de niveau bas est associé au bloc auquel il serait relié pour une mise à jour future. La recherche dans chaque bloc de niveau haut ou de niveau bas dans l'index peut être effectuée indépendamment de la recherche dans les autres blocs. Cela veut dire que l'on peut effectuer une recherche dans un bloc d'index 20 adressé sans se baser sur le résultat de la recherche dans un autre bloc de l'index à l'exception d'un indicateur qui peut être obtenu à partir d'une recherche antérieure. Cette indépendance de recherche dans les blocs nécessite qu'un compteur d'égalité utilisé dans l'opération de recherche soit remis aux conditions initiales avant d'effectuer une recherche dans un bloc d'index 25 donné. La remise aux conditions initiales du compteur d'égalité détruit l'information qu'il contenait provenant d'une recherche antérieure. Cette indépendance permet à un bloc d'index d'être sélectionné arbitrairement et d'avoir la possiblité d'Stre exploré» Cette indépendance fournit les caractéristiques suivantes de l'invention: 30 Cela permet à un bloc suspecté d'avoir une condition d'erreur d'être sélectionné isolement et vérifié en effectuant une recherche dans ce bloc avec des arguments de recherche prédéterminés. Cela permet à un bloc isolé d'être sélectionné et mis à jour sans modifier les autres blocs de l'index. 35 Cela permet d'effectuer une recherche complète dans l'index en commençant a un niveau quelconque de l'index ce qui élimine les niveaux supérieurs. Le niveau introduit initialement peut avoir un seul ou plusieurs blocs. Le nombre des blocs par niveau augmente exponentiellement au fur et à mesure que le niveau d'index diminue, seul le niveau le plus haut peut avoir un seul 40 bloc mais ce niveau peut aussi avoir plusieurs blocs. 70 17710 6 2047949 10 15 20 La caractéristique décrite en dernier lieu permet aussi d'améliorer la fiabilité de la recherche en permettant d'éliminer certains ou tous les niveaux supérieurs en commençant une recherche à un niveau désiré. L'indépendance permet à une recherche dans un niveau désiré d'être réalisée en série dans toute la séquence de blocs jusqu'à ce que l'on trouve l'indicateur correct au bloc de niveau inférieur suivant. Si le niveau dans lequel est effectuée une recherche est un niveau haut, on peut amorcer une recherche à plusieurs niveaux avec l'indicateur correct pour retrouver le bloc de données désiré. L'indépendance permet d'avoir une certaine souplesse en travaillant sur un index ayant un nombre fixe de niveaux qui peut être un nombre quelconque de niveaux y compris un seul niveau. L'indépendance permet d'effectuer une recherche des blocs dans un niveau à partir d'une table d'indicateurs (adresses de bloc) pour ce niveau. Dans la table les indicateurs sont disposés en séquence dans l'ordre choisi des blocs à ce niveau. Par exemple une telle table peut être utilisée à la place du niveau le plus haut dans l'index comprimé. (On doit faire la distinction que dans une recherche binaire il faut des indicateurs auxquels on peut accéder de façon aléatoire alors que tout bloc comprimé unique nécessite d'être lu en série.). Dans la recherche binaire, il faut d'abord retrouver l'indicateur dans le milieu de la table pour sélectionner le bloc moyen de ce niveau d'index. Si la première clé du bloc moyen est supérieure à l'argument de recherche, son indicateur est emmagasiné et ensuite le bloc dans le milieu de la première moitié de l'index "bloc moyen de la première moitié" est recherché en utilisant l'indicateur moyen dans la première moitié de la table d'indicateurs. D'autre part, si la dernière clé dans le bloc moyen est supérieure, son indicateur est emmagasiné et le bloc moyen dans la seconde moitié de l'index adressé par l'indicateur dans la seconde moitié de la table d'indicateur est sélectionné. Ceci se poursuit et dans chaque étape, le nombre de ^ blocs dans lequel est effectuée la recherche étant dans le rapport 1/2n, où n est le nombre de blocs déjà explorés, jusqu'à ce que l'indicateur correct soit trouvé. On peut trouver l'indicateur correct à l'intérieur d'un bloc dans lequel est effectuée la recherche, ceci est indiqué par le fait que l'indicateur emmagasiné du bloc n'est pas le premier ou le dernier indicateur. Si un indicateur emmagasiné est. le premier ou.dernier indicateur d'un bloc de l'index, cette exactitude possible est indiquée si la recherche binaire emmagasine l'indicateur suivant par rapport à l'extrémité opposée du bloc suivant, auquel cas les deux indicateurs sont emmagasinés et l'indicateur correct est déterminé par vérification. La rechercha binaire se termine lorsqu'il n'y a plus d'indicateur à sélectionner dans la table d'indicateurs 25 35 40 70 17710 7 2047949 auquel cas le dernier indicateur lu "premier ou dernier" est l'indicateur correct. D'autres objets caractéristiques et avantages de la présente invention ressortiront mieux de l'exposé qui suit, fait en référence aUx dessins annexés 5 à ce texte, qui représentent un mode de réalisation préféré de celle-ci. La figure 1A représente un index comprimé de niveau haut et la figure 1B représente un index comprimé de niveau haut obtenu à partir de l'index non comprimé. Les figures 2A et B représentent les circuits de mémoire intermédiaire 10 et d'entrée/sortie utilisés pour emmagasiner un index non comprimé de niveau haut et l'ind8X comprimé résultant. La figure 3 représente un circuit de commande de mode et d'horloge. La figure 4A représente la chronologie du mode de formation (d'index comprimé) et la figure 4B représente la chronologie du mode de recherche 15 (dans l'index) pour le circuit des figures 9A et B. La figure 5A représente le format pour un bloc comprimé de niveau bas alors que la figure 5B représente un format pour un bloc d'index comprimé de niveau haut. La figure 6 représente la structure du bloc d'index comprimé à plusieurs 20 niveauengendré conformément à cette invention. La figure 7A représente une vue générale d'un ordinateur utilisé dans la mise en oeuvre de l'invention et les figures 7B et C représentent les tables utilisée dans les diverses réalisations. La figure 8 représente des commandes d'interface et décodeur de commande 25 pour une réalisation d'un système de commande de recherche dans un index à plusieurs niveaux. Les figures 9A et B représentent les commandes d'horloge de mode de recherche utilisées dans une version "mode de recherche" de l'invention. Les figures 10 et 11 représentent des commandes utilisées pour engendrer 30 un index comprimé et effectuer une recherche dans l'index comprimé. •Les figures 12 et 13 représentent des circuits utilisés pour effectuer une recherche dans un index comprimé. Les figures 14A-G représentent une réalisation du procédé de recherche de cette invention. 35 Les figures 15-19 représentent une réalisation d'un système de commande de recherche dans un index à plusieurs niveaux. Un index à plusieurs niveaux dans lequel est effectué une recherche par l'invention est représenté sur la figure 6 par les niveaux d'index comprimés L1 à L4. Au cours d'une recherche, on recherche l'information à partir 40 du niveau de données (L0). L'index à plusieurs niveaux comprend un index 70 1771Q 8 2047949 comprimé de niveau bas L1 et des index comprimés de niveau haut L2, L3 et L4. Un cinquième index n'est pas comprimé et peut constituer une entrée dans un catalogue classique, l'entrée comprend le nom de la base de données LO, et une adresse (indicateur) R^ qui localise le bloc d'index comprimé de 5 . niveau le plus haut L4. 4-1. Le niveau de données LO comprend un grand nombre de blocs de données, chacun étant indexé par sa clé non comprimée UK qui comprend un premier bloc d'information ayant une clé UK (A^) jusqu'à un dernier bloc ayant une clé UK Le choix de la clé pour chaque bloc ne fait pas partie de cette 10 invention et on peut utiliser un champ dans le bloc pour indexer ce bloc. Par exemple, la clé peut être un champ dans le bloc représentant un article, un numéro matricule, un numéro de département, un numéro de license, etc.. avec d'autres parties dans le bloc représentant l'information indexée par la clé. Les blocs au niveau de donnée LO peuvent être placés au hasard aux 15 endroits où il y a de la place dans un dispositif d'emmagasinage à accès aléatoire, par exemple, une unité à disque magnétique, à tambour magnétique ou une unité à bande. Il n'y a pas de conditions imposées sur la position des blocs dans les niveaux L0-L5 que ce soit une relation séquentielle ou autre entre ces blocs. Chaque bloc peut être placé à n'importe quel endroit 20 où il y a de la place sur le dispositif dans la mesure où les adresses des blocs dans l'espace disponible sont amenées comme entrée. La condition primordiale pour une recherche rapide est que l'on puisse avoir accès rapidement à un bloc lorsqu'on a son adresse. Les blocs sur la figure B au niveau LO sont représentés dans l'ordre 25 de la séquence ordonnée des clés non comprimées UK. (A^) à UK (@n). Cette représentation ordonnée fait partie de l'organisation de la structure à plusieurs niveaux de l'invention. Cependant, cette relation ordonnée n'est pas une relation de position avec les emplacements des données ou blocs d'index sur le ou les dispositifs à accès alléatoire sur lesquels sont emmagasinés 30 les blocs. Une conséquence avantageuse de cette organisation d'indexage à position aléatoire est qu'il n'est plus nécessaire de déplacer un bloc inchangé chaque fois que les nouveaux blocs sont ajoutés quelque part dans la séquence ordonnée. Il est préférable bien que cela ne soit pas nécessaire que l'e niveau 35 le plus haut n'est qu'un seul bloc. Une recherche bloc dans LO en utilisant cette structure d'indexage ne nécessite que l'accès d'un bloc par niveau de l'index à la vitesse de l'ordinateur quelque soit le nombre des blocs dans un niveau quelconque. Par suitB, sur la figure 6, tout bloc L0 nécessaire peut être recherché directement 40 au sixième accès après cinq accès d'indexage à partir du niveau L5 au niveau 70 17710 g 2047949 L4, L3, L2, L1 et LO. Les six accès ne sont pas affectés par le nombre de blocs à un de ces niveaux comprenant le niveau de données LO. Le début de chaque bloc d'index est placé à une adresse appelée un indicateur R ayant deux indices. Le premier indice représente le niveau du bloc 5 adressé et le second représente la position dans la séquence ordonnée du bloc adressé dans le niveau particulier. Les indicateurs Rg_ AT vjri LO. Au niveau L1 chaque clé comprimée est associée à un indicateur tel que la première clé CK. CA^3 associé à l'indicateur R^ pour localiser le premier 15 bloc LO et chaque bloc dans le niveau L1 est sngendré par le procédé décrit dans les demandes de brevet n° 6945785 et 6945787 déposés par la demanderesse en France le 30 Décembre 1969. Une base de données LO très grande peut être traitée par la structure d'indexage de la figure 6. En conséquence l'index peut traiter un très grand 20 nombre de clés pour effectuer une recherche parmi un nombre correspondant de blocs au niveau LO. Par exemple, les tableaux B et C suivants représentent un index comprimé qui peut loger 27 000 blocs de données distincts si chaque bloc L1 comprend 1 000 clés comprimées CK, ce qui est un nombre possible.- Le tableaut A représente l'index non comprimé correspondant à l'index comprimé 25 des tableaux B et C. Dans un autre exemple, si chaque bloc d'index dans les niveaux L1-L4 de la figure 10 est supposé comporter 35 indicateurs par bloc, les quatre niveaux de l'index permettront de loger jusqu'à 1 500 625 blocs de données au niveau L0. Par suite il devient possible de rechercher au hasard 1 500 625 blocs de données en cinq accès, ce qui peut être réalisé en moins 30 d'une seconde en utilisant sept dispositifs différents à accès direct DASD ayant chacun un temps d'accès moyen inférieur à 200 millisecondes, ce qui est possible actuellement* Dans le cas particulier, où chaque bloc d'index a C clés, et que j niveaux d'index sont utilisés, le nombre maximum de blocs L0 est CJ. 35 On va donner quelques exemples utilisant quatre niveaux d'index tj=4): (1J En utilisant 100 indicateurs par bloc: 1 010 101 blocs d'index sur les quatre niveaux peuvent répertorier -un maximum de 1 000 000 000 blocs de données au niveau L0. _ (2) En utilisant 1 000 indicateurs par bloc 1 001 001 001 blocs d'index 40 sur les quatre niveaux peut être indexés à un maximum de 1 trillion 70 17710 10 2047949 soit 1 000 D00 000 000 blocs de données au niveau L0. Dans les exemples C1) et (2) il faut cinq accès pour rechercher" un bloc de données L0 en amorçant une recherche avec le bloc de niveau le plus haut. Si on utilise des clés comprimées au lieu des clés non comprimées dans chaque 5 bloc d'index, le nombre des blocs d'index est réduit lorsqu'on utilise des. blocs ayant le même nombre de multiplets, ou la longueur des multiplets des blocs d'index est réduite lorsqu'on utilise le même nombre de blocs d'index. Ainsi, pour un facteur de compression de 1 dizième, en utilisant des clés comprimées l'exemple (1) peut soit (a) réduire dans le rapport, de 1 dizième 1Q le nombre des blocs de l'index en conservant la même longueur en multiplets pour un total de 101 011 blocs d'index soit Cb) réduire de 1 dizième la longueur des multiplets de chacun des 1 010 101 blocs, line compression identique dans l'exemple (2) peut soit Ca) utiliser la même longueur de multiplet pour réduire le nombre total des blocs d'index à 100 100 101, soit Cb) réduire dans le 15 rapport de 1 dizième la longueur des multiplets de chacun des 1 001 001 001 blocs d'index. Le tableau A suivant représente un index non comprimé à plusieurs niveaux ayant quatre niveaux d'index L1-L4 de blocs à partir desquels est engendré l'index comprimé à plusieurs niveaux des tableaux B et C: Sur ces tableaux 20 les colonnes eéférencées BL contiennent des désignations de blocs, les. colonnes référencées UK ou CK. contiennent respectivement des désignations des clés non comprimées ou comprimées et les colonnes référencées IND contiennent les références des indicateurs associés aux clés ou couples de clés. TABLEAU A 25 INDEX NON COMPRIME A PLUSIEURS NIVEAUX 30 1-1 L1 BL. UKs IND. A1 An L2 BL. UKs IND. 2-1 A R„ „ n 1-1 L3 BL. UKs IND. 3-1 C R_ , n 2-1 L4 BL. UKs IND. 4-1 I R , n 3-1 70 17710 u 2047949 L1 BL. UKs IND. 1-2 Bl RB1 B ri Bn 1"3 C1 RC1 C Rr n . Cn —/«•—— 1-4 D, RD1 I • I I Dn ROn 1-5 E. R,., 1 E1 E Rc n En 1 F1 I t » I F Rc n , Fn —+—■ W G1 R01 G R_ n Gn 1-B ^ Rm H Ru n Hn L2 BL. UKs IND. Bn R1-2 C R, ~ n 1-3 2-2 -D R. „ n 1-4 E R-. C n 1-5 F R- B n 1-6 2-3 G R. n 1-7 H R L3 BL. UKs IND. n 2-2 n 2-3 —// 3-2 L R„ . n 2-4 °N R2-5 Rn R2-6 —// 3-3 U - R- -, n 2-7 Xn R2-6 L4 BL. UKs IND. R R 3-2 n R3-3 FIN '/// Fin d'index L4 70 17710 12 2047949 L1 BL. UKs IND. 1-9 I, 11 n ,, In ---r/—-» 1-10 J 1 "J1 n Jn 1-11 K 1 K1 n Kn 1-12 L. L 1-13 M -0-,- 1 L1 Ln M Mn 1-14 N. N1 l\l R, 1-15 D 1 Nn 01 o Rn _n_^___0n L2 BL. UKs IND. I R„ „ n 1-9 1 / 2-4 J Ra An n 1-10 K R« -4 n 1-11 'n 1-12 / 2-5 H R„ „0 n 1-13 N R, AA n 1-14 0 R, n 1-15 L3 BL. UKs IND. G FIN 2-9 —// Fin d'index L3 L4 BL. UKs IND. 70 17710 13 2047949 L1 BL. UKs IND. 1-16 P. P1 n Pn 1-17 CJ 1 Q1 Qn 1"18 R1 RR1 r 9 r • Rn_^_RRn 1"19 S1 RS1 S R„ n Sn 1-20 T. T1 T RT n Tn 1-21 U1 Rui U Rn _n_^___Un_ 1-22 V R • I I f V R.. n Vn L2 BL. UKs IND. 2~B Pn R1-1B *n R1-17 Rn R1-1B —//- 2-7 S R. ,Q n 1-19 Tn R1-20 Un R1-21 2"6 V R1-22 L3 BL. UKs IND. L4 BL. UKs IND. 70 17710 14 2047949 L1 BL. UKs IND. 1"23 W1 RW1 W R.. n Wn 1-24 Xl RX1 * r X Rv Xn 1-25 Y1 Ryi i > i » Y R., n Yn 1-26 Z. R7, 1 Z1 i » Z R-, 1-27 G. R „ 1 1 » I I I Fin d'index L1 L2 BL. UKs IND. W R. n 1-23 Xn R1-24 / 2"9 V R1-25 Z R. __ n 1-26 ®1 @n R1-27 FIN « /- Fin d'index L2 L3 BL. UKs IND. L4 BL. UKs IND. 70 17710 15 2047949 TABLEAU B INDEX COMPRIME A PLUSIEURS NIVEAUX 5 10 15 20 25 30 35 L1 L2 BL. CKs IND. BL. CKs IND. 1-1 CKCA1 ), Ra 1 1 2-1 CK(An), CKCB^, R1M 1 1 CK.CB ], CKCCJ, R. _ 1 1 n 1 1-2 00 ' RAn CKCC ), 00- , . R, _ n ^ i J 1-2 CMB^. Rq1 1 « i t 1 00 . R_ t i i i i i i i i i i i i i IDC t D 1-3 CKCC1), RC1 1 1 i i « 1 00 , ' R« qu t f i ■ f t 9 i i » - i t 1-25 CKCYr Ry1 1 t 2-9 CKCY ), CKCZJ, R. n 1 1-zd 9 » 9 9 CKCZnJ. cue^), R^_26- 00 , RYn CKfanJ.0Q- . R,_27 «•—W-M f - 1-2B CKCZ^), RZ1 9 9 9 9 0° :„._JzD 1-27 CK^Î. RQ1 00 ' ^Sn /// 70 17710 16 2047949 TABLEAU C INDEX COMPRIME A PLUSIEURS NIVEAUX BL. 3-1 3-3 L3 CKs IND nJ' CKÎD ), R2-1 n3' CKCG^, R2-2 : ), n 00 , // R2-3 CKCU^J, CKCV^, CKCX^), CKCY^, CKI@ ), 00 /j 2-7 *2-8 *2-9 L4 B. CKs IND. 4-1 CKCI^, CKCJ^, R CKtR ), CKCSJ, R n 1 CK( 3-2 a ?:3_ Le tableau A, colonne L1, représente les blocs du-niveau d'index le plus bas L1 de clés non comprimées UK obtenues à partir des champs des clés des blocs d'information au niveau de données L0. Les blocs d'information au niveau L0 ne doivent pas nécessairement être disposés dans un ordre-parti-30 culier et on suppose qu'ils ont une disposition "aléatoire. Les clés sont " - . prises à partir d'un champ dans les blocs d'information L0 nécessaires pour l'indexage. Une fois que les clés des blocs L0 sont obtenues, elles sont ordonnées et bloquées pour engendrer la séquence de blocs UK de niveau L1 telle que représentée dans la colonne L1 par un moyen connu de l'homme de --O 17710 17 2047949 l'art et ne faisant pas partie de l'invention. Par suite, les clés non comprimées UK et leurs blocs sont dans une séquence ordonnées dans la colonne L1 et elles sont emmagasinées sous une forme qui peut fournir l'entrée au mode de formation de cette invention. 5 Par exemple, Slles peuvent être emmagasinées sur un dispositif entrée/ sortie à bande d'une manière séquentielle telle que les 27 blocs consécutifs 1-1 à 1-27 du tableau A, colonne L1. Ces blocs UK sont utilisés pour engendrer des blocs de clés non comprimées 2-1 à 2-9 représentés dans la colonne L2 du tableau A. Les blocs UK dans la colonne L2 sont alors utilisés pour engen-10 drer les blocs UK dans la colonne L3 etc.. jusqu'à ce que le niveau le plus haut L4 soit engendré qui comprend un seul bloc UK. En conséquence, chaque niveau actuel de blocs UK est utilisé pour engendrer le niveau supérieur suivant des blocs UK. De plus, tout en engendrant le niveau de blocs UK supérieur suivant, la réalisation décrite ici comprime 15 aussi les clés au niveau UK actuel. La longueur des blocs UK à un niveau quelconque est déterminée par la dimension nécessaire pour les blocs à ce niveau. La limite à la fin de chaque bloc dans le tableau A, dans la colonne L1 est représentée par les lignes en pointillés et certaines des lignes en pointillés ont une ou plusieurs 20 lignes obliques qui les coupent £/) pour représenter la signification de la limite aux niveaux supérieurs. Toutes les limites des blocs de niveau L2 dans le tableau A sont identifiées par le symbole —/ , toutes les limites des blocs de niveau L3 par le symbole —// , et toutes les limites des blocs L4 par le symbole — . L'utilisation de ces symboles indiquent 25 l'importance des limites. Les clés non comprimées sur les côtés opposés de chaque limite extrême sont importantes dans la formation des clés comprimées de niveau supérieur, et sont appelées "clés non comprimées limites". Chaque limite de fin de blocs est représentée par deux "clés non comprimées limite". 30 La séquence UK de second niveau (L2) représentée dans la colonne L2 du -tableau A comprend toutes les clés "UK limite" dans la séquence de blocs L1. La séquence UK de troisième niveau. CL3) représentée dans la colonne L3 du tableau A comprend le dernier couple de clés non comprimées dans chaque 35 bloc UK dans la séquence de niveau L2. Le dernier niveau (L4) dans l'exemple du tableau A comprend le dernier couple de clés non comprimées dans chaque bloc UK dans la séquence de niveau L3. Certaines "clés non comprimées limites" L1 constituent le dernier couple de clés non comprimées à la fin de chaque bloc à chaque niveau supérieur. 40 Ainsi, au niveau L1, une limite sur trois identifie un couple de clés non 70 17710 18 2047949 comprimées qui ast utilisé pour terminer chaque bloc au niveau L2, une limite L1 sur neuf, définit les "clés non comprimées limites" utilisées pour terminer chaque bloc au niveau L3 et la dernière limite L1 (27ième) définit les clés non comprimées limites utilisées pour terminer le bloc de niveau le plus 5 haut au niveau L4. Ainsi les "clés non comprimées limites" terminant le bloc de niveau haut terminent aussi le dernier bloc de chaque niveau haut inférieur (au-dessus de L1), et représente aussi les dernières "clés non comprimées limites" au niveau bas L1. Le nombre de clés non comprimées dans chaque niveau haut EL2 et niveau 10 supérieur) est suppposé égal à six dans l'exemple du tableau A. Chaque couple de niveau haut des clés non comprimées et d'un indicateur engendre deux clés comprimées correspondantes avec le même indicateur que l'on trouve dans les tableaux B et C. En pratique un grand nombre d'indicateurs ayant chacun un couple de 15 clés comprimées peut être fourni dans un bloc. La dimension du bloc est déterminée en pratique par l'utilisateur et elle dépend du type de mémoire dont il dispose pour l'index à plusieurs niveaux et la vitesse de recherche nécessaire. La dimension d'un bloc comprimé est directement associée à la vitesse de recherche puisqu'un bloc unique est recherché séquentiellement depuis 20 son début. Par suite, plus le bloc est court, moins le temps de recherche est long dans un bloc. Il est rarement nécessaire d'effectuer la recherche jusqu'à la fin d'un bloc donné puisque la,recherche se termine dès que l'argument de recherche ast inférieur à une clé comprimée dans un bloc. Une régie empirique pour déterminer les temps de recherche moyens par bloc revient 25 à prendre le temps nécessaire pour balayer la moitié d'un bloc. Pour faire la recherche on peut utiliser le procédé et les moyens décrits dans les demandes de brevets n° 6945436 et 6945787 déposées par la demanderesse en France le 30 Décembre 1969. Le nombre des blocs balayés séquentiellement par un argument de recherche 30 est généralement égal au nombre des niveaux dans l'index. Ainsi, la vitesse de recherche est indépendante du nombre de blocs dans un niveau donné. D'autres facteurs pour déterminer la dimension des blocs à plusieurs niveaux eont l'efficacité de l'utilisation de l'espace d'emmagasinage des dispositifs I/O particuliers dans lesquels des blocs peuvent être emmagasinés et leur temps 35 d'accès. Bien que l'on ait représenté les blocs de même dimension pour tous les niveaux hauts du tableau A ceci est. un cas particulier. La dimension des blocs exprimée en nombre de clés comprimées par bloc peut être représentée par C^, C2 Cj aux niveaux respectifs 1, 2 ...j, où j. est.le niveau- le 40 plus haut. C/2 représente le nombre d'indicateurs dans le bloc d'index de 70 17710 19 2047949 niveau haut, où le niveau .haut est le niveau 2 ou un niveau supérieur. C/2 est aussi le nombre des blocs suivant de niveau inférieur répétorié par ce mSme bloc. représente le nombre des indicateurs dans un bloc L1. K^, .....représentent le nombre des blocs aux niveaux d'indice 5 inférieur respectifs. Le nombre K des blocs diminue exponentiellement au fur et à mesure que-le numéro des niveaux augmente. Par suite, le nombre total des blocs dans un index est K^* K2+ .... + K ^. Cette série de nombres diminue de K^ à K^. Au niveau le plus bas L1 une seule clé CK par indicateur est utilisée et KQ = K1 x . 10 Dans le cas particulier où le nombre des indicateurs (R) par bloc est égal pour tous les niveaux de l'index, et que L = 1, on a alors C = KQ/K^ = K^/K2 = ... Ge cas particulier est représenté dans le tableau A. Le nombre total des blocs de données LO traité dans ce cas particulier est Rj. 15 Les tableaux B et C représentent les quatre niveaux de l'index comprimé à plusieurs niveaux qui est obtenu à partir de l'index non comprimé à plusieurs niveaux représenté sur le tableau A. Les tableau B et C comportent le même nombre de blocs que le tableau A, mais chaque bloc dans les tableaux B et C est plus petit à cause de la compression. En conséquence, il y a une relation 20 biunivoque Bntre les blocs respectifs dans les index comprimés et non comprimés. La figure 7A représente une vue générale de l'environnement de la réalisation de l'invention dans laquelle les étapes sont exécutées par le circuit de commande d'index 516. Elle comprend.un canal et/ou une unité centrale de traitement (CPU) 511 qui relie une mémoire 510 par l'intermédiaire de 25 lignes de tranmission et de commande 511A aux commandes d'interface 512 et aux commandes I/O 530. Ces commandes I/O 530 sont reliées à plusieurs dispositifs I/O 530C-1, 530C-2 et 530C-3. Dans les dispositifs 530C 8st emmagasiné l'index comprimé à plusieurs niveaux. Il ne faut plusieurs dispositifs d'entrée/sortie que lorsque l'index comprimé exige une capacité d'emmagasinage 30 supérieure à celle que l'on obtient avec un seul dispositif. Dans ce sens, le numéro de référence 530C ne représente que le nombre nécessaire de dispositifs dans lesquels est emmagasiné l'index. Chaque dispositif 530C a de préférence une possiblité d'accès aléatoire rapide sur une base par bloc et il peut être constitué d'un ou plusieurs disques magnétiques,, tambours magnétiques 35 ou unités à bande magnétique. Avant d'amorcer ls procédé de la figure 14D, il est nécessaire que les dispositifs 530C contiennent l'index à plusieurs niveaux de blocs comprimés et que la mémoire 510 soit chargée avec la table de commande nécessaire ayant des commandes qui peuvent être décodées par le décodeur 513 sur la figure 40 7A. 70 17710 20 2047949 Avant d'amorcer une recherche dans un niveau, il ast aussi nécessaire que la mémoire 510 soit chargée avec les tables d'indicateurs représentées sur la figure 7C. Recherche èi plusieurs niveaux; 5 Un argument de recherche (S.A) est un article non comprimé que l'on trouva dans la liste d'arguments de recherche dans la mémoire 510 de la figure 7A. Il est à chercher dans l'index à plusieurs niveaux représenté sur la figure 6, qui peut être emmagasiné sur un ou plusieurs des dispositifs d'entrée/sortie 530C. L'argument de recherche peut être un article alphanumé-10 rique comportant des caractères spéciaux et il peut comprendre une clé non comprimée UK utilisée dans la formation de l'index à plusieurs niveaux cette clé pouvant Être appelée une clé UK initiale. Si l'article est une clé UK initiale, il sera trouvé par une recherche à plusieurs niveaux. D'autre part si l'article n'est pas une clé UK initiale, il n'est pas représenté dans 15 l'index à plusieurs niveaux et par suite ne sera pas trouvé mais le bloc particulier est trouvé à l'endroit où cet article serait placé dans l'index comprimé si l'index devait être mis à jour par la suite pour l'inclure. Sur la figure 6, une recherche commence par l'accès à l'emplacement du bloc comprimé de niveau le plus haut 4-1, accès obtenu en utilisant l'in-20 dicateur emmagasiné dans le cinquième nivBau. Par conséquence, cet indi cateur localise l'emplacement où l'argument de recherche doit commencer la recherche dans l'index à plusieurs niveaux. Le bloc 4-1 est ensuite lu. Comme les clés comprimées sont lues en série à partir du bloc 4-1, elles sont comparées avec l'argument de recherche en 25 utilisant la technique décrite dans les demandes de brevet 6945786 et 69457S7 déposées par la demanderesse en France le 30 Décembre 1969. Au fur et à mesure que les clés comprimées sont comparées à l'argument de recherche, une des clés comprimées dans le bloc au niveau le plus haut sera trouvée supérieure et son indicateur associé Rg_x sera emmagasiné temporairement. 30 L'indicateur emmagasine R„_ provenant du bloc de niveau le plus haut est ensuite utilisé pour sélectionner le bloc correfet au niveau inférieur suivant (L3). Ce bloc est lu de la même façon et ses clés CK comparées à l'argument de recherche jusqu'à ce que l'on trouve la première cl'é CK supérieure', et son indicateur associé R2_x est emmagasiné temporairement pour rechercher le 35 bloc correct au niveau inférieur suivant [L2]. Ensuite le bloc est recherché avec ^2-x aU n^veau inférieur suivant et ses clés CK sont lues d'e nouveau et comparées à l'argument de recherche jusqu'à ce que l'on détecte la première clé CK supérieure et son indicateur associé R.j_x est emmagasiné. Ce procédé de recherche d'un bloc à chaque niveau inférieur se poursuit jusqu'à ce'que 40 le dernier indicateur recherché sélectionne un des blocs du niveau de données 70 17710 21 2047949 CLOÎ. Chaque bloc de données a un ou plusieurs champs qui doivent définir la clé UK initiale utilisée pour construire l'index. Ce champ est recherché à partir du bloc de données et est comparé à l'argument de recherche pour vérifier si le bloc de données retrouvé est le bloc désiré. C'est le bloc 5 correct si son champ prédéterminé est égal à l'argument de recherche. Si ces deux éléments ne sont pas égaux, l'argument de recherche n'est pas dans l'index comprimé.Cependant, les blocs à plusieurs niveaux sélectionnés sont les seuls blocs dans l'index qui doivent être mis à jour si il faut par la suite inclure cet argument de recherche dans l'index. 10 La recherche à plusieurs niveaux décrite dans le paragraphe précédent est obtenue par le procédé représenté sur les figures 14A-F. L'accès au bloc correct dans la recherche est réalisé par le procédé représenté sur les figures 14D-F. La recherche dans un bloc auquel on a accédé est réalisée par le procédé représenté dans les figures 14A-C.. Les figures 14A-C sont pratique-15 ment identiques aux figures 14A- B et C dans la demande de brevet 6945787 citée précédemment. En conséquence; les figures 14A-C de ce brevet ne seront pas décrites en détail puisqu'on pourra se référer à cette demande de brevet, seules quelques modifications y ont été apportées. Ces modifications sur les figures 14A sont les entrées D-10 et D-12 qui remplacent l'étape de détart. Sur la 20 figure 14B les étapes 884, 866 et 867 ont été ajoutées. Sur la figure 14C la sortie C10 remplace l'étape finale que l'on trouve dans les figures de la demande de brevet mentionnée. Le circuit représenté sur les figures 3, 9A-13 exécute le procédé des figures 14A, B et C de la mêmB manière que dans la demande de brevet citée, 25 il y a un seul changement sur la figure 13 à savoir le prolongement de la-sortie du circuit ET 332 ayant la désignation "bloc actuel supérieur sur P=Q". Le procédé de recherche à plusieurs niveaux est introduit sur la figure 14D par l'étape de départ 910, qui représente soit une opération de départ 30 manuelle soit unB opération de départ automatique pour faire passer à l'étape suivante 911 qui comprend la recherche d'une commmande "écriture argument de recherche et premier indicateur" provenant de la table de commande dans la mémoire 510 de la figure 7A et la transmission de cette commande sur le bus 511A à partir de l'unité centrale de traitement au décodeur de commande 35 513 qui décode la configuration de bit particulière dans son code opération pour exciter la ligne de sortie 5131 sur la figure 8, qui est amenée aux figures 17 et 19. Cette commande est exécutée dans l'unité centrale de traitement par la transmission de l'argument de recherche et d'un indicateur tinitialement l'indicateur du bloc de niveau le plus haut) aux commandes 40 d'interface 512. 70 17710 22 2G47949 L'étape 912 est introduite simultanément lorsque sur la figure 19, la ligne 5131 est excité, cette ligne allant aux commandes d'adresse d'indicateur et d'argument de recherche 667, qui excitent ensuite la ligne de sortie 667A allant au compteur d'adresse 11a de la figure 15 pour le mettre à l'adresse 5 prédéterminée du registre d'argument de recherche dans la mémoire 10 représenté sur la figure 2B. Le registre d'indicateurs dans la mémoire 10 est contigû au registre d'argument de recherche. La porte 621 sur la figure 17 est conditionnée par la même ligne 5131 de sorte que les multiplets de l'argument de recherche reçus à partir de 10 l'unité centrale de traitement sur le bus de sortie 511B passent par la porte 621 et vont aux bus d'entrée de la mémoire 10 621A, qui est reçue par le circuit OU 522a sur la figure 15 qui transmet l'argument de recherche au registre désiré dans la mémoire 10. Pendant la réception de l'argument de recherche, une ligne de champ d'argument de recherche 666A conditionne la 15 porte 621 par l'intermédiaire du circuit OU 622 sur la figure 17. La ligne 666A vient du décodeur 666 de la figure 19 pendant qu'il reconnait les adresses de multiplet provenant du compteur 11a à l'intérieur du champ du registre de l'argument de recherche dans la mémoire 10. Ensuite, la ligne 666C est excitée par le décodeur 666 lorsque le dernier multiplet de l'argument de 20 recherche charge le compteur d'adresse 11a à l'emplacement du registre d'indicateurs dans la mémoire 10, et le transfert des multiplets de l'indicateur se poursuit jusqu'à ce qu'il soit terminé pour l'indicateur localisant le bloc de niveau supérieur de l'index comprimé dans le registre d'indicateurs de la mémoire 10. L'étape 912 est terminée lorsque le registre d'arguments 25 de recherche et le registre d'indicateur trouvé sont chargés dans la mémoire 10. L'étape 913 fournit le signal C.E. & D.E. (signal de fin de bloc) à partir du basculeur 624 sur la figure 17, une fois que le circuit ET 623 a enclenché le basculeur 624 en réponse à l'excitation de la ligné transfert 30 CPU terminé 512C provenant des commandes d'interface 512 sur la figure 6. Ensuite, l'unité centrale de traitement transmet un signal d'acceptation d'état sur la ligne 512D provenant des commandes d'interface 512 qui restaure le basculeur 624 pour terminer le signal C.E. S D.E. Une recherche à plusieurs niveaux nécessite que l'étape 920 soit réalisée 35 en réponse à l'étape 913 afin que l'unité centrale de traitement recherche une commande "recherche* comme commande suivante à partir de la table'de commandes dans la mémoire 10. (l'autre étape 940 est utilisée pour effectuer une recherche de plusieurs blocs à un seul niveau et elle sera décrite par la suite). 40 La commande "recherche " est transmise au décodeur 513 qui excite sa 70 17710 23 2047949 ligne de sortie 513J allant aux figures 17 et 16. Les étapes 921 et 922 sont réalisées simultanément. Au cours de l'étape 921, le signal sur la ligne 513J actionne le monostable 625 sur la figure 17 pour enclencher lé basculeur 826 qui fournit un 5 signal de commande de lecture et de sélection I/O aux commandes de sélection I/O 530h sur la figure 17 qui fait partie des commandes I/O 530 sur la figure 16. Ceci conditionne la porte 627 et les commande 530g. La ligne de commande de recherche 513J est aussi amenée aux commandes 667 sur la figure 19 pour exciter la ligne d'adresse du registre d'indicateurs 10 667B qui provoque l'extraction de la mémoire 10 du champ du registre d'indicateurs sur le bus de sortie 14, qui est transmis par la porte conditionnée 627 (figure 17) aux commandes de sélection I/O conditionnées 530g. Chaque dispositif I/O 530 est sélectionné avec l'indicateur, et c'est ce même dispositif qui permet la formation de l'index à plusieurs niveaux. On accède ensuite 15 au bloc de niveau le plus haut, dans le dispositif I/O 530c en utilisant cet indicateur pour terminer l'exécution d8 l'étap8 921. L'étape 922 est exécutée lorsque la ligne de commande de recherche 513J actionne un monostable 625 (figure 17) qui envoie des impulsions à la ligne 625B (figure 13), où il restaure le compteur d'égalité 301. Ceci rend la 20 recherche du bloc suivant indépendante des résultats de la recherche d'un bloc antérieur sauf pour l'adresse du bloc acutel. Ensuite on introduit l'étape 923 dans laquelle la lecture du bloc auquel on a accédé commence et on passe à l'étape de sortie D10 (figure 14A) pour comparer l'argument de recherche aux multiplets à l'intérieur de ce bloc, 25 de la même manière que celle décrite en détail dans la demande de brevet n° 6945787 déposée par la demanderesse en France le 30 Décembre 1969. Lorsqu'on arrive à l'étape 844 (figure 14A) le multiplet transféré au registre de niveau 268 sur la figure 12 excite la ligne de sortie de niveau haut 268A allant à la figure 18. 30 Lorsque le procédé de la figure 14B est exécuté, on introduit l'étape 866- afin de lire le format du bloc de niveau haut dans lequel chaque indicateur a une seconde clé comprimée associée. L'étape 866 fonctionne de la même façon en ce qui concerne le basculeur binaire 211 de la figure 9B pour indiquer que dans une opération de niveau haut un circuit ET 209 est excité et 35 le basculeur P suivant 213 sera enclenché pour exécuter l'étape 867 en vue de la lecture de la seconde clé CK du couple de clés de" niveau haut. L'étape 684 suit pour commander la lecture de la seconde clé CK d'un couple. Pendant la recherche du bloc de niveau supérieur (ou d'un autre bloc) on trouve un indicateur, et il est emmagasiné dans le registre d'indicateurs 40 de la mémoire 10 par les étapes 886-891 (figure 14C-K Cet indicateur est 70 17710 24 2047949 ensuite utilisé pour accéder au bloc correct au niveau inférieur suivant dans l'index à plusieurs niveaux. L'étape 892 (figure 14C) indique éventuellement (le basculeur 326 étant enclenché) qu'une clé supérieure à l'argument de recherche a été trouvée ou que (ce basculeur 333 étant enclenché) la der-5 nière clé ayant P=0 a eu son indicateur lu puisqu'aucuns clé comprimée dans le bloc n'était supérieure à l'argument de recherche. L'étape 894 indique que 1b basculeur "recherche terminée" 331 de la figure 13 est enclenché et l'étape 895 est exécutée dans le circuit ET 336 lorsqu'il fournit un signal de sortie de restauration générale qui fait que le procédé de la figure 14C 10 aboutit en C10 et amène à l'étape 930 de la figure 14D. L'étape 930 détermine si la commande actuelle est une commande "recherche" ou une commande "recherche à un niveau" qui sont les deux commandes possibles à ce point du procédé. Une commande "recherche" fait passer de l'étape 930 à l'étape 931 qui détermine le niveau actuel suivant le signal sur la ligne de niveau haut 15 268A ou la ligne de niveau bas 260B provenant de la figure 12 et allant au circuit ET 642 ou 644 respectivement sur la figure 18. Puisqu'à l'origine il existe le niveau haut la ligne 268A est d'abord excitée. Ensuite on passe à l'étape 921, le circuit 642 est excité pour enclencher un monostable 643 qui enclenche un basculeur 626 (figure 17). L'étape 921 20 est ensuite exécutée de la manière précédemment expliquée pour cette étape. Le signal de sortie du basculeur 626 accède et lit le bloc adressé par l'indicateur qui se trouve dans le registre d'indicateurs de la mémoire 10 qui a été placé dans ce registre au cours du procédé décrit sur la figure 14C. Ensuite l'étape 922 est exécutée de la manière précédemment expliquée 25 et on aboutit en D10 sur la figure 14A, où les étapes des figures 14A, B et C sont reprises comme précédemment expliqué pour rechercher dans le bloc actuel l'indicateur du bloc correct au niveau inférieur suivant, lequel indicateur est placé dans le registre d'indicateurs de la mémoire 10 de la manière précédemment décrite. Ensuite on aboutit en C10 sur la figure 14C et on passe 30 à l'étape 930 de la figure 14D. Puisque la commande de recherche existe, on passe de nouveau à l'étape 931. Le déroulement des cycles du procédé des figures 14D, A, B et C se poursuit, chaque cycle localisant le bloc au niveau inférieur suivant dans l'index à plusieurs niveaux. L'étape 931 examine toujours l'état du registre de niveaux 35 268 sur la figure 12, fourni par le multiplet de drapeau dB niveau dans le dernier bloc lu qui ne représente pas nécessairement le niveau du bloc à adresser par l'indicateur qui se trouve actuellement dans le registre d'indicateurs de la mémoire 10. Ainsi, c'est seulement une fois qu'un bloc de niveau bas (L1) a été lu que le registre de niveau 268 indique le niveau bas pour l'étape 40 931 de sorte que, il peut signaler que le bloc de niveau de données L0 est 70 17710 25 2047949 représenté par l'indicateur qui se trouve actuellement dans le registre d'indicateur de la mémoire 10. En conséquence, les cycles du procédé de recherche dans l'index à plusieurs niveaux de l'étape 931 à l'étape 921 sont repris tant que l'index à plusieurs 5 niveaux est exploré. La recherche dans l'index à plusieurs niveaux est terminée lorsque l'indicateur LO a été trouvé et est placé dans le registre d'indicateurs de la mémoire 10, ce qui est signalé lorsque l'étape 931 indique le niveau bas. On passe alors à l'étape 932 qui transfère cet indicateur de la mémoire 10 à l'unité centrale de traitement. L'étape 932 transfère l'indica-10 teur trouvé pour le bloc de données L0 et le ramène à l'unité centrale de traitement de sorte que cette unité peut rechercher le bloc de données nécessaire qui peut être emmagasiné dans un dispositif I/O qui n'est pas accessible à partir des commandes I/O 530. Par exemple, un tel bloc de données peut être sur une autre commande dans le même canal ou peut être sur un autre 15 canal appartenant à la même unité de traitement où il peut être disponible pour une autre unité de traitement avec laquelle cette unité de traitement peut communiquer dans un système de multi traitement. L'étape 932 est mise en route par la ligne d8 niveau bas 2B6B qui excite un circuit ET 644 (figure 16) qui signale sur la ligne 644A d'exciter les commandes 667 (figure 19) pour 20 démarquer l'adresse du registre d'indicateur et enclencher le basculeur 645 (figure 18) pour permettre à la porte 646 de transférer les multiplets d'indicateur trouvés sur le bus de sortie de la mémoire 14 (figure 15) par.l'in) termédiaire d'un circuit OU 647 sur la figure 18 au bus d'entrée 647A et aux commandes d'interface 512 de la figura 8 qui transmettent l'indicateur 25 à l'unité centrale de traitement. Le décodeur 666 (figure 19) indique par un signal de sortie sur la ligne 666C lorsque le transfert a atteint la fin du champ du registre d'indicateur. La ligne 666C excite alors le circuit ET 648 (figure 18) pour obtenir 1b signal C.E. & D.E. qui indique la fin de l'opération de recherche. 30 Lorsque l'étape 933 (figure 14D) fournit le signal C.E. S D.E. à partir de la ligne 649A, l'unité centrale de traitement envoie des signaux sur la ligne d'"état accepté" 512D par l'intermédiaire des commandes d'interface 512 (figure 8). Ceci termine l'opération de recherche'. C'est ensuite à l'unité centrale de traitement de rechercher le bloc de données et de vérifier si 35 ce bloc est le bloc ayant l'argument de recherche comme clé, ou si l'argument de recherche n'est pas dans l'index. Recherches jà niveau: Une recherche peut être réalisée (1) séquentiellement dans tout un niveau en explorant tous les blocs du niveau unique, ou (2) en faisant une recherche 40 binaire dans un niveau ou C3) en faisant une combinaison de (1) et (2). Dans 70 17710 26 2047949 tous les cas on utilise !bs commandes "recherche dans un niveau", mais différents indicateurs sont fournis pour l'étape 911, Pour une recherche séquentielle, le premier indicateur dans l'étape 911 adresse le premier bloc au début du niVBau à explorer qui peut être un niveau quelconque dans un index à plu-5 sieurs niveaux, tel qu8 représenté sur la figure 6. Le niveau introduit est exploré en série d'un bloc à l'autre jusqu'à ce que l'on trouve la clé correcte qui est transférée à l'unité centrale de traitement 511. C'est à cette unité centrale de traitement 511 d'emmagasiner cet indicateur, tel que dans le registre 1 CPU dans la mémoire 510 figure 7A. 10 Dans le cas (2) de la recherche binaire, l'indicateur pour le bloc moyen dans le niveau est d'abord utilisé par l'étape 911. Dans le cas (3) d'une recherche binaire partielle suivie par une recherche séquentielle complémentaire, le dernier bloc dans la recherche binaire peut être utilisé pour déterminer l'indicateur commençant et le nombre de blocs restant dans lequel doit 15 être effectué la recherche dans la petite partie du niveau un> misB de c6té par la recherche binaire pour la recherche séquentielle ultérieure. Ces trois cas de recherche dans un niveau réalisé par les circuits décrits nécessitent différents procédés de recherche par table par l'unité centrale de traitement. Ces procédés de rechsrche sont déjà anciens et par conséquent 20 ne seront pas décrits en détails ici. Dans le cas de la recherche séquentielle dans un niveau, les indicateurs dans la table d'indicateurs sont recherchés séquentiellement par le programme de recherche par table pour délivrer l'indicateur pour le bloc suivant au niveau un. Dans le cas de la recherche binaire partielle suivie par une recherche séquentielle partislle dans un niveau, 25 deux programmes de recherche par table sont utilisés, le résultat de la localisation des indicateurs de la rechercha binaire étant transmis au début de la recherche séquentislle partiells. Le transfsrt des paramètres d'un programme à un autre est une technique ancienne dans les ordinateurs. La mise en route de la recherche à un niveau est réalisée en amorçant 30 le programme de recherche par table nécessaire pour obtenir l'indicateur correct et demander la commande de recherche 512, 513, 516 et 530 représentée sur la figure 7A, qui réalise alors la recherche réelle dans l'index sur les dispositifs I/O 530C. Une recherche à un niveau peut être réalisée dans un niveau quelconque 35 d'un index à plusieurs niveaux comportant plusieurs blocs au niveau le plus haut ou à des niveaux inférieurs. Une rechercha dans un niveau est terminée quand on a trouvé l'indicateur correct dans ce niveau. Il est important de remarquer que la recherche dans un niveau permst d'effectuer des recherches avec un niveau supérieur comportant plusieurs 40 blocs. Le niveau supérieur peut être engendré avec plusieurs blocs si un 70 17710 27 2047949 nombre fixe de niveaux est imposé dans l'index à plusieurs niveaux. La recherche dans un niveau augmente aussi la fiabilité de la recherche en éliminant les erreurs dans les niveaux supérieurs. Dans ce cas on peut utiliser la recherche à un niveau pour passer à un niveau inférieur au niveau 5 qui comporte un défaut. On n'a alos besoin d'aucune information provenant des niveaux supérieurs. A la fin d'une recherche à un niveau dans un niveau haut quelconque, c'est-à-dire au-dessus du niveau bas CL1), on peut amorcer une recherche à plusieurs niveaux avec l'indicateur trouvé par la recherche à un niveau, pour 10 localiser un bloc du niveau de données LO cherché. Dans tout type de recherche à un niveau, séquentiel ou binaire, la rechercha se termine lorsqu'on lit un indicateur entre les premier et dernier indicateurs dans un bloc soumos à la recherche, ce qui se produit lorsqu'une clé comprimée dans le bloc entre la première clé CK et la dernière clé CK 15 CP30) est égale à l'argument de recherche. Le procédé Bst plus complexe si le premier ou le dernier indicateur est lu à partir du bloc en cours de recherche. Chaque bloc dans l'index est engendré de sorte que sa dernière clé CK (P^O), pas de multiplet K at associé au dernier indicateur dans le .bloc) 20 sont supétieur à l'argument de recherche. Pendant une recherche le dernier indicateur du bloc exploré est lu et envoyé au registre d'indicateur dans la mémoire 10 si aucun autre indicateur n'est lu à partir du bloc. Dans une recherche séquentielle, le dernier indicateur lu indique que la recherche doit se poursuivre dans le bloc suivant pour déterminer: [1) 25 si ce dernier indicateur peut indexer correctement l'argument de recherche, (2) si il faut poursuivre la recherche pour trouver l'indicateur correct. Dans une recherche binaire, la recherche doit se poursuivre si le premier ou le dernier indicateur d'un bloc est lu jusqu'à ce que C1) le dernier niveau de sa recherche binaire soit atteint auquel cas, le dernier indicateur est 30 correct, soit C2) deux indicateurs adjacents dans deux bloc adjacents ordonnés différents sont lus auquel cas l'unité CPU doit déterminer lequel est correct. La figure 14G représente le cas particulier (2) dans le dernier paragraphe ou le cas (1) de l'avant dernier paragraphe, qui peut se produire dans une recherche à un niveau. Cela se produit lorsque la première clé CK d'un 35 bloc suivant CN+D à l'intérieur du.niveau est égal à l'argument de recherche. Dans ce cas, la recherche dans un. niveau se termine, l'unité centrale de traitement emmagasinant deux indicateurs, qui sont les derniers indicateurs du bloc antérieur N et le premier indicateur du bloc en cours (N=1)« Ensuite chaque indicateur peut Stre utilisé pour amorcer une~recherche à plusieurs 40 niveaux des niveaux inférieurs pour rechercher un bloc du niveau de données 70 17710 28 2047949 respectif, LO. Une comparaison de vérification de l'argument de recherche avec le champ de clé dans chaque bloc LO retrouvé détermine lequel est correct. Naturellement, si le premier bloc LO retrouvé est trouvé correct, la recherche à plusieurs niveaux utilisant le second indicateur devient superflue. 5 On va donner ci-dessous un tableau des conditions à la fin d'un bloc en cours de recherche: TABLEAU Condition Lecture Indicateurs Signaux indiquant Condition Condition Fin Recherche 10 (1) dernier indicateur C.E. & D.E. Lecture bloc suivant (2) indicateur intermédiaire S.M. 8 C.E. S D.E. Indicateur en cours correct (3) premier indicateur ATTN. 8 C.E. 8 D.E Indicateur en cours correct 15 (4) deux indicateurs ambigûs S.M. 8 ATTN. S C.E. 8 D.E. Indicateur en cours ou dernier indicateur correct 15 (5) fin de fichier (plus d'indicateur en cours). U.E. 8 C.E. 8 D.E. Dernier indicateur correct Recherche Séquentielle £ uri niveau: Une recherche séquentielle à un niveau est amorcée à l'étape 910 de la figure 14D de la mSme manière qu'est amorcée la recherche à plusieurs niveaux par exemple, en enfonçant un bouton de mise en route ou en exécutant 20 une instruction de liaison. La mise en route d'une recherche sélectionne l'unité de commande et excite la ligne 512F pour restaurer le basculeur de premier bloc 660a (figure 19). L'étape 911 suit de la manière décrite précédemment, sauf que l'indicateur pour chaque itération par l'étape 911 pendant qu'une recherche séquentiel-25 le dans un niveau est obtenue à partir de la table d'indicateurs sur la figure 7C pour le niveau sélectionné. Le premier indicateur dans la table d'indicateurs sélectionné adresse le premier bloc dans le niveau de l'index dans lequel est effectuée la recherche. L'ordre des indicateurs dans chaque table d'indicateurs représente la séquence ordonnée des blocs à l'intérieur d8s 30 niveaux respectifs bien que les emplacements physiques de ces blocs puissent §tre quelconques (dans la mesure où ils sont adressés par les indicateurs de la table). Par conséquent l'étape 911 de la figure 14D répond à l'étape 910, l'unité centrale de traitement recherchant et délivrant une commande 70 17710 29 2047949 "écriture argument de recherche et premier indicateur" pour rechercher le premier indicateur à partir de la table d'indicateur sélectionnée sur la figure 7C. L'étape 912 est ensuite exécutée par le transfert de l'argument de recher-5 che et de cet indicateur à partir de l'unité centrale de traitement dans le registre d'arguments de recherche et le registre d'indicateur de la mémoire 10. Ensuite l'étape 913 engendre le signal C.E. & D.E. L'étape 940 répond en recherchant une commande "recherche à un niveau" 10 comme commande suivante dans la table de commande de la figure 7A dans une séquence de commandes prédéterminée pour une opération de recherche à un niveau. L'étape 941 suit, le dispositif I/D 530c accédant au bloc défini par le contenu actuel du registre d'indicateur dans la mémoire 10 (de la manière 15 précédémment décrite pour l'étape 921.). Ensuite, l'étape 941a restaure le compteur d'égalité 301 (figure 13) en vue de rechercher le bloc. L'étape 942 est exécutée de la mSme manière que décrite précédemment pour l'étape 922 pour lire le bloc auquel on a accédé au cours de l'étape 941. Ensuite une étape "fin de fichier" (E.O.F) 943 effectue une vérification 20 pour voir si le bloc en cours de lecture a envoyé un signal E.O.F. Sinon, on aboutit à l'étape D12 qui conduit à l'étape 840 de la figure 14A afin de rscherchsr le bloc en cours lu par l'étape 942. Mais si il existe un signal EOF, on obtient le signal LJ.E. par l'étape 943a et l'opération de recherche à un niveau se tsrmine. Dans le dernier cas 1'indicateur correct est le dernier 25 indicateur du bloc antérieur lu et envoyé à l'unité centrale de traitement pour obtenir la condition (5) dans le tableau précédent. A la fin d'une recherche en série d'un bloc (EOF) par le procédé des figures 14A, B st C, on aboutit à C10 sur la figure 14C et on passe à l'étape 930 sur la figure 14D pour vérifier si la commande en cours est uns commande 30 "recherche" ou non. Sinon, c'est une commande "recherche à un niveau™ qui est la commande restante.des deux choix dans l'étape 930. Pour une commande "recherche à un niveau" on aboutit en D11 qui conduit à l'étape 926 sur la figure 14E. Le procédé de la figure 14E consiste à rechercher les premières et der-35 nières conditions CK. dans le bloc lu actuellement y compris le cas particulier précédemmsnt msntionné Bn es qui concsrne la figure 14G. L'étape 926 détermine si le damier indicateur du bloc en cours est lu et l'étape 928 détermine si le premier indicateur du bloc en cours est lu. 11 faut deux-itérations dans D11 (une pour chacun des deux blocs séquentiels) avant que l'on puisse 40 déterminer si la première clé CK est haute pour le bloc en cours et si la 70 17710 30: 2047949 10 20 dernière clé CK. est haute pour le bloc antérieur. Chaque fois que l'indicateur lu résulte d'un clé CK haute à l'intérieur du bloc, c'est-à-dire ne résulte pas de la première et dernière clé CK haute, l'étape 928 introduit E12 pour faire passer à l'étape 956 (figure 14F). l'étape 956 transfère à l'unité CPU 511 le contenu du registre d'indicateurs dans la mémoire 10 et l'étape 957 envoie le signal S.M. & C.E. & D.E. pour terminer l'opération de recherche dans un niveau représentée par la"condition (2) du tableau précédent. Si l'étape 926 trouve que le dernier indicateur du bloc en cours est lue elle fait passer à l'étape E13 qui conduit à l'étape 950 de la figure 14F. L'étape 950 répond en transférant le dernier indicateur provenant du registre d'indicateurs dans la mémoire 10 à l'unité CPU, comme représenté sur la figure 14G. Ensuite, l'étape C.E.,& D.E. 951 est exécutée; elle se produit seule pour chaque bloc qui n'a pas de clé CK supérieure à l'argument 15 de recherche, c'est-à-dire dans lequel seule la dernière clé CK P=0 est supérieure. Ceci remplit la condition (1) dans le tableau précédent. Ensuite l'étape 952 est introduite pour déterminer si la recherche à un niveau en cours est séquentielle ou binaire. Si elle est séquentielle, l'étape 953 est introduite pour accéder à l'indicateur suivant dans la table d'indicateurs à un niveau pour accéder au bloc suivant. La sortie F10 provoque la répétition des étapes 911-913 et 940-943 sur la figure 14D, l'étape 911 délivrant la commande "d'écriture argument de recherche" et premier indicateur". L'étape 912 provoque le transfert du même argument de recherche (la recherche n'est pas terminée) et du nouvel indicateur auquel on a accédé par l'étape 953. L'étape 940 redélivre la commande "recherche à un niveau" provoquant la lecture du bloc suivant par l'étape 942 sur la figure 14D. Ensuite, si on n'atteint pas de fin de fichier, le procédé des figures 14D, A B et C est repris pour conduire à C10 qui ramène à l'étape 930 sur la figure 14E et on aboutit en D11 pour passer à l'étape 926 sur la figure 14E. Si le bloc en cours de lecture est un premier indicateur, l'étape 926 répond négativement et introduit l'étape 928. Le bloc antérieur provoquant la lecture de ce dernier indicateur a pas d'effet sur l'étape 926 pendant le bloc en cours. Ainsi, l'étape 928 détecte si le premier indicateur est lu à partir du bloc en cours. Si oui on passe à E14 qui conduit à l'étape 958 sur la figure 14E pour déterminer si le bloc en cours est le premier bloc dans l'index à un niveau. Si oui le premier indicateur est l'indicateur correct et l'étape 960 est introduite pour le lire à partir du registre indicateurs et l'introduire dans la mémoire 10 à l'unité centrale de traitement CPU. Ensuite, l'étape 961 envoie le signal ATTN. & C.E. & D.E. et l'étape" 962 indique négativement l'existence d'une recherche séquentielle. L'étape 964 suit pour 25 30 35 40 70 17710 31 2047949 indiquer que le signal S.M. n'a pas été indiqué de sorte que l'unité centrale de traitement fait que la condition (3) dans le tableau précédent existe. Alors, la recherche à,un niveau est terminée. Si la condition précédente n'est pas remplie, l'étape 959 envoie le 5 signal S.M. pour indiquer que le bloc en cours n'est pas le premier bloc de l'index. Ensuite, l'indicateur correct est soit le premier indicateur lu, soit le dernier indicateur du bloc antérieur. Ensuite, au cours de l'étape 960 le premier indicateur est extrait de la mémoire 10 et envoyé à l'unité centrale de traitement. Le signal S.M. fait que l'unité centrale de traitement 10 emmagasine le nouvel indicateur dans la mémoire 510 tel que dans le registre-2 de l'unité centrale de traitement. L'étape 9B1 envoie alors le signal ATTN. 8 C.E. 8 D.E.. L'unité centrale de traitement a alors suffisamment d'informations par l'intermédiaire des étapes 962 et 964 pour exécuter l'étape 963 et terminer l'opération, la condition (4) du tableau est alors remplie. L'opé-15 ration à un niveau se termine à l'étape 964 et l'unité centrale de traitement peut exécuter l'étape 963 en amorçant une recherche à plusieurs niveaux comme décrit précédemment pour chacun des deux indicateurs pour déterminer lequel est l'indicateur correct. Une série particulière de circuits pour obtenir le procédé séquentiel 20 de la figure 14D-F est inclus dans les figures 17-19. Les circuits pour les étapes 910-913 ont été décrits précédemment en ce qui concerne les opérations de recherche à plusieurs niveaux. Les circuits pour les étapes 940-943 sont les mSmes que les circuits pour les étapes 920-923 sauf que la ligne 513K du décodeur est excitée au lieu de la ligne 51 3J: La ligne EOF 530E est réservee 25 sur la figure 19 pour envoyer le signal U.E. (dans l'étape 943a de la figure 14D) ce qui termine une recherche séquentielle dans un niveau et fournit les conditions (5) du tableau ci-dessus. Sur la figure 18, un signal C.E. 8 0..E. est obtenu à partir du basculeur 649 lorsqu'il est enclenché soit par (1) la ligne EOF 530E, soit (2) à la 30 fin d'un transfert d'indicateur dans la mémoire 10. Ce signal C.E. 8 D.E. indique à l'unité centrale de traitement qu'elle doit sélectionner la commande suivante dans le tableau de commandes de la figure 7A en fonction des conditions existantes. Le basculeur 649 est enclenché à la fin d'un transfert d'indicateur 35 en conditionnant un circuit ET 648 lorsque la ligne 666C est excitée par le décodeur 666 sur la figure 19 lorsque le dernier multiplet est adressé dans le registre d'indicateurs de la mémoire 10 pendant le signal de commande "de recherche dans un niveau" qui se trouve alors sur la ligne 513K allant • au circuit OU 648a. Une fois que l'unité CPU a accepté 1'indicateur transféré 40 et les signaux d'état, il renvoie les signaux par l'intermédiaire de l'inter 70 17710 32 2047949 face sur la ligne "état accepté" 513D qui restaure le basculeur 649. Le signal C.E. S D.E. peut se produire seul ou en combinaison avec les signaux ATTN., et/ou S.M. au transfert d'un indicateur à l'unité centrale de traitement pour terminer l'exécution d'une commande de recherche dans 5 un niveau. La combinaison particulière de ces signaux indique à l'unité" centrale de traitement comment elle peut traiter l'indicateur reçu. Le tableau précédent donne la signification de chacun de ces signaux allant à l'unité centrale de traitement. Ensuite, l'unité centrale de traitement peut être programmée de façon normale (qui n'est pas décrite ici) pour réaliser l'emma-10 gasinage et l'accès à l'indicateur ou aux indicateurs dans la mémoire 510. Un signal C.E. a D.E. est fourni après chaque transfert d'indicateur à l'unité CPU. S'il n'y a pas de signal ATTN., S.M. ou U.E. à la fin de cette commande à un niveau, alors le signal C.E. 8 D.E. se produit seul et signifie à l'unité centrale de traitement que l'indicateur correct n'a pas été reconnu 15 et que la recherche séquentielle doit se poursuivre en lisant le bloc séquentiel suivant. Cependant si le signal ATTN, S.M., ou U.E. est amené par l'étape 961, 959 ou 943a, ce signal (au lieu du signal C.E. 8 D.E. simultané) commande l'unité centrale de traitement pour ce qui est de l'indicateur transféré. 20 Le signal C.E. et D.E. indique à l'unité centrale de traitement que l'indicateur transféré est le dernier indicateur dans le bloc en cours et que le bloc suivant doit être lu. Le signal U.E. indique la fin du fichier à l'unité centrale de traitement et indique que le dernier indicateur transféré est le dernier indicateur dans l'index à un niveau et que par conséquent il est 25 l'indicateur correct. Les signaux S,H. 8 C.E. et D.E. indiquent que l'indicateur est un indicateur intermédiaire correct. Lorsque les signaux S.M. et ATTN. sont transmis, ils indiquent à l'unité centrale de traitement le cas particulier représenté sur la figure 14G dans laquelle l'indicateur transféré est le premier indicateur du bloc et que soit celui-ci, soit le dernier indi-30 cateur du bloc antérieur adjacent, est l'indicateur correct. L'unité centrale de traitement doit alors amorcer la détermination. La figure 19 représente des circuits pour engendrer les signaux ATTN, SM. et U.E.. Ils sont respectivement engendrés par le circuit ET 664b, le * circuit DU 664c, et la ligne 530K. Les signaux ATTN. et S..M. sont-commandés 35 par des circuits ET 660, 664d, et 664b, chacun étant conditionné par l'excitation de la ligne 513K. et de la ligne du registre de fin d'indicateur 686C'i Le circuit ET 664d engendre le signal S.M. pour l'étape 957, le circuit" ET 664a engendre le signal S.-M. pour l'étape 959, le:circuit ET 664d engendre le signal ATTN. pour l'étape 961 et la ligne 530K engendre 1b signal U.E. 40 pour l'étaps 943a à partir du signal-EOF. 70 17710 33 2047949 Le circuit ET 660 est conditionné par l'anclenchement du basculeur dernier indicateur 661, par la ligne 332A qui est excitée à partir de la figure 13 lorsque le bloc en cours lit son dernier indicateur c'est-à-dire surmonté sur P=0. Le basculeur 661 est restauré par l'excitation de la ligne "état 5 accepté" 512D. Lorsque le circuit ET 660 est conditionné, il enclenche un basculeur "non premier bloc" 660a. Le basculeur 660a est initialement restauré par l'excitation de la ligne de départ au début d'une recherche à un niveau. Le basculeur 661 est enclenché par la clé CK P=Q avec le dernier indicateur du premier bloc si aucune clé CK antérieure n'est supérieure à l'argument 10 de recherche. Cet enclenchement du basculeur 660a indique que chaque bloc dans le niveau n'est pas le premier bloc. Un circuit ET 664a engendre un signal S.M. par l'excitation simultanée du basculeur 660a et du circuit ET 664b "premier indicateur". Le circuit ET 664b est conditionné par l'enclenchement du basculeur "premier indicateur 15 sélectionné" 663 qui est enclenché par l'excitation d'un circuit ET 662. Un basculeur "premier indicateur" 665 commande le conditionnement du circuit ET 662. Le basculeur 665 est enclenché au début du bloc en cours de lecture par le signal d'horloge "multiplet-drapeau longueur d'indicateur" RL CY; et il est restauré par le signal d'horloge lisant le premier indicateur R 20 CY. En conséquence, le basculeur 665 est enclenché pendant le temps où la première clé CK du bloc est comparée à l'argument de recherche. Si la première clé CK est trouvée supérieure à l'argument de recherche, un basculeur "indicateur sélectionné" 328 (figure 13) est enclenché pour exciter la ligne "sélection R" 328A allant au circuit ET 662 de la figura 19. Par suite, l'excitation 25 du circuit ET 662 indique que le premier indicateur (qui va être lu)est l'indicateur à sélectionner et il enclenche le basculeur "premier indicateur" sélectionné 6B3. Ensuite le circuit ET 664b est excité à la fin du transfert de l'indicateur dans le registre d'indicateurs de la mémoire 10 par l'excitation de la ligne 666C. 30 Par conséquent le circuit ET 664a est conditionné par l'excitation du circuit ET 664b lorsque le bloc en cours n'est pas le premier bloc du niveau un. Le fait que le bloc en cours ne soit pas le premier bloc est indiqué par la lecture du dernier indicateur du bloc antérieur qui enclenche le basculeur 660a. 35 En conséquence, le circuit ET 664a envoit les signaux S.M. par l'inter médiaire du circuit OU 664c sur la ligne 664B lorsqu'elle est excitée dans ces conditions pour signaler l'étape 959, de sorte que l'unité centrale CPU fait qu'elle doit examiner les deux indicateurs qui lui ont été transférés en dernier. 40 Un signal sur la ligne 530E provenant des commandes 1/0 530 sur la figure 70 17710 34 2047949 16 indiquB que ls bloc en cours représente la fin du fichisr (EOF). Le signal est amené sur la ligne 530K. aux commandes d'interface 512 (figure 8) pour signaler à l'unité centrale de traitement que le dernier indicatsur du bloc antérieur est le dernier indicateur d'un index à un niveau et que par suita, 5 il ast l'indicateur correct. ' Recherche Binaire £ un niveau: Une autre recherche à un seul niveau à travers les blocs peut être réalisée en utilisant la "recherche binaire". Il faut aussi utiliser la table d'indicateurs de la figure 7C pour le niveau particulier dans lequel est 10 effectué la recherche. Comme on l'a dit précédemment, chaque table d'indicateurs a ses indicateurs disposés dans la séquence ordonnées des blocs représentée par l'indicateur. Les procédés de recherche binaire dans les tables sont bien connus dans la techniqus dss ordinateurs, par suite la recherche binaire est un élément bisn connue utilisée par cette invention. Ainsi, cette 15 recherche ne sera pas décrite en détail ici. La recherche binaire commence aussi avec l'étape de départ 910 de la figure 14D. L'étape 911 est exécutée par la commande "écriture argumsnt de recherche et premier indicateur" sélectionnant l'indicateur moyen à partir du tableau (ou proche de l'indicateur moyen si le tableau a un nombre pair 20 d'indicateurs]. L'étape 912 charge le registre d'indicateur et le registre d'argument de rscharchs dans la mémoire 10 avec cet indicateur et l'argument de recherche nécessaire respectivement. L'étape 940 délivre alors une commande "recherche dans un niveau" et l'étape 941 accède à ce bloc.-L'étape 941a restaure le compteur d'égalité 25 et l'étape 942 lit le bloc pour effsctuer la rechercha lorsqu'on aboutit à l'étape D12 sur la figure 14A. L'étape 943 est sautée dans une recherche binaire car aucun des indicateurs sélectionnés ne représente le bloc de fin de fichier. Une fois que le bloc est recherché par les figures 14A-C, l'étape 930 30 sur la figure 14D est introduite en C10 et on aboutit à D11, puisque la commande de "recherche" n'est pas utilisée. L'étape 926 sur la figure 14E est introduits. Le procédé de la figure 14E est le même pour la recherche binaire que pour la recherche séquentielle. 35 Chaque fois que l'indicateur en cours de lecture ast un indicateur inter médiaire (ce n'est ni le premier, ni le dernier indicateur dans le bloc) l'indicateur lu est correct et la recherche se termine en introduisant E12 sur la figure 14F qui agit de la mSme manière qu'expliquée précédsmmBnt pour la racherche séquentielle. Ceci remplit la condition (2) dans le tableau 40 précédent. 70 17710 35 2047949 Cependant, si ni le premier ni le dernier indicateur n'est lu par le bloc en cours [condition (1), (3), ou (4) du tableau) on passe aux étapes E14 ou E13 respectivement sur la figure 14F pour continuer la recherche binaire. Il résulte de la lecture d'un premier indicateur, le signal ATTN. 8 C.E. 5 8 D.E.. La lecture d'un dernier indicateur donne le signal C.E. 8 D.E. seul. La lecture du premier ou dernier indicateur fait un choix entre les deux indicateurs disponibles dans le niveau suivant de la recherche binaire. L'algorithme de recherche binaire bien connu choisit le couple suivant disponible d'indicateurs. Une lecture du.premier indicateur choisit l'indicateur 10 suivant disponible dans la partie supérieure du tableau pour sélectionner un bloc de niveau inférieur dans l'index. La lecture d'un dernier indicateur choisit l'indicateur suivant disponible dans la partie inférieure du tableau pour sélectionner un bloc de niveau supérieur dans l'index. Le procédé est repris pour le bloc sélectionné suivant qui devient alors 15 le bloc actuel. Chaque niveau suivant de la recherche binaire se rétrécit du nombre maximum de blocs qui doit encore être à rechercher. Ce nombre maximum M est 1/2 du nombre total de blocs dans le niveau recherché, M étant le niveau binaire actuel de la recherche. Ainsi, M est égal à 1 au début de la recherche binaire et il est augmenté de 1 chaque fois que l'on accède à un nouvel indi-20 cateur pour la recherche binaire. Ainsi, le nombre maximum de blocs dans le niveau devant être recherché diminue exponentiellement au fur et à mesure que le niveau binaire M augmente. Si l'étape 926 trouve que le dernier indicateur du bloc en cours est lu, elle fait aboutir en E13 qui fait passer à l'étape 950 sur la figure 25 14F. L'étape 950 répond en transférant le dernier indicateur à partir du registre d'indicateurs dans la mémoire 10 à l'unité centrale de traitement comme représenté sur la figure 14G. Ensuite l'étape 951 est exécutée ce qui se produit pour chaque bloc qui n'a pas de clé CK qui est trouvé supérieur à l'argument de recherche, c'est-à-dire seule la dernière clé CK P=0 artificiel 30 est supérieure. Ceci remplit la condition C1) du tableau ci-dessus. . Ensuite l'étape 952 est introduite pour déterminer si la recherche dans un niveau actuel est séquentielle ou binaire. Si elle est séquentielle, l'étape 954a est introduite pour que l'unité centrale de traitement détermine si le bloc en cours (représenté par l'indicateur binaire en.cours) est le dernier 35 bloc dans la recherche binaire en cours. En général, il y a un nombre fixe M de niveaux binaires dans une recherche appliquée au tableau de dimensions W particulières de la figure 7C. Il existe des techniques bien connues pour terminer une recherche binaire. Par exemple, si l'indicateur en cours est le dernier d'un nombre Mt total d'indicateurs utilisés pour effectuer la 40 recherche de l'argument de recherche en cours, l'étape 954a fait passer à ?0 17710 36 2047949 l'étape 955 pour déterminer la condition spéciale représentée sur la figure 14G. Si au cours de l'étape 954a on trouve que moins de -M blocs ont été lus, dans la recherche binaire en cours, l'étape 954b est introduite pour 5 accéder à l'indicateur supérieur suivant Crendu disponible par le programme de recherjhe binaire] qui est supérieur à l'indicateur en cours dans la table d'indicateur. On aboutit à F10 après l'étape 954b. Par suite, une recherche binaire dans un niveau quelconque dans l'index à plusieu as niveaux nécessite entre un et M recherche de bloc pour trouver 10 un indicateur correct. est égal au logarithme à base deux du nombre total de blocs à ce niveau c'est-à-dire L0G2 T. A titre de comparaison, on peut dire que le nombre maximum de recherche de blocs nécessaire dans une recherche séquentielle dans un niveau est situé entre un et T (nombre total de blocs] dans le niveau. Par suite la recherche binaire est en moyenne T/PI^ fois plus 15 rapide que la recherche séquentielle pour une recherche complète dans un niveau. Après F10 les étapes 911-913 et 940-943 sur la figure 14D sont répétées l'étape 911 délivrant la commande "écriture argument de recherche et premier indicateur". Il résulte de l'étape 912 le transfert du même argument de recher-20 che (la recherche n'est pas terminée] et le nouvel indicateur auquel on a accédé par l'étape 953. L'étape 940 redélivre la commande "recherche à un niveau" provoquant la lecture du bloc suivant dans l'étape 942 sur la figure 14D. Ensuite, si l'on atteint pas de fin de fichier, le procédé des figures 14D, A, B et C est repris pour conduire à C10 dans la figure 14C qui ramène 25 à l'étape 930 de la figure 14E et on aboutit en D11 qui conduit à l'étape 926 de la figure 14E. Si la lecture du bloc en cours Bst son premier indicateur, l'étape 926, répond négativement et introduit l'étape 928. Le bloc antérieur lisant son dernier indicateur n'a pas d'effet sur l'étape 926 cependant que le bloc en cours. 30 Ainsi, l'étape 928 détecte si le premier indicateur est lu à partir du bloc en cours. Si oui, on aboutit à l'étape E14 qui conduit à l'étape 958 sur la figure 14E. La détermination par l'étape 958 du fait que le bloc en cours est le premier bloc dans ce niveau d'index est ignorée dans cette recherche binaire, c'est-à-dire, le fait qu'un signal S.M. est engendré par 35 l'étape 959 est ignoré puisqu'il ne fait pas de différence avec la recherche binaire dans laquelle, on passe de l'étape 958 pour atteindre l'étape 960. qui lit l'indicateur dans le registre d'indicateur et l'introduit-dans la mémoire 10 à l'unité centrale de traitement. Ensuite l'étape 961 envoie les signaux ATTN. et C.E* & D.E., et l'étape 40 962 doit indiquer positivement l'existence d'une recherche binaire.•L'étape 70 17710 37 2047949 966 suit et est exécutée de la même façon que l'étape 954a pour déterminer si le bloc en cours est le dernier dans la recherche binaire en cours. Si non on passe à l'étape 967 pour accéder à l'indicateur inférieur suivant Crendu disponible par 1b programme de recherche binaire) qui est inférieur 5 à l'indicateur actuellement dans la table d'indicateur. On aboutit ensuits à F10 pour rechercher le bloc suivant dans le nivsau. Si l'étape 966 fait passer à l'étape 955, l'opération décrite précédemment pour la condition "oui* après l'étape 954a est obtenue. Une série particulière de circuits permattant de réaliser le procédé 10 de recherche représenté sur lss figures 14D-F est représentée sur les figures 17-19. Les circuits pour les étapes 910-913 ont été décrits précédemmsnt pour les opérations de rechercha à plusieurs nivsaux. Les circuits pour les étapss 940-943 sont las mêmes que les circuits des étapes 920-923, sauf que la ligne 513K du décodeur est excitée au lieu ds la ligne 513J. 15 Sur la figure 18, un signal C.E. & D.E. est amené à partir du basculeur 649 lorsqu'il est snolenché à la fin d'un transfert d'indicateur dans la mémoire 10. (La condition "fin de fichier" n'est pas utilisée pendant une recherche binaire)■ Le signal C.E. S D.E. indique à l'unité centrale de traitement qu'il 20 doit sélectionnsr la commande suivante dans le tableau de commande de la figure 7A en fonction des conditions existantes. Le basculeur 649 est enclenché à la fin d'un transfert d'indicateurs en excitant un circuit ET 648 lorsque la ligne 666C est excitée par le décodeur 666 sur la figure 19 lorsque la dernier multiplet est adressé dans le regis-25 tre d'indicatsurs ds la mémoire 10 pendant le signal de commande actuel "recherche à un niveau" sur la ligne 513K. allant au circuit OU 648a. Une fois que l'unité centrale de traitement CPU a accepté l'indicateur transféré et lss signaux d'état, il renvoie les signaux par 1'intermédiaire de l'interface sur la ligne "état accepté" 513D qui restaure le basculeur 649. 30 Le signal C.E. S D.E. peut se produira seul ou avec las signaux ATTN., et/ou S.M. au transfert d'un indicateur à l'unité centrale de traitement pour terminer l'exécution d'une commande de recherche à un niveau. La combinaison particulière des signaux indique à l'unité centrale de traitement comment elle doit traiter l'indicateur reçu. Le tableau précédent donne la 35 signification de chacun de ces signaux à l'unité centrale de traitement. La programmation normale non décrite ici peut être fournie à l'unité centrale de traitement pour traiter l'emmagasinage et l'accès de l'indicateur pu des indicateurs dans la mémoirs 10. Ainsi, un signal C.E. & D.E. sst obtenu après chaque transfert d'indica-40 teur à l'unité centrale de traitement. Si aucun signal ATTN ou S.M. n'est 70 17710 38 2047949 fourni à la fin de cette commande à un niveau alors le signal C.E. & D.E. se produit seul ce qui indique à l'unité centrale de traitement que l'indicateur correct n'a pas été identifié et que la recherche binaire doit se poursuivre en lisant le bloc choisi suivant. 5 Le signal ATTN. & C.E. & D.E., or le signal C.E. S D.E. seul fournit par les étapes 961 ou 951 respectivement commande l'unité centrale de traitement en ce qui concerne l'indicateur transféré. Le signal C.E. S D.E. seul indique à l'unité centrale de traitement que l'indicateur transféré est le dernier indicateur dans le bloc en cours et qu'un bloc de niveau supérieur 10 dans l'index doit être lu puisque le dernier indicateur n'est pas nécessairement l'indicateur correct. Le signal ATTN. indique que le premier indicateur est lu dans le bloc en cours et qu'un bloc de niveau inférieur dans l'index doit être lu puisque le premier indicateur n'est pas nécessairement correct dans une recherche binaire. Ce bloc suivant est choisi à partir des deux 15 blocs (un supérieur et un inférieur au bloc en cours) rendu disponible par le programme de recherche binaire précédemment décrit. La figure 19 représente les circuits pour engendrer le signal ATTN. Il est engendré par le circuit ET 664b comme décrit précédemment dans le paragraphe intitulé "recherche séquentielle à un niveau". 20 Recherches Binaire et Séquentielle combinées. Une recherche à;un niveau peut être parfois plus efficace lorsqu'elle est effectuée par une combinaison des techniques de recherche binaire et séquentielle. Etant donnée la nature exponentielle de la recherche binaire elle est particulièrement efficace aux niveaux initiaux et diminue le nombre 25 maximum restant de blocs dans le niveau qui peut être exploré. Vers la fin de la recherche binaire, elle peut être plus efficace que la recherche séquentielle. Dans un tel cas, la recherche binaire peut se terminer au niveau binaire B, qui a une valeur inférieure au nombre maximum M de niveaux binaires dans une recherche. La valeur M dépend du nombre particulier d'indicateurs 30 dans la table d'indicateurs. Le passage de la recherche binaire à la recherche séquentielle peut Stre commandé par l'unité centrale de traitement lorsqu'elle détecte que les niveaux B de recherche binaire sont terminés. Ainsi, la fraction restante de l'index dans laquelle doit être effectuée la recherche est déterminée par l'indicateur sélectionné dans l'étape 954b ou 967 pendant la recher-35 che dans le dernier niveau binaire B. Cet indicateur localise le milieu de la fraction restante de l'index dans laquelle sera effectué la recherche G séquentielle. La fraction restante comprend 1/2 du nombre de blocs dans le B niveau d'index qui est le même que 1/2 du nombre total T d'indicateurs dans B la table d'indicateurs actuels, c'est-à-dire T/2 . 40 Par conséquent, la recherche séquentielle commencera avec un indicateur 70 17710 39 2047949 qui est au-dessus du dernier indicateur défini par les étapes 954b ou 967, 5 B+ de la moitié de T/2 indicateurs, c'est-à-dire T/2 pendant la recherche dans le dernier niveau binaire B. On peut aussi utiliser les recherches binaire et séquentielle combinées 5 dans l'option (13 de l'étape 955 sur la figure 14F. Ici, la recherche binaire a terminé le dernier niveau M à la fin du processus de recherche comme c'est indiqué par la condition "oui" après les étapes 954a ou 966. L'étape 955 n'est nécessaire que dans le cas particulier où le dernier bloc binaire recherché a lu son premier ou dernier indicateur. L'option (1) amorce alors une 10 recherche séquentielle pour obtenir les deux indicateurs pour la situation représentée sur la figure 14G. Si le dernier indicateur lu est le premier indicateur dans le dernier bloc binaire recherché, une recherche séquentielle dans deux blocs est amorcée avec l'indicateur antérieur adjacent dans la table d'indicateurs [relative à l'indicateur pour le dernier bloc binaire 15 recherché). Si le dernier indicateur lu est le dernier indicateur dans le dernier bloc binaire recherché, une recherche séquentielle dans un bloc est amorcée avec l'indicateur adjacent suivant dans la table d'indicateurs [concernant aussi les indicateurs pour le dernier bloc binaire recherché). 20 L'option (2) pour l'étape 955 accomplit la même fonction en inscrivant l'information recherchée avec chaque indicateur dans la table d'indicateur représentant un bloc recherché pour le m8me argument de recherche. Il y a au moins trois bits avec chaque indicateur, par exemple un bit "recherche faite" un bit "premier ou dernier indicateur" et un bit "recherche terminée". 25 La condition a deux indicateurs de la figure 14G peut alors être détectée en examinant ces bits pour déterminer si les deux indicateurs adjacents ayant leurs bits "recherche faits" à un ont aussi leur bit "premier ou dernier indicateur" à un pour indiquer le dernier indicateur pour un indicateur et le premier pour un indicateur inférieur suivant dans la table. La recherche 30 est alors terminée. Bien que l'on ait décrit dans ce qui précède et représenté sur le dessin, les caractéristiques essentielles de l'invention appliquées à un mode de réalisation préféré de celle-ci, il est évident que l'homme de l'art peut y apporter toutes modifications de forme ou de détail qu'il juge utiles, 35 sans pour autant sortir du cadre de ladite invention. 70 17710 2047949 REVENDICATIONS 1.- Dispositif pour rechercher un argument dans un index à plusieurs niveaux ayant un premier format pour les niveaux élevés, dans lequel une paire de clés comprimées est associée à un indicateur, et un second format pour le 5 niveau bas, dans lequel une seule clé comprimée est associée à un indicateur, caractérisé par la combinaison des éléments suivants: des moyens pour sélectionner dans l'index un bloc initial de niveau élevé comme premier bloc comprimé soumis à la recherche, des moyens pour lire le contenu dudit bloc, 10 des moyens pour comparer successivement l'argument de recherahe avec les clés des paires de clés comprimées contenues dans ledit bloc, dans l'ordre où elles sont placées, des moyens pour retrouver l'indicateur associé à une paire de clés comprimées lorsque l'une des clés de la paire est reconnue plus "haute" que l'argu-15 ment de recherche, et pour arrêter alors les comparaisons, et des moyens pour transférer à une unité de traitement de données l'indicateur ainsi eetrouvé pour accéder à un bloc de niveau immédiatement inférieur adressé par ledit indicateur. 2.- Dispositif selon la revendication 1, caractérisé en outre en ce que, si 20 ledit bloc de niveau immédiatement inférieur est du premier format, lesdits moyens de lecture, comparaison, et transfert agissent sur ledit bloc de la même façon que svjç\ le bloc initialement soumis à la recherche. 3.- Dispositif selon la revendication 1, caractérisé en outre en ce que, si ledit bloc de niveau immédiatement inférieur est du second format, lesdits 25 moyens de lecture, comparaison et retrouvaille effectuent les opérations suivantes: restauration du compteur à son état initial, lecture du contenu dudit bloc, comparaisons successives de l'argument de recherche avec les clés compri-30 mées contenues dans ledit bloc, reconnaissance de l'indicateur associé avec une clé copprimée lorsque cette clé est reconnues plus "haute" que l'argument dB recherche et arrêt des comparaisons, cet indicateur adressant le bloc de données cherchées. 4.- Dispositif pour rechercher un argument par une recherche dans un niveau 35 d'un index à plusieurs niveaux en utilisant une table d'indicateurs dans laquelle les adresses des blocs de ce niveau sont rangées dans un ordre 70 17710 41 2047949 déterminé, caractérisé par la combinaison des éléments suivants: des moyens pour commander la sélection des indicateurs dans ladite table, chaque nouvelle sélection d'un indicateur étant une réponse à un signal de position d'indicateur d'un type prédéterminé. sélectionné à partir de ladite table d'indicateurs, des moyens pour restaurer un compteur de recherche d'égalité d'argument à un ëtat initial avant d'effectuer la recherche dans ledit bloc, des moyens pour lire le bloc obtenu par lesdits moyens de commande de 10 sélection, des moyens pour comparer l'argument de recherche avec les clés comprimées dudit bloc dans l'ordre déterminé sus-mentionné, des moyens pour incrémenter ledit compteur pour qu'il indique la position du multiplet de l'argument de recherche en cours de comparaison toutes les 15 fois qu'un multiplet de la clé est reconnu égal audit multiplet de l'argument de recherche, des moyens pour indiquer le multiplet suivant de l'argument de recherche comme multiplet en cours de comparaison en réponse à l'action desdits moyens d'incrémentation, 20 des moyens pour retrouver l'indicateur associé avec une clé comprimée la première fois que la comparaison indique qdun multiplet de la clé est "haut" par rapport au multiplet de l'argument de recherche, et des moyens pour créer des signaux de position d'indicateur pour établir un rapport entre l'indicateur ainsi retrouvé et l'emplacement dudit indicateur 25 dans son bloc, 5.- Dispositif selon la revendication 4, caractérisé en outre en ce que lesdits moyens de création de signaux comportent: des moyens paur engendrer un signal de dernière position pour indiquer que l'indicateur retrouvé est le dernier indicateur du bloc, 30 ' des moyens pour engendrer un signal de position intermédiaire pour indiquer que l'indicateur retrouvé est compris entre le premier et le dernier indicateur du bloc, des moyens pour engendrer un signal de première position pour indiquer que l'indicateur retrouvé est le premier indicateur d'un bloc. 35 6.- Dispositif selon la revendication 4 ou 5 caractérisé en outre par les éléments suivants: des moyens pour sélectionner le bloc suivant adressé par l'indicateur suivant de la table d'indicateur en réponse à l'action desdits moyens de 5 des moyens pour sélectionner un bloc adressé par un premier indicateur 70 17710 42 2047949 commande de sélection d'indicateurs répondant auxdits signaux de position d'indicateur, et des moyens pour commander la répétition de l'action desflits moyens de restauration lecture, comparaison, incrémentation, retrouvaille et création 5 de signaux pour ledit bloc suivant. 7.- Dispositif selon la revendication B, caractérisé en outre par des moyens pour détecter une forme prédéterminée des signaux de position d'indicateur pour reconnaître une fin de recherche, et des moyens pour actionner lesdits moyens de commande de répétition 10 jusqu'à ce que cette fin de recherche soit détectée.