Flux RSS - La vie du site - Nouveautés et mises à jour
Assiste.com - Sécurité informatique - Vie privée sur le Web - Neutralité d'Internet Assiste.com - Sécurité informatique - Vie privée sur le Web - Neutralité d'Internet

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

B-Tree (Arbre B) ISAM - structure de données à accès rapide et vitesse constante, quelle que soit la quantité de données. Maintient en temps réel de l'ordre de tri, y compris lors de modifications, adjonctions ou suppressions et de multiutilisateurs.

01.01.2012 - Révision 21.08.2020 - Révision mineure 13.05.2022. Auteur : Pierre Pinard.

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).


# # # # # # # # # # # # # # # # # # # # # # # # # # # #

Dossier (collection) : Vidéos sur Assiste

Cybercriminels - Envoyé Spécial - France2 (fr - 2009 - 47 min)
Aux prises avec la mafia de l'Internet (fr - 2013 - 1 h 16 min 14 s)
NSA - L'agence de l'Ombre - Arte (fr - 2012 - 50 min 19 s)
Quand c'est gratuit, qui paye - France5 (fr - 2018 - 50 mn 40 s)
Arnaque aux faux présidents de sociétés - 1 - France2 (fr - 2015 - 39 mn 16 s)
Arnaque aux faux présidents de sociétés - 2 - BFM (fr - 2015 - 1 mn 18 s)
Arnaque aux faux présidents de sociétés - 3 - Officiel (fr - 2019 - 4 mn 12 s)
Arnaque 419 (Nigéria) à la culpabilité sexuelle - JE (fr - 2015 - 18 mn 01 s)
Cartes de fidélité, fidèle 1 jour, fiché pour toujours - Arte (fr - 2013 - 54 mn 09 s)
Collusion : Traquer les traqueurs - Kovacs (en st fr - 2012 - 6 mn 39 s)
Qu'est-ce qu'Internet 1/3 - Benjamin Bayart (fr - 2010 - 1 h 37 mn 13 s)
Qu'est-ce qu'Internet 2/3 - Benjamin Bayart (fr - 2010 - 1 h 48 mn 59 s)
Qu'est-ce qu'Internet 3/3 - Benjamin Bayart (fr - 2010 - 2 h 01 mn 02 s)
Escroquerie au RSI - Régime Social des Indépendants - TF1 (fr - 2012 - 1 mn 52 s)
Escroquerie au blanchiment d'argent sale - TSR (fr - 2012 - 4 mn 19 s)
Arnaques aux sentiments - escroqueries à la romance amoureuse (fr - 2012 - 1 mn 52 s)
Toute ma vie sur Internet - utilisations de mes données privées - France 2 (fr - 2016 - 35 mn 17 s)
Une contre-histoire de l'Internet - Défense des libertés - Arte (fr - 2013 - 1 h 27 mn 24 s)
AppRemover - désinstallation complète d'applications - OPSWAT (en - 2013 - 2 mn 37 s)
RIOT (Rapid Information Overlay Technology) - Raytheon (en - 2013 - 4 mn 4 s)
Core Wars - vidéo 1 - Joueur : Marco Pontello, l'auteur de TrID (59 s)
Core Wars - vidéo 2 - Joueur : Marco Pontello, l'auteur de TrID (6 mn 3 s)
Core Wars - vidéo 3 - Joueur : Marco Pontello, l'auteur de TrID (1 mn)
La guerre invisible (dont le virus Stuxnet) - Arte (fr - 2012 - 1 h 15 mn)
Fermes de contenu (content farms) - SMX (en - 2011 - 1 h 11 mn - 6 s)
FaceBook, déclare que l'âge de la vie privée est révolu ! - Facebook - (en - 2010 - 6 mn 1 s)
Keylogger acoustique et électroacoustique - LASEC - (en - 2008 - 2 mn 56 s et 2 mn 35 s)
James Gosling, le père de Java, honore Jerry Garcia du Grateful Dead - (1994 - 6 mn 1 s)
Arbres B (B-Trees, ISAM, Indexed Sequential Access Method) - (1 mn 47 s)
Hacker - PIRATAGE (documentaire sur les hackers) - MK2TV (fr - 2011 - 1 h 15 mn 31 s)
Hackers - Ni Dieu, ni Maître (documentaire sur les hackers) - Arte (fr - 2011 - 56 mn 47 s)


Les ressources ci-dessous offrent des vidéos expliquant le principe sur lequel reposent les B-Trees.

https://www.youtube.com/watch?v=RAgCa_IDCNQ

https://www.youtube.com/watch?v=coRJrcIYbF4

http://slady.net/java/bt/ - Le durcissement actuel de la sécurité Java ne permet plus d'utiliser la version actuellement mise en ligne de cette applet Java, qui date de 2005. C'est en découvrant cette applet, il y a des années, que j'ai eu l'idée de parler des arbres-B.

https://en.wikipedia.org/wiki/B-tree

https://fr.wikipedia.org/wiki/Arbre_B

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

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

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