3.4. Árboles B.
Representación: Cada nodo tiene p-1 posiciones (y p punteros), que pueden estar llenas o vacías.
Inserción de entradas en un árbol B.
- Buscar el nodo hoja (no interno) donde se debería colocar la entrada.
- Si quedan sitios libres en esa hoja, insertarlo (en orden adecuado).
- Si no quedan sitios (la hoja tiene p-1 valores) partir la hoja en 2 hojas (de d = ?p/2? - 1 nodos cada una) y añadir un nuevo elemento al nodo padre (con el valor medio).
- Si en el padre no caben más elementos, repetir recursivamente la partición de las hojas.
Ejemplo. Árbol B de orden 5.