estructura

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos de autor.
Este documento no tiene costo alguno. El uso indebido de este documento es responsabilidad del estudiante.

Estructuras de datos
y algoritmos para
almacenamiento externo
Este capitulo comienza considerando las diferencias en lasformas de acceso entre
la memoria principal y los dispositivos de almacenamiento externo como los discos.
Despuks se presentan varios algoritmos para clasificación de archivos de datos almacenados en forma externa. Se concluye el capítulo con un análisis de estructuras
de datos y algoritmos, como los archivos indizados y los irboles B, que son muy adecuados para el almacenamiento y recuperaciónde información en dispositivos de almacenamiento secundario.

11-1

Un moddo p a n cómputos con almacanamlonto externo

En los algoritmos estudiados en capitulas anteriores, se ha supuesto que la cantidad
de datos de entrada es lo bastante pequeiía como para que quepan en la memoria
al mismo tiempo. Pero, ¿que sucede si se desea clasificar a todos los empleados de
gobierno de acuerdo consu antigüedad, o almacenar toda la informaci6n de los impuestos de la nacibn? En problemas como éstos, la cantidad de datos por procesar
supera la capacidad de la memoria principal. La mayor parte de los grandes sistemas de cómputo tienen dispositivos de almacenamiento externo conectados en Iinea, como discos o dispositivos de almacenamiento masivo, en los cuales se pueden
almacenar cantidadesmuy grandes de datos. Sin embargo, esos dispositivos tienen
características de acceso que difieren mucho de las de la memoria principal. Se han
desarrollado diversas estructuras de datos y algoritmos para utilizar con más eficiencia esos dispositivos. Este capitulo comprende las estructuras de datos y algoritmos
para clasificar y recuperar la información almacenada en memoria secundaria.
Ellenguaje Pascal, y algunos otros, tienen el tipo de datos archivo, destinado a
representar datos almacenados en memoria secundaria. Aunque el lenguaje utilizado no tenga este tipo de datos, es indudable que el sistema operativo debe manejar
la noción de archivos en memoria secundaria. Tanto si se habla de los archivos de
Pascal como de los manipulados directamente por el sistema operativo, seencuentran limitaciones a la forma en que puede accederse a los archivos. El sistema operativo divide la memoria secundaria en bloques de igual tamafío. El tamaiío de los
bloques varía entre los distintos sistemas operativos, pero de 512 a 4096 bytes a lo
típico.
Se considera un archivo como si estuviera almacenado en una lista enlazada de
bloques, aunque lo más comiln es que el sistema operativoutilice una disposición

Aho, Alfred V., John E. Hopcroft y Ullman. (1998). Estructura de datos y algoritmos para almacenamiento externo.
En Estructuras de datos y algoritmos (pp. 379-411). México: Adisson Wesley Longman de México.

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos deautor.
Este documento no tiene costo alguno. El uso indebido de este documento es responsabilidad del estudiante.

UN MODELO PARA COMPUTOS CON ALMACENAMIENTO EXTERNO

347

tipo hrbol, donde los bloques que contienen el archivo son hojas, y cada uno de los
nodos interiores apunta a varios bloques del archivo. Si, por ejemplo, cuatro byies
son suficientes para contener la dirección de unbloque y los bloques tienen 4096
byte de longitud, entonces un bloque raíz puede tener apuntadores hasta para 1024
bloques. Asi, los archivos de hasta 1024 bloques, es decir, cerca de cuatro millones
de bytes, pueden representarse con un bloque raiz y los bloques que wntienen el archivo. Los archivos de hasta 220bloques, o 212 bytes, pueden representarse w n un
bloque raiz que apunte a 1024...