Concept
Arbre B
Concepts associés (20)
Btrfs
Btrfs (B-tree file system, prononcé ButterFS) est un système de fichiers des années 2010 fondé sur le Copy-On-Write (copie sur écriture en français) sous licence GNU GPL, développé conjointement par Oracle, Red Hat, Fujitsu, Intel, SUSE, et autres. En 2012, alors qu'il n'était pas encore considéré comme tout à fait stable, un effort intense de développement et de test est fourni par la communauté afin de faire de Btrfs le successeur de ext4 et ext3, systèmes de fichiers habituels des distributions Linux.
Arbre AVL
En informatique théorique, les arbres AVL ont été historiquement les premiers arbres binaires de recherche automatiquement équilibrés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même nœud diffèrent au plus de un. La recherche, l'insertion et la suppression sont toutes en dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement et , qui l'ont publié en 1962 sous le titre An Algorithm for the Organization of Information.
Arbre binaire de recherche
En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
Structure de données
En informatique, une structure de données est une manière d'organiser les données pour les traiter plus facilement. Une structure de données est une mise en œuvre concrète d'un type abstrait. Pour prendre un exemple de la vie quotidienne, on peut présenter des numéros de téléphone par département, par nom, par profession (comme les Pages jaunes), par numéro téléphonique (comme les annuaires destinés au télémarketing), par rue et/ou une combinaison quelconque de ces classements.
Attributs étendus
En informatique, les attributs étendus (EA - Extended Attributes) sont une fonctionnalité du système de fichiers. On distingue en fait les attributs dits réguliers, réservés à l'usage du système de fichiers lui-même, des attributs dits étendus, qui en sont une extension. Ces derniers permettent à l'utilisateur d'un système de fichier d'associer des métadonnées, autrement dit un certain nombre d'informations supplémentaires, à un inode.
Ext3
ext3 est le nom d'un système de fichiers utilisé notamment par GNU/Linux. C'est une évolution de ext2, le précédent système de fichiers utilisé par défaut par de nombreuses distributions GNU/Linux. Le premier à avoir annoncé travailler sur une amélioration de ext2 est , qui annonce le avoir ajouté un fichier journal à ext2. ext3 passe finalement dans la branche 2.4.15 de Linux en novembre 2001. Ses successeurs désignés sont ext4 et à terme Btrfs.
Index (base de données)
En informatique, dans les bases de données, un index est une structure de données utilisée et entretenue par le système de gestion de base de données (SGBD) pour lui permettre de retrouver rapidement les données. L'utilisation d'un index simplifie et accélère les opérations de recherche, de tri, de jointure ou d'agrégation effectuées par le SGBD. L’index placé sur une table va permettre au SGBD d'accéder très rapidement aux enregistrements, selon la valeur d'un ou plusieurs champs.
Arbre splay
Un arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.
Block (data storage)
In computing (specifically data transmission and data storage), a block, sometimes called a physical record, is a sequence of bytes or bits, usually containing some whole number of records, having a maximum length; a block size. Data thus structured are said to be blocked. The process of putting data into blocks is called blocking, while deblocking is the process of extracting data from blocks. Blocked data is normally stored in a data buffer, and read or written a whole block at a time.
Best, worst and average case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. Usually the resource being considered is running time, i.e. time complexity, but could also be memory or some other resource. Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n.