Arboles B+
Páginas: 10 (2444 palabras)
Publicado: 16 de diciembre de 2013
ESTRUCTURAS DE DATOS
Á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 aquellos que resulten necesarias para definir los caminos de búsqueda. Parafacilitar 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íze 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
En informática, un árbol-B es un tipo de estructura de datos de árboles. Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en elnúmero de claves por nodo.
Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.
El númeromáximo de claves en un registro es llamado el orden del árbol-B+.
El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.
El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura.
Para un árbol-B+ de orden n, conuna altura h:
Número máximo de claves es: nh
Número mínimo de claves es: 2(n / 2)h − 1
Un árbol B+ simple (una variación del árbol B) que enlaza los elementos 1 al 7 a valores de datos d1-d7. Note la lista enlazada (en rojo) que permite el recorrido de los elementos en orden.
Los árboles B+ se han convertido en la técnica más utilizada para la organización de archivos indizados. Laprincipal característica de estos árboles 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 tiene la misma longitud. En la figura 8.4 representamos un diagrama de un árbol-B+ de orden 2.
Figura 8.4 Arbol- B+ de orden 2
Es de notar que los arboles-B+ ocupan un poco mas de espacio que los arboles-B, y esto ocurre al existirduplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.
Formalmente se define un árbol- B+ de la siguiente manera:
1. Cada página, excepto la raíz, contiene entre d y 2d elementos.
2. Cada página, excepto la raíz, tiene entre d + 1 y 2d + 1descendientes. Se utiliza m para expresar el número de elementos por página.
3. La pagina raíz tiene al menos dos descendientes.
4. Las paginas hojas están todas al mismo nivel.
5. Todas las claves se encuentran en las paginas hojas.
6. Las claves de las páginas raíz e interiores se utilizan como índices.
7. Búsqueda De Arboles- B+
2. BUSQUEDA EN UN ÁRBOL B+
En este caso, la búsqueda no debedetenerse cuando se encuentre la clave en la página raíz o en una página interior, sino que debe proseguir en la página apuntada por la rama derecha de dicha clave.
La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B. El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentra en una página raíz o interior, en...
Á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 aquellos que resulten necesarias para definir los caminos de búsqueda. Parafacilitar 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íze 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
En informática, un árbol-B es un tipo de estructura de datos de árboles. Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en elnúmero de claves por nodo.
Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.
El númeromáximo de claves en un registro es llamado el orden del árbol-B+.
El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.
El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura.
Para un árbol-B+ de orden n, conuna altura h:
Número máximo de claves es: nh
Número mínimo de claves es: 2(n / 2)h − 1
Un árbol B+ simple (una variación del árbol B) que enlaza los elementos 1 al 7 a valores de datos d1-d7. Note la lista enlazada (en rojo) que permite el recorrido de los elementos en orden.
Los árboles B+ se han convertido en la técnica más utilizada para la organización de archivos indizados. Laprincipal característica de estos árboles 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 tiene la misma longitud. En la figura 8.4 representamos un diagrama de un árbol-B+ de orden 2.
Figura 8.4 Arbol- B+ de orden 2
Es de notar que los arboles-B+ ocupan un poco mas de espacio que los arboles-B, y esto ocurre al existirduplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.
Formalmente se define un árbol- B+ de la siguiente manera:
1. Cada página, excepto la raíz, contiene entre d y 2d elementos.
2. Cada página, excepto la raíz, tiene entre d + 1 y 2d + 1descendientes. Se utiliza m para expresar el número de elementos por página.
3. La pagina raíz tiene al menos dos descendientes.
4. Las paginas hojas están todas al mismo nivel.
5. Todas las claves se encuentran en las paginas hojas.
6. Las claves de las páginas raíz e interiores se utilizan como índices.
7. Búsqueda De Arboles- B+
2. BUSQUEDA EN UN ÁRBOL B+
En este caso, la búsqueda no debedetenerse cuando se encuentre la clave en la página raíz o en una página interior, sino que debe proseguir en la página apuntada por la rama derecha de dicha clave.
La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B. El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentra en una página raíz o interior, en...
Leer documento completo
Regístrate para leer el documento completo.