b-tree
Páginas: 5 (1068 palabras)
Publicado: 21 de febrero de 2014
7.2.4 B-Trees
El concepto de B-Tree surge en 1972 (después del viaje a la luna) y fue creado por Bayer y McCreight en los Laboratorios de Investigación Boeing.
Los autores nunca han mencionado el significado de la "B", algunas personas dicen que es por "balanced", "broad" o inclusive por "Bayer" o "Boeing".
Evidentemente se trata de un árbol o mejor dicho de la generalización de unárbol que permite varias "salidas" o ligas desde sus nodos, de hecho cada nodo contiene varios registros (llaves).
La Figura 7.5 muestra un árbol binario señalando la ruta que se seguiría para insertar un nodo nuevo con valor de "15".
Figura 7.5
Este árbol es muy similar a los que ya hemos presentado anteriormente y que seguramente también es el más popular cuando hablamos de estructuras dedatos. Pero este árbol no necesariamente tiene que tener únicamente un registro (para nuestro caso una llave), la Figura 7.6 muestra un árbol donde cada nodo posee dos llaves y 3 ligas o salidas hacia los siguientes niveles. Se puede observar que para el caso de la raíz el camino de la izquierda representará la ruta hacia aquellas llaves menores que 42, mientras que el de la derecha representaráaquellas que sean mayores que 81 y la del centro aquellas que sean mayores a 42 pero menores a 81.
Figura 7.6
De manera general podemos decir que cada nodo de un B-Tree de orden "d" contiene a lo más 2d llaves y 2d+1 apuntadores o ligas. Es importante resaltar que cada nodo debe tener al menos "d" llaves en todo momento, exceptuando la raíz cuya única restricción que tenga la menos 1llave (2 ligas).
Para los ejemplos de inserción y eliminación estaremos utilizando un b-tree de orden 2.
Figura 7.7
Balanceo
Una de las grandes ventajas de los B-Trees son sus métodos de inserción y eliminación ya que mantienen balanceado el árbol a diferencia de los tradicionales donde se podría tener un caso donde se tenga un acceso secuencial (Figura 7.8a) donde no se aprovecha en nadala estructura de árbol, mientras que el B-Tree siempre mantiene una forma piramidal (Figura 7.8b) gracias a su balanceo.
Figura 7.8
Gracias a dicho balanceo el "camino" más largo en un B-Tree de "n" llaves contiene a lo más logd n nodos, donde d es el orden el B-Tree. Esto es muy importante porque tenemos un gran ahorro en el número de accesos que tenemos que hacer ya que recordemos queestamos hablando de almacenamiento secundario.
Inserción
Analicemos como ocurren las inserciones en un árbol B-Tree. En la Figura 7.9 se presenta un B-Tree de orden 2, cada nodo en el árbol tendrá por consiguiente entre 2 y 4 llaves (debe existir un contador por cada nodo para saber rápidamente el número actual de llaves). La inserción es un proceso de 2 pasos, primero se debe realizar unabúsqueda desde la raíz para localizar la "hoja" apropiada para insertar; a continuación la inserción se realiza y el balanceo se realiza por un procedimiento que mueve desde la hoja hasta la raíz.
Pongamos un ejemplo para ver este proceso más claramente. Deseamos insertar la llave "57" al B-Tree, lo primero que hacemos es buscar la posición que ocuparía, de manera que notamos que su lugar sería en elnodo donde estan (53,54,63), de manera que la llave se agrega y no se hace ningún otro movimiento adicional (Figura 7.9b)
Figura 7.9
Por otro lado si quisiéramos insertar la llave "72" veríamos que su lugar sería en el nodo donde están (68,69,71,76) el cual como se puede observar ya se encuentra "lleno" de manera que debemos dividirlo (split) como se observa en la Figura 7.10. De manera quelas llaves más pequeñas pertenecerán a uno de los nodos (68,69), las llaves más grandes al otro nodo (72,76) y finalmente la llave intermedia (71) se promocionará como separador en el nivel superior (acompañando al 66 y 78). Algo muy importante a considerar es qué sucede cuando esta "promoción" se hace hacia un nodo superior que ya se encuentra lleno, entonces ese nodo se deberá dividir y en...
El concepto de B-Tree surge en 1972 (después del viaje a la luna) y fue creado por Bayer y McCreight en los Laboratorios de Investigación Boeing.
Los autores nunca han mencionado el significado de la "B", algunas personas dicen que es por "balanced", "broad" o inclusive por "Bayer" o "Boeing".
Evidentemente se trata de un árbol o mejor dicho de la generalización de unárbol que permite varias "salidas" o ligas desde sus nodos, de hecho cada nodo contiene varios registros (llaves).
La Figura 7.5 muestra un árbol binario señalando la ruta que se seguiría para insertar un nodo nuevo con valor de "15".
Figura 7.5
Este árbol es muy similar a los que ya hemos presentado anteriormente y que seguramente también es el más popular cuando hablamos de estructuras dedatos. Pero este árbol no necesariamente tiene que tener únicamente un registro (para nuestro caso una llave), la Figura 7.6 muestra un árbol donde cada nodo posee dos llaves y 3 ligas o salidas hacia los siguientes niveles. Se puede observar que para el caso de la raíz el camino de la izquierda representará la ruta hacia aquellas llaves menores que 42, mientras que el de la derecha representaráaquellas que sean mayores que 81 y la del centro aquellas que sean mayores a 42 pero menores a 81.
Figura 7.6
De manera general podemos decir que cada nodo de un B-Tree de orden "d" contiene a lo más 2d llaves y 2d+1 apuntadores o ligas. Es importante resaltar que cada nodo debe tener al menos "d" llaves en todo momento, exceptuando la raíz cuya única restricción que tenga la menos 1llave (2 ligas).
Para los ejemplos de inserción y eliminación estaremos utilizando un b-tree de orden 2.
Figura 7.7
Balanceo
Una de las grandes ventajas de los B-Trees son sus métodos de inserción y eliminación ya que mantienen balanceado el árbol a diferencia de los tradicionales donde se podría tener un caso donde se tenga un acceso secuencial (Figura 7.8a) donde no se aprovecha en nadala estructura de árbol, mientras que el B-Tree siempre mantiene una forma piramidal (Figura 7.8b) gracias a su balanceo.
Figura 7.8
Gracias a dicho balanceo el "camino" más largo en un B-Tree de "n" llaves contiene a lo más logd n nodos, donde d es el orden el B-Tree. Esto es muy importante porque tenemos un gran ahorro en el número de accesos que tenemos que hacer ya que recordemos queestamos hablando de almacenamiento secundario.
Inserción
Analicemos como ocurren las inserciones en un árbol B-Tree. En la Figura 7.9 se presenta un B-Tree de orden 2, cada nodo en el árbol tendrá por consiguiente entre 2 y 4 llaves (debe existir un contador por cada nodo para saber rápidamente el número actual de llaves). La inserción es un proceso de 2 pasos, primero se debe realizar unabúsqueda desde la raíz para localizar la "hoja" apropiada para insertar; a continuación la inserción se realiza y el balanceo se realiza por un procedimiento que mueve desde la hoja hasta la raíz.
Pongamos un ejemplo para ver este proceso más claramente. Deseamos insertar la llave "57" al B-Tree, lo primero que hacemos es buscar la posición que ocuparía, de manera que notamos que su lugar sería en elnodo donde estan (53,54,63), de manera que la llave se agrega y no se hace ningún otro movimiento adicional (Figura 7.9b)
Figura 7.9
Por otro lado si quisiéramos insertar la llave "72" veríamos que su lugar sería en el nodo donde están (68,69,71,76) el cual como se puede observar ya se encuentra "lleno" de manera que debemos dividirlo (split) como se observa en la Figura 7.10. De manera quelas llaves más pequeñas pertenecerán a uno de los nodos (68,69), las llaves más grandes al otro nodo (72,76) y finalmente la llave intermedia (71) se promocionará como separador en el nivel superior (acompañando al 66 y 78). Algo muy importante a considerar es qué sucede cuando esta "promoción" se hace hacia un nodo superior que ya se encuentra lleno, entonces ese nodo se deberá dividir y en...
Leer documento completo
Regístrate para leer el documento completo.