Arboles B*

[pic 1][pic 2]

Universidad de Guadalajara

Centro Universitario de Ciencias Exactas e Ingenierías

Materia: Estructura de Archivos

“Arboles B*”

Introducción

Los arboles B* son arboles B espaciales en que cada nodo está lleno por lo menos en dos terceras partes.

Los arboles B* por lo general proporcionan mejor utilización del almacenamiento que los arboles B.

• Propone nuevas reglas para el mantenimiento:
• Los nodos deben estar 2/3 llenos siempre
• La nueva construcción logra una búsqueda más rápida que B+ pero una inserción más costosa.

[pic 3][pic 4][pic 5][pic 6][pic 7][pic 8]

[pic 9][pic 10][pic 11][pic 12][pic 13]

Propiedades:

• Cada página tiene un máximo de m descendientes
• Todas las paginas, excepto la raíz y las hojas, tiene al menos (2m-1) / 3 descendientes
• La raíz tiene al menos dos descendiente, a menos que sea hoja
• Todas las hojas se encuentran en el mismo nivel
• Una página que no sea hoja, con K descendiente contiene K -1 claves
• Una página-hoja contiene al menos (2,-1)/ 3 -1 claves, y no más de m -1 claves

Características:

• Mejoran la eficiencia del acceso directo y la sobrecarga al reorganizar el árbol en la inserción y el borrado
• Aseguran ocupación de páginas >= 66.6% (2/3)
• Cambia la división y fusión de paginas
• Pasar elementos al vecino
• cuando el vecino también este lleno, convertir las dos páginas en tres

Inserción

La inserción del árbol B* emplea un esquema de redistribución local para retrasar la división hasta que dos nodos hermanos están llenos.

• Entonces los dos nodos se dividen en tres cada uno lleno en 2/3 partes
• Este esquema garantiza que la utilización del almacenamiento es al menos del 66%, mientras que solamente requieren una moderada modificación de los algoritmos de mantenimiento.
• Esto debe ser señalado ya que el incremento en la utilización del almacenamiento tiene el efecto literal de acelerar la búsqueda ya que la altura del árbol resultante es más pequeña

Insertemos un 40 en el siguiente árbol

[pic 14]

El nodo de un árbol B* de orden 2 tiene 4 llaves, pero en este caso, que se trata de una inserción en la raíz del árbol, la inserción se realiza en el propio nodo, porque la raíz de orden 2 admite hasta 4 llaves. Lo que se obtiene es:

[pic 15]

Si el árbol anterior se le inserta un 70, estaríamos nuevamente en un caso fácil y obtendríamos:

[pic 16]

Eliminación

La eliminación se realiza del mismo modo que  en el árbol B, siempre y cuando no provoque que un nodo quede con menos llaves que las que debe tener, por que en este caso, el procedimiento a seguir en el árbol B* difiere de la vista anteriormente para el árbol B.

...