Arboles b+
Páginas: 2 (340 palabras)
Publicado: 16 de abril de 2010
ÁRBOLES B+
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 aquellos que resulten necesarias para definir los caminos de búsqueda. Para facilitar el recorrido secuencialrá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 seencuentran 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.
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 debeproseguir 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 unanueva 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 laclave central.
4. BORRADO EN UN ÁRBOL B+
La operación de borrado debe considerar:
• Si al eliminar la clave (siempre en una hoja) el número de claves es mayor o igual a m/2 elproceso ha terminado. Las claves de las páginas raíz o internas no se modifican aunque sean una copia de la eliminada, pues siguen constituyendo un separador válido entre las claves de las páginasdescendientes.
• Si al eliminar la clave el número de ellas en la página es menor que m/2 será necesaria una fusión y redistribución de las mismas tanto en las páginas hojas como en el...
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 aquellos que resulten necesarias para definir los caminos de búsqueda. Para facilitar el recorrido secuencialrá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 seencuentran 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.
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 debeproseguir 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 unanueva 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 laclave central.
4. BORRADO EN UN ÁRBOL B+
La operación de borrado debe considerar:
• Si al eliminar la clave (siempre en una hoja) el número de claves es mayor o igual a m/2 elproceso ha terminado. Las claves de las páginas raíz o internas no se modifican aunque sean una copia de la eliminada, pues siguen constituyendo un separador válido entre las claves de las páginasdescendientes.
• Si al eliminar la clave el número de ellas en la página es menor que m/2 será necesaria una fusión y redistribución de las mismas tanto en las páginas hojas como en el...
Leer documento completo
Regístrate para leer el documento completo.