ARBOLES B+
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 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.
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.
BORRADO EN UN ÁRBOL B+
La operación de eliminación en árboles-B+ es mas simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos: Si al eliminar una clave, la cantidad de llaves queda mayor o igual que [m/2] entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas. Si al eliminar una clave, la cantidad de llaves queda menor que [m/2] entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas.
Video Complementario
Ejercicio
Dada la siguiente secuencia de claves:7,25,27,15,23,19,14,29,10, 50,18,22,46,17,70,33 y 58;dibuje el árbol B+ de orden 5 cuya raíz es R,que se corresponde con dichas claves.
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 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.
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.
BORRADO EN UN ÁRBOL B+
La operación de eliminación en árboles-B+ es mas simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos: Si al eliminar una clave, la cantidad de llaves queda mayor o igual que [m/2] entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas. Si al eliminar una clave, la cantidad de llaves queda menor que [m/2] entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas.
Video Complementario
Dada la siguiente secuencia de claves:7,25,27,15,23,19,14,29,10, 50,18,22,46,17,70,33 y 58;dibuje el árbol B+ de orden 5 cuya raíz es R,que se corresponde con dichas claves.
No hay comentarios.:
Publicar un comentario