En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique.
Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de l’arbre binaire de recherche. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un arbre B grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles.
Le créateur des arbres B, Rudolf Bayer, n'a pas explicité la signification du « B ». L'explication la plus fréquente est que le B correspond au terme anglais « balanced » (en français : « équilibré »). Cependant, il pourrait aussi découler de « Bayer », du nom du créateur, ou de « Boeing », du nom de la firme pour laquelle le créateur travaillait (Boeing Scientific Research Labs).
Les arbres B ont été inventés en 1970 par Rudolf Bayer et Edward M.McCreight dans les laboratoires de recherche de Boeing. Le but était de pouvoir gérer les pages d'index de fichiers de données, en tenant compte du fait que le volume des index pouvait être si grand que seule une fraction des pages pouvait être chargée en mémoire vive. Le premier article décrivant le mécanisme des arbres B a été écrit en juillet et publié en .
Un arbre étiqueté est un arbre (au sens informatique du terme) tel qu'à chaque nœud on associe une étiquette ou clé (ou bien plusieurs étiquettes ou clés dans le cas des arbres B) prise(s) dans un ensemble donné. Donc formellement un arbre étiqueté est un couple formé d'un graphe orienté, acyclique et connexe et d'une fonction d'étiquetage des arbres qui attribue à chaque nœud une étiquette ou une clé.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.
Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.
Explore le chaos dans les théories quantiques des champs, en se concentrant sur la symétrie conforme, les coefficients OPE et l'universalité de la matrice aléatoire.
Une base de données permet de stocker et de retrouver des données structurées, semi-structurées ou des données brutes ou de l'information, souvent en rapport avec un thème ou une activité ; celles-ci peuvent être de natures différentes et plus ou moins reliées entre elles. Leurs données peuvent être stockées sous une forme très structurée (base de données relationnelles par exemple), ou bien sous la forme de données brutes peu structurées (avec les bases de données NoSQL par exemple).
En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique. Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de l’arbre binaire de recherche.
Le terme système de fichiers (abrégé « FS » pour File System, parfois filesystem en anglais) désigne de façon ambigüe : soit l'organisation hiérarchique des fichiers au sein d'un système d'exploitation (on parle par exemple du file system d'une machine unix organisé à partir de sa racine (/) ) soit l'organisation des fichiers au sein d'un volume physique ou logique, qui peut être de différents types (par exemple NTFS, , FAT32, ext2fs, ext3fs, ext4fs, zfs, btrfs, etc.
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and op
This course introduces the theory and applications of optimization. We develop tools and concepts of optimization and decision analysis that enable managers in manufacturing, service operations, marke