Upload
krytor
View
688
Download
4
Embed Size (px)
Citation preview
Árboles B+ de prefijos simples.Equipo No. 8
INTEGRANTES:
ALONSO GONZÁLEZ GERARDO DANIEL
BUENROSTRO RIVAS DANIEL
FRANCO GARCÍA JUAN
SANTANA ORNELAS MIGUEL ÁNGEL
Contenido: ¿Qué son los arboles B+ de prefijos simples?
Características principales y diferencias.
Inserción
Eliminación
Modificación
Conclusión
¿Qué son los árboles B+ de prefijos simples?
En términos generales es un árbol en el cual los separadores elegidos son los prefijos más cortos que permiten distinguir dos llaves de índices vecinas.
Tenemos aquí un ejemplo, el hijo izquierdo de la raíz tiene dos llaves, BF90 y BQ322. Si
una llave es menor que BF90, se elige la primera hoja; si es
mayor que BQ322, la segunda hoja es la elección correcta. Pero se tiene que
observar que también tenemos los mismos
resultados si, en lugar de BF90 se utilizan las llaves BF9
ó solo BF y, en lugar de BQ322, se utiliza uno de los tres prefijos de esta llave;
BQ32, BQ3 o solo BQ.
Después de elegir el prefijo más corto de las dos llaves respectivamente, si una
llave es menor que BF la búsqueda termina en la primera hoja y si la llave es menor que BQ se elige la segunda hoja; el resultado es exactamente el mismo que antes. La reducción del tamaño de los separadores a lo mínimo necesario no
cambia el resultado de la búsqueda. Solo vuelve a los separadores más pequeños.
“”
Separadores
Separadores
• Derivados de las llaves de los registros que limitan un bloque en el conjunto de secuencia
• Separadores más cortos, ocupan espacio mínimo
• Por consecuente:• Árbol B+ en el cual el
conjunto índice está constituido por separadores más cortos
Características principales
La característica de estos árboles radica en que el conjunto de llaves que NO son hojas del árbol (index set), no son llaves completas sino un "prefijo" (prefix) de dichas llaves, de manera que las llaves completas sólo existen en el nives más bajo (hojas del árbol).
Similar al árbol B+ las hojas del árbol en realidad son "bloques" de datos que se van ligando unos con otros
Todo árbol B+ puede tener menos niveles. Lo cual reduce el factor de ramificación y acelera el procesamiento del árbol.
Esta lógica no se detiene en el nivel de los padres de las hojas. Se transfiere a otro nivel de manera que todo el conjunto de índices de un árbol B+ se llena con prefijos, como se muestra en la siguiente figura.
Lo que se pretende con los prefijos es que sean
del menor tamaño posible ya que
recordemos que para cada nodo hoja la
referencia que se tiene con el nodo superior es
la llave de mayor tamaño. En el ejemplo
de la figura 8.8 (un prefix b+tree de orden 2)
podemos ver que la llave más grande del primer
bloque sería "Berne" y el prefijo que nos sirve de
separador es "Bo" de ahí lo que mencionábamos de la relación menor-
mayor.
Las operaciones sobres los arboles B+ de prefijos simples
son muy parecidas a las operaciones de los arboles B+
con ciertas modificaciones para representar los prefijos utilizados
como separadores.
En particular después de una división, la primera llave de un nodo nuevo no se mueve ni se
copia al padre, pero se encuentra el prefijo mas corto que lo
diferencia del prefijo de la ultima llave en el nodo viejo, y el prefijo más corto luego se aplica en el
padre.
Inserción
Partimos de un árbol de un nodo hoja vacio de un árbol B+, los bloques de datos del conjunto secuencia pueden almacenar un máximo de 2 registros . Las claves son {B,A,D,C,R,P,G}
Borrado En Arboles-B+
La operación de borrado en árboles-B+ es mas simple que la operación de borrado en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos:
1. Si al eliminar una clave, m queda mayor o igual a d entonces termina la operación de borrado. Las claves de las paginas raíz o internas no se modifican por mas que sean una copia de la clave eliminada en las hojas. ( Se presenta un ejemplo de este caso en la figura 8.9 ).
Figura 8.9 Eliminación de la clave 25a) Antes de eliminar la clave. b) Después de eliminarla.
2. Si al eliminar una clave, m queda menor a d entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas. ( Hay dos ejemplos que ilustran como funciona este caso en la figura 8.10 ).
Nota: Al eliminar la clave 27 de la página A, m queda menor a d por lo que debe realizarse una redistribución de las claves. Se toma la clave que se encuentra más a la derecha en la rama izquierda de 25 (21 de la página B). Se coloca dicha clave en la página A y una copia de la misma, como índice, en la página C.
Figura 8.10 Eliminación de la clave 21b) Antes de eliminar la clave. d) Después de eliminarla.
b) Antes de eliminar la clave. d) Después de eliminarla.
Nota: Al eliminar la clave 21 de la página A, m queda menor a d por lo que debe realizarse una redistribución de claves. Como no se puede tomar una clave de la página B puesto que m quedaría menor a d, entonces se realiza una fusión de las páginas A y B.
Puede suceder que al eliminar una clave y al realizar una redistribución de las mismas, la altura del árbol disminuya en una unidad. ( En la figura 8.11 se presentan dos diagramas que clarifican y resuelven este caso).
Nota: Al eliminar la clave 37 de la página A, m queda menor a d por lo que debe realizarse una redistribución de claves. Como no puede tomarse una clave de la página B puesto que m quedaría menor a d, entonces se realiza una fusión de las páginas A y B. Sin embargo, luego de está fusión m queda menor a d en la página C, por lo que debe bajarse la clave 29 de la página E y realizarse una nueva fusión, ahora de las páginas C y E. La altura del árbol disminuye en una unidad.
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.
La diferencia fundamental consiste en que al estar todos los registros en los bloques de datos, es necesario que la búsqueda llegue siempre a un nodo hoja, que es donde se encuentra la dirección del bloque donde puede estar el registro almacenado. Una vez localizado el bloque, se llevará a memoria, donde se realizará la búsqueda del registro.
Buscamos el registro 86
Bibliografia
http://books.google.com.mx/books?id=2Fwqu0XE77gC&pg=PA316&lpg=PA316&dq=arboles+b%2B+de+prefijos+simples&source=bl&ots=6W484r_DZD&sig=haLWN2TUogvb4eYfGzXDiJh1ovA&hl=es&sa=X&ei=gpaaUbqfOoa0yQGz2IDQDA&ved=0CC8Q6AEwAQ#v=onepage&q=arboles%20b%2B%20de%20prefijos%20simples&f=false
http://ict.udlap.mx/people/carlos/is215/ir08.html
http://www.inadsys.com/itig_oga_0607/tema7.pdf