ÁRBOLES B+



1. INTRODUCCIÓN

Los árboles B+ constituyen otra mejora sobre los árboles B,pues conservan la propiedad de acceso aleatorio rápido y permiten además un recorrido secuencial rápido.En un árbol B+ todas las claves se encuentran en hojas,duplicándose en la raíz y nodos interiores aquellas que resulten necesarias para definir los caminos de búsqueda.Para facilitar el recorrido secuencial rápido las hojas se pueden vincular,obteniéndose ,de esta forma,una trayectoria secuencial para recorrer las claves del árbol.

Su principal característica es que todas las claves se encuentran en las hojas.Los árboles B+ ocupan algo más de espacio que los árboles B,pues existe duplicidad en algunas claves.En los árboles B+ las claves de las páginas raíz e interiores se utilizan únicamente como índices.



El orden de inserción de los diversos elementos fue: p v d e b c s a r f t q

2. BUSQUEDA EN UN ÁRBOL B+

En este caso,la búsqueda no debe detenerse cuando se encuentre la clave en la página raíz o en una página interior,si no que debe proseguir en la página apuntada por la rama derecha de dicha clave.

3. INSERCIÓN EN UN ÁRBOL B+

Su diferencia con el proceso de inserción en árboles B consiste en que cuando se inserta una nueva clave en una página llena,ésta se divide también en otras dos,pero ahora la primera contendrá con m/2 claves y la segunda 1+m/2, y lo que subirá a la página antecesora será una copia de la clave central.

4. BORRADO EN UN ÁRBOL B+

La operación de borrado debe considerar:





Tutor de Estructuras de Datos Interactivo
Exposito Lopez Daniel, Abraham García Soto, Martin Gomez Antonio Jose
Director de proyecto: Joaquín Fernández Valdivia
5º Licenciatura Informatica
ETSII 99/00 (Universidad de Granada).