Dans les années 77-78. L'histoire d'arbres qui cachent une forêt. 1977. C'est cette année-là qu'apparaît le premier Apple II, dont je fus l'un des tous premiers importateurs en France. L'Apple comportait une alim 110V. A cette période, il existait encore quelques habitations en 110V à Paris! Le carton d'emballage ouvert, on pouvait brancher l'unité centrale, sans acheter un transformateur 220/110. Il fallait songer à acquérir un écran vidéo L'Apple II était concurrencé par le Pet puis le CBM de Commodore, entre autres. Mais surtout, l'Apple II pouvait recevoir, à partir de l'année 1978, un lecteur de disque souple, d'une capacité de 116K, et un interpréteur BASIC permettant d' exploiter ce nouveau dispositif de stockage.
Pour vendre cette machine, il fallait l'équiper d'un minimum de composants applicatifs, et en premier lieu d'un système de gestion de fichiers, permettant à des sociétés de réaliser des applications de gestion classique: paye, comptabilité, gestion commerciale. Je commençai par mettre au point un système permettant de gérer des fichiers directs, en imposant des clés numériques correspondant à des numéros relatifs d'enregistrement. Les performances, en accès direct étaient tout à fait raisonnables.
Mais , très vite ce système apparu très contraignant, en particulier dans des contextes de gestion comptable: un numéro de compte du plan comptable ne peut pas être remplacé par un numéro d'ordre quelconque. Je dus donc passer à une autre technique: celle du hashcode.
Le hashcode permet d'associer à un indicatif, par le biais d'une fonction appliquée à cet indicatif, un numéro relatif d'enregistrement. Cette technique présentait un grand intérêt: elle faisait l'objet de nombreuses recherches, et celles-ci pouvaient donc être mises en œuvre immédiatement, moyennant un investissement en temps de compréhension et d'expérimentation, en particulier pour la gestion des synonymes. . Le succès fut immédiat. Je pouvais désormais offrir un système permettant d'utiliser, en guise de clé d'accès, n'importe quelle rubrique d'un enregistrement de données.
Dans les années 1982, en feuilletant mes supports de cours, je redécouvrais une bibliographie comportant les ouvrages de Knuth (The art of computer programming), et la référence à des publications de Rudolf Bayer et E. McCreight (Organization and Maintenance of Large Ordered Indexes -Acta Informatica, Vol. 1, Fasc. 3, 1972 pp. 173-189) sur une théorie: les arbres binaires, le B-tree. c'est exactement ce qu'il me fallait. Je passai des nuits entières à m'imprégner de cette théorie et commençais à expérimenter des implémentations possibles. La suppression des enregistrements était très délicate à appréhender. Les temps de réponse effectifs pour une application commerciale étaient inacceptables. L'analyse du code montrait de nombreux accès disque, non pas pour l'accès aux données, mais pour l'accès aux index, c'est à dire aux nœuds de l'arborescence B-tree. Je me penchai durant plusieurs semaines sur les algorithmes développés par Knuth et surtout par Rudolf Bayer:. Avoir un fichier d'index dont chaque enregistrement ou page contiendrait plusieurs nœuds ou clés.
C'est alors que j'entrepris de gérer mon arborescence de pages sans me soucier des transferts disque, en mettant en applications les concepts de mémoire virtuelle. Un processus principal manipulerait les pages de clés comme si elles étaient toujours en mémoire. Un autre processus de bas niveau, se chargerait , grâce à un mécanisme de buffer ou mémoire cache circulaire, d'envoyer une page sur disque, ou d'extraire une page à partir du disque, selon la stratégie de la page la moins récemment utilisée(LRU :Least Recently Used pages).
A la fin des années 82-83, mon système était au point. Une première mouture était en Basic. La version mature fut rédigée en C. Les performances étaient surprenantes. L'exploitation du concept de buffer ou cache circulaire doit être très intéressante à exploiter pour implémenter un mécanisme du type "Real Application Cluster" (c) Oracle! Voilà ce que vous trouverez dans cet ouvrage chez Amazon.
Vos remarques, vos idées, vos critiques seront indéfectiblement les bienvenues. Je serai tout particulièrement heureux de voir des lecteurs transposer ce système en C++, et exploiter les environnements 64-bits.
Avec toute ma gratitude.
