B-Tree (Arbre-B) : technologie d’indexation des données selon une structure à accès rapide et vitesse constante, quelle que soit la quantité de données.

cr  01.01.2012      r+  22.10.2024      r-  22.10.2024      Pierre Pinard.         (Alertes et avis de sécurité au jour le jour)

Les méthodes d’accès rapide aux données enregistrées dans un appareil, lorsqu’il faut en extraire une dans un corpus plus ou moins gigantesque de données stockées sur des unités de mémoire à accès direct (type « disques durs » et tout ce qui, technologiquement, tend à les remplacer, comme les mémoires SSD), passent par une indexation de ces données.

Lorsque vous naviguez sur le Web, vous faites appel à l'un des nombreux moteurs de recherche qui utilisent, tous, des méthodes personnelles pour trouver rapidement et donner d'accès à ce qui est recherché (secrets industriels complexes, avec recherches par approximations et classement par pertinence, exclusions par listes noires et identifications de cybercriminalités [vidéo]...).

Pour une recherche applicative dans des fichiers privés (grands comptes, administrations, entreprises, particuliers...), dont les données contenues sont, par fichier, de même nature et de même format, il existe plusieurs technologies d’accès permettant d'échapper au balayage intégral séquentiel des données jusqu’à la trouver (ce qui donnerait un temps moyen effrayant de balayage de la moitié de chaque base de données et l'exploitation lourde des ressources matérielles) :

1. Le « séquentiel indexé ».
2. L’ISAM.
3. Les B-Tree - (Arbre-B).
4. Les algorithmes de calcul de hashcodes (condensat).

Le but de ces différentes méthodes est le même :

1. Trouver rapidement la donnée recherchée.
2. La trouver au moindre coût (utilisation minimale des ressources matérielles et logicielles).

Les opérations qui doivent être permises et dont les vitesses doivent être optimisées portent, pour un nombre quelconque d'utilisateurs accédant aux mêmes données simultanément (contrôle de concurrence), sur :

1. Insertion de nouvelles données.
2. Extraction de données.
3. Modification (ré-écriture) de données.
4. Suppression de données.

Les fichiers indexés selon la technologie B-Tree (Arbre-B) utilisent un système d'indexation de données à accès rapide et vitesse constante, quels que soient la quantité de données et le nombre d'utilisateurs simultanés. Cela permet de maintenir en temps réel l'ordre de tri et la vitesse d'accès à une donnée recherchée, y compris lors de :

1. Création de nouvelles données (adjonctions).
2. Modifications de données (réécritures).
3. Suppressions de données.
4. Même avec des multitudes d'utilisateurs simultanés.

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

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 - quelle est ma version de Java

10. D.S. Batory (EN, PDF, 10 pages) : B+ Trees and Indexed Sequential Files: A Performance Comparison

11. Assiste.com (FR) : Cache disque - accélération par l'anticipation

12. Qwant (FR) - Modalités de référencement, déréférencement et de classement par le moteur de recherche Qwant.

13. Philippe Rigaux (FR) - Cours de bases de données - Aspects systèmes