B-Tree : fichiers indexés (ISAM - Arbre B)

Toute ma carrière s'est faite avec des applications s'appuyant sur des données en quantités illimitées et en vitesse d'accès constante, en insertion, comme en extraction, comme en suppression, et ce avec un nombre quelconque d'utilisateurs accédant aux mêmes données simultanément (adjonctions, modifications, suppressions, etc.).

Les systèmes de gestion de ces immenses quantités de données étaient les systèmes de gestion de bases de données ou des fichiers indexés utilisant l'ISAM et la technique des structures en arbres B (B-Tree).

Tout est sur disque et seule monte en mémoire la donnée sur laquelle on travaille (un compte client, une fiche article, une écriture comptable, etc. ...)

La structuration des données en arbre-B fut inventée en 1971 par Rudolf Bayer et Edward M. McCreight. Ils étaient employés, à l'époque, par la firme Boeing. Bayer étant l'ainé et le chef de projet et le mot " Boeing " ne pouvant être utilisé pour cause de marque déposée, ce fut la lettre " B " qui fut retenue pour nommer cette arborescence (explication donnée par Edward M. McCreight le 17 juin 2013 au 24e CMP - CPM 2013 : 24th Annual Symposium on Combinatorial Pattern Matching, Bad Herrenalb, Germany).

Quelle ne fut pas ma surprise, en abordant la micro-informatique sous MS-DOS puis sous Windows, de m'apercevoir que les fichiers n'ont aucune structure interne ni système de gestion des données et que, pour faire semblant d'aller vite alors que les données ne sont pas indexées, mais balayées séquentiellement, les fichiers montent en entier en mémoire RAM (d'où l'écroulement de la mémoire) !

Au début de ma carrière, la RAM coûtait une fortune et les données organisées d'un fichier se comptaient en millions d'enregistrements, dizaines de millions, centaines de millions. Pourtant, il y a 30 ans, nous allions plus vite qu'aujourd'hui. Il n'y avait jamais d'écroulement des temps de réponse avec ces gigantesques réservoirs de données. Lorsque nous étions dans une entreprise riche, nous pouvions atteindre des tailles RAM gigantesques de... 128 KO de ram et des programmes écrits en Fortran ou en Cobol montaient en mémoire pour gérer ces gigantesques fichiers d'une banque, d'une compagnie d'assurance, etc. ... avec des dizaines d'utilisateurs connectés simultanément sur le même programme et les mêmes fichiers.

Aujourd'hui, avec des monstres de RAM, de processeurs, de disques, etc. pour un unique utilisateur devant son unique poste de travail, tout rame et se traîne ! C'est la fuite en avant du matériel. Mettons à part les données par nature non structurées ou peu structurées, comme les documents texte. Les tableurs manipulent des données fortement structurées, mais calculer une inversion de matrice avec quelques millions d'accès disque prendrait un peu plus de temps !

Les structures en arbres-B (B-Trees) sont toujours utilisées et sont, par exemple, les structures de données et leurs indexations sous-jacentes dans les systèmes de gestion de bases de données relationnelles comme :

• Oracle : le moteur commercial de gestion de bases de données (le SGBD le plus utilisé au monde dans les grands comptes)

• mySQL : (la Base de Données Open Source la plus populaire au monde et le second SGBD au monde - c'est le SGBD sur lequel repose notre forum)

• Microsoft SQL Server : (troisième moteur de SGBD le plus utilisé au monde).

1. Three Reasons for Using B-Tree Indexes, Intuition, Properties, find, ISAM, find_range

2. Vidéo : principe de fonctionnement d'un B-Tree

3. Wikipedia (en) : B-Tree

4. Wikipedia (fr) : B-Tree (Arbre B)

5. Using B-Tree Indexes - When to use B-Tree Indexes (Indexes in Oracle-1)

6. Using B-Tree Indexes - When to use B-Tree Indexes (Indexes in Oracle-2)

7. Using B*Tree Indexes - When to use B*Tree Indexes (Indexes in Oracle-3)

8. Animations B-Tree (ce site date de 2005 - Le durcissement actuel de la sécurité Java ne permet plus d'utiliser la version mise en ligne de cette applet Java. C'est en découvrant cette applet, il y a des années, que j'ai eu l'idée de parler des B-Tree (arbres-B) que j'ai tant utilisés.

9. Java