L’implémentation des fichiers ISAM : les B-trees

• L’organisation adoptée pour les index est le B-tree qui est une forme d’arbre équilibré optimisé en vue de l’utilisation sur disque.
• Dans un B-tree l’équilibre de l’arbre est maintenu en le réorganisant périodiquement, mais aussi en laissant varier le nombre de successeurs de chaque noeud dans certaines limites.
• Une implémentation optimale sur disque du B-tree utilise des noeuds dont la taille est celle d’un secteur.
• Pour un fichier de n enregistrements, rechercher un enregistrement nécessite un temps O(n) sans index, mais seulement O(log(n)) avec un index !
• Par contre, plus il y a d’index pour un fichier, plus les opérations de modification seront lentes.