Arbre B | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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

À propos de ce résultat

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.

Concepts associés (33)

Cours associés (62)

Séances de cours associées (487)

MOOCs associés (18)

CS-250: Algorithms

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

CS-322: Introduction to database systems

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

MGT-483: Optimal decision making

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

Base de données

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

Arbre B

Système de fichiers

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.

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 about plasma applications from nuclear fusion powering the sun, to making integrated circuits, to generating electricity.

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.

Couvre la théorie et les applications des orbitales hybrides dans les structures moléculaires.

Explore les transformations des jauges non-abéliennes, en mettant l'accent sur les représentations mathématiques et les forces sur le terrain.