3.4. Árboles B.
Son los sucesores de los árboles binarios de búsqueda. Existen muchas variantes, árboles B, B+ y B*. Los árboles B+ son muy usados en bases de datos, en la implementación de índices.
En cada nodo hay n valores (o entradas) y n+1 punteros a nodos hijos.
- Definición: un árbol B de orden p debe cumplir las siguientes propiedades:
- La raíz, o no tiene hijos o como mínimo tiene 2 y máximo p.
- Cada nodo (excepto la raíz y las hojas) tiene entre ?p/2? y p hijos.
- Todas las hojas aparecen al mismo nivel (condición de balanceo).
- Búsqueda: igual que en los árboles binarios, eligiendo la rama por la que seguir. El número de pasos es logp N, en el peor caso.