Los árboles B+ son
una variante de los árboles B, se diferencian en que los
arboles B+ toda la información se encuentra almacenada en las hojas. En la raíz
y en las páginas internas se encuentran almacenado índices o
claves para llegar a un dato.
Los árboles-B+ se han
convertido en la técnica más utilizada para la organización de archivos
indizados. La principal característica de estos arboles es que todas las claves
se encuentran en las hojas y por lo tanto cualquier camino desde la raíz hasta
alguna de las claves tienen la misma longitud.
Principales características de
los árboles B+ de orden m son:
- Propuestos por Knuth en 1997
- Los arboles B+ almacenan los registros de
datos en sus nodos hoja.
- En los nodos interiores y nodo
raíz se construye un indice multinivel.
- Los B+ son la técnica mas utilizada
para la organización de archivos indexados.
- La raíz almacena como mínimo
un dato y como máximo m-1 datos.
- La página raíz tiene como mínimo
dos descendientes.
- Las páginas intermedias tienen
como mínimo (m-1)/2(Parte entera) datos.
- Las páginas intermedias tienen
como máximo m-1 datos.
- Todas las paginas hojas tienen
la misma altura
- La información se encuentra ordenada.
- Toda la información se encuentra
almacenada en las páginas hoja, por lo que en las páginas internas
se puede duplicar las claves.
- Son arboles enearios
Dentro dela operaciones que
podemos hacer con estos árboles están las siguientes:
- Búsqueda
- Inserción
- Eliminación
Búsqueda
Para buscar un registro en un
árbol B+ a partir de su clave, primero hay que recorrer todo el árbol del
índice, comparando los valores de clave de cada nodo y tomando el descendiente
adecuado, tal y como se realiza en la operación de búsqueda de un registro en
un árbol B.
Insertar
Para insertar una clave en un
árbol b+ se hace de la misma manera que los arboles b, lo único que cambia es
que cuando halla desbordamiento y tenga que subir un nodo a la raíz este dejara
una copia en la parte inferior como lo muestra el siguiente ejemplo.
Ejemplo:
Cuando el 30 subió a la raíz
dejando su copia en la parte abajo.
Ahora vamos a insertar la
clave 18 y veremos como queda.
Lo que sucedió fue que al
insertar la clave 18 hubo desbordamiento en la página derecha, lo que provoco
que la clave 18 subiera como raíz dejando su copia en la parte de abajo.
Ahora vamos a insertar la clave
41 quedando de la siguiente manera:
Eliminación
La operación de
eliminación en árboles-B+ es más simple que en árboles-B. Esto ocurre porque
las claves a eliminar siempre se encuentran en las páginas hojas. En general
deben distinguirse los siguientes casos:
Ejemplo: Vamos a retirar la
llave 40 del anterior árbol, quedando de la siguiente manera:
Lo que sucedió fue que al
borrar la clave 40 se elimina la raiz y su copia dejando como nueva raíz a
la clave 41 y su respectiva copia.
Ahora vamos a eliminar la
clave 30 en el siguiente ejemplo:
Como vemos la clave 30 al
eliminarla, la clave 35 queda afectada porque no puede quedar sola, entonces lo
que hacemos es pegar la clave 35 a la clave 27 quedando así 4 claves como
máximo.
En resumen: el árbol B+
mantiene varios órdenes. Dentro de cada nodo existe orden. Entre las hojas
existe orden. En los punteros dentro de un nodo existe orden.
0 comentarios:
Publicar un comentario