Los árboles reciben su nombre de R. Bayer, quien en 1970 propuso un nuevo tipo de árboles, en los que todas las páginas, excepto una), contienen entre n y 2n nodos, siendo n una constante dada. Como consecuencia de esto se puede deducir que los árboles B no son árboles binarios como sí lo son los binarios de búsqueda o los AVL.
En los árboles B los nodos se agrupan dentro de páginas, por lo que se podría definir a la página como un conjunto de nodos.
Los árboles B deben cumplir las siguientes características en cuanto a estructura:
Además de estas características, los árboles B tienen que cumplir un cierto orden:
A continuación se muestran dos árboles, uno de ellos es un árbol B y otro no.
Este es un árbol B correcto, ya que cumple todas las reglas en cuanto a su estructura y al orden.
En cambio, este no es un árbol B, ya que a pesar de mantener el orden, hay una página (que no es la raíz) que tiene menos de n elementos (en este caso menos de 2 elementos). Esta página es la que contiene al elemento 10.