|
|
|
|
Costos Ya que visitar un nodo en el Arbol B conlleva a acceder a memoria secundaria, el número de páginas que se visiten en cada operación sobre el Arbol es lo que nos da la medida de su costo. Analizemos el caso de un archivo externo (ubicado en memoria secundaria) de N elementos. Costo de Buscar Como vimos en la sección Funcionamiento de un Arbol B y su Definición, podemos organizar lógicamente los elementos del archivo mediante un Arbol B de orden n, en el cual cada página contiene entre n y 2n elementos. De aquí que, la Búsqueda de un elemento requiere a lo más lognN accesos al dispositivo secundario. De este modo, el costo de procesar una operación de Búsqueda crece de forma logarítmica en relación con el tamaño del archivo. El peor caso de Búsqueda corresponde cuando se está buscando un elemento que está en la hoja del Arbol y además está situado al final de la página hoja. Costo de Inserción y Borrado La Inserción o el Borrado de un elemento del Arbol B podría requerir, además de la operación de Búsqueda, un costo adicional que es el acceso a memoria secundaria. Es decir el costo de Insertar o Borrar un elemento es de: lognN + Tiempo de acceso a memoria secundaria Pero como el "Tiempo de acceso a memoria secundaria" es una constante (muchas veces bastante significativa), podemos obviarla si usamos el criterio asintótico. Y decir que el costo de Inserción y Borrado en un Arbol B de orden n que contiene las claves de un archivo externo de N elementos es a lo más de: lognN La Tabla 1 muestra cómo puede ser de razonable el costo logarítmico, incluso para archivos de gran tamaño. Por ejemplo, en un Arbol B de orden 50 que contenga las claves que indexan a un fichero de un millón de registros, se puede realizar una operación de Búsqueda, Inserción o Borrado con 4 accesos como mucho.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| 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 |
Copyright © 2001 |
Homepage
