Homepage    Links     Download    Email

Inserción

Es intersante señalar que la inserción en un Arbol B de orden n es relativamente sencilla. Si hay que insertar un elemento en una página con    m<2n elementos, el proceso de inserción queda limitado a esa página.

Para analizar esta situación, considérese la Figura 4(a) que muestra un Arbol B de orden 2. Puesto que cada página en un Arbol B de orden n (excepto la raíz ) contiene entre n y 2n elementos, cada página del ejemplo tiene entre 2 y 4 elementos. En cada página debe existir un indicador (que no está reflejado en la figura) para informar sobre el número de elementos que tiene la página. Primero se procede a Buscar desde la raíz hasta localizar la página apropiada para la inserción. Entonces se realiza la inserción. Refiriéndonos a la Figura 4(a), uno puede ver que cuando se inserta el elemento 24, la Búsqueda termina sin éxito en la segunda hoja. Puesto que la hoja puede alojar otro elemento, se inserta el elemento nuevo simplemente, dando lugar al Arbol que se muestra en la Figura 4(b).

Figura 4. (a) Un Arbol B de orden 2, y (b) el mismo árbol tras la inserción del elemento 24

La otra situación que se presenta y la más problemática, es cuando se inserta un elemento en una página ya llena. Esto puede afectar la   Estructura del Arbol y ocasionar asignación de páginas nuevas.

Para comprender lo que sucede en este caso, analizemos la Figura 5 que ilustra la inserción de la llave 22 en un Arbol B de orden 2. La acción se realiza en los siguientes pasos:

1. Se descubre que falta la llave 22; la inserción en la página C es imposible porque C ya está llena.
2. La página C se divide en dos páginas (esto es, se asigna una nueva página D).
3. Las 2n + 1 llaves se distribuyen uniformemente en C y D, y la llave de la mitad se sube un nivel hacia la página madre A.

Figura 5. Inserción de la llave 22 en un Arbol B de orden 2

Este plan tan elegante preserva todas las Propiedades típicas de los Arboles B. En particular, las páginas divididas contienen exactamente n elementos. Desde luego, la inserción de un elemento en la página madre puede hacer que ésta se desborde, con lo cual ocasiona que la división se propague. En el caso extremo, puede propagarse hasta la raíz. Es decir, la única manera en que el Arbol B pueda aumentar su altura. Tiene pues una manera singular de crecer: crece de las hojas hacia la raíz.

  | Introducción | - | Funcionamiento | - | ¿Qué es un Arbol B? | - | Búsqueda | - | Inserción |

| Borrado | - | Costos | - | Casos especiales | - | Conclusión | - | Bibliografía |

Web diseñado y creado por
Francisco Luna, Francisco Pizarro y Patricio Merino

Copyright © 2001
Todos los derechos reservados