Son arboles K-arios con las siguientes propiedades

• Todas la hojas deben de estar en el mismo nivel

• Todas las paginas internas excepto la raiz, tienen un maximo de n branches y un minimo de n/2 branches

• La cantidad llaves a nivel interno de cada pagina debe coincidir con la cantidad de ramificaciones -1, es decir que si hay 6 ramificaciones, hay 5 llaves

• Las llaves separan las raficaciones de la misma manera que funcionan los ABB(izq= <, der= >)

• La raiz debe tener un maximo de m ramificacion y no tiene minimo de branches

Los arboles B siempre estan perfectamente balanceados

Las paginas deben estar parcialmente llenas para no ser un simple nodo binario

El orden del B-tree debe coincidir con tamaño de los bloques del disco

1. Busca la llave que desea insertar
2. Si no se encuentra se inserta en el ultimo nodo hoja visitado no lleno
3. Si la pagina es una hoja llena, se inserta ordenando la hoja y se hace la operacion del ## split
4. Si se encuentra no se inserta

• Caso 1. Nodo Hoja con un extra
• Caso 2. hijo Con predecedente con extra
• Caso 3. hijo Con sucesor con extra
• Caso 4. no sobran en hijos, junta los del medio
• Caso 5. Junta todos para mantener niveles

Datos se almacenan en nodos hoja Nodos internos con llaves para llegar Hojas con punteros a hermanos derechos

Cambia condiciones, todos nodos excepto raiz y hojas, tiene (2m-1)/3 hijos Raiz tiene al menos 2 y maximo 2[(2m-2)/3]+1 hijos Todas las hojas en el mismo nivel Nodo NO hoja, con k hijos, puede tener k-1 llaves

Insercion lenta, debido a que el SPLIT