Alertes de sécurité en cours Discussion Discussion
Faire un lien Lien
Assiste.com - Sécurité informatique - Décontamination - Antivirus - Protection - Protection de la Vie Privée Assiste.com - Sécurité informatique - Décontamination - Antivirus - Protection - Protection de la Vie Privée

B-Tree (Arbre B) ISAM

Dernière mise à jour : 2017-04-28T00:00 - 28.04.2017
01.04.2012 - 00h00 - Paris - (Assiste - Pierre Pinard) - Mise à jour de notre article antérieur (versions 1997-2007)

B-Tree (Arbre B) ISAM - Structure de données à accès rapide et vitesse constante quelque soit la quantité de données.

B-Tree (arbre B - fichiers indéxés à accès rapides - ISAM)B-Tree (arbre B - fichiers indéxés à accès rapides - ISAM)B-Tree (arbre B - fichiers indéxés à accès rapides - ISAM)

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 quelconques d'utilisateurs accédant aux mêmes données simultanément (modification / suppression ...).

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 24ème 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).

Chargement...

Animation B-Tree par rationalpsychedelia sur Youtube en utilisant l'applet Java de Slady

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

Sécurité informatique - Comment je me fais avoir - Comment ne pas me faire avoirSécurité informatique - Comment je me fais avoir - Comment ne pas me faire avoirSécurité informatique - Comment je me fais avoir - Comment ne pas me faire avoir

Contre mesuresContre-mesures" Contre mesures "

Derrière le rideauDerrière le rideauDerrière le rideau

RéférencesRéférences" Références "

RessourcesRessources" Ressources "

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)

 Requêtes similairesRequêtes similaires" Requêtes similaires "