Les B-arbres sont des arbres de recherche équilibrés conçus pour être efficaces sur des disques magnétiques ou autres unités de stockage secondaires à accès direct. Les B-arbres ressemblent aux arbres rouge-noir, mais ils sont plus performants quand il s'agit de minimiser les entrées-sorties disque. La différence majeure entre les B-arbres et les arbres rouge-noir réside dans le fait que les nœuds des B-arbres peuvent avoir de nombreux enfants, jusqu'à plusieurs milliers. Autrement dit, le "facteur de ramification" d'un B-arbre peut être très grand, bien qu'il soit généralement déterminé par les caractéristiques de l'unité de disque utilisée. Les B-arbres ressemblent aux arbres rouge-noir au sens où tout B-arbre à n nœuds a une hauteur O(log n), bien que la hauteur d'un B-arbre puisse être très inférieure à celle d'un arbre rouge-noir, car son facteur de ramification peut être beaucoup plus grand. Cela permet donc également d'utiliser les B-arbres pour implémenter en temps O(log n) de nombreuses opérations d'ensemble dynamique. Les B-arbres généralisent de façon naturelle les arbres binaires de recherche.
Un B-arbre simple. Si un nœud interne x d'un B-arbre contient n[x] clés, alors x possède n[x] + 1 enfants. Les clés du nœud x sont utilisées comme points de séparation de l'intervalle des clés gérées par x en n[x]+1 sous-intervalles, chacun étant pris en charge par un enfant de x. Lorsqu'on recherche une clé dans un B-arbre, on prend une décision à (n[x] + 1) alternatives, via des comparaisons avec les n[x] clés stockées dans le nœud x. La structure des feuilles diffère de celle des nœuds internes ; nous étudierons ces différences :