Fundamentos De Estructuras De Archivos Flashcards
¿Qué es un campo?
La unidad más pequeña unidad de información que tiene sentido en un archivo
¿Cuáles son métodos comunes para estructurar un archivo de registros?
Hacer registros de longitud fija
Añadir indicador de tamaño a cada campo (RLV)
Añadir delimitador al final de cada campo
Usar una expresión llave = valor
¿Cuáles son los métodos más comunes pars organizar un archivo en registros?
Requerir que los registros sean de un tamaño en bytes específico
Requerir que los registros tengan un número específico de campos
Comenzar registro con un número que represente la longitud en bytes de cada registro
Tener un segundo archivo registrando el tamaño en bytes de cads registro
Usar un delimitador al final de cada registro
¿En qué consiste la búsqueda secuencial?
Es una estrategia que lee un programa registro por registro buscando una llave (identificador)
¿Para qué situaciones es apropiada la búsqueda secuencial?
Archivos donde buscas cierto patrón
Archivos con pocos registros
Archivos que casi nunca requieren búsquedas
Archivos donde quieres registros con llaves secundarias, donde se espera una gran cantidad de coincidencias
¿De qué manera puedes reclamar espacios de registros eliminados en RLF?
Utilizando una pila conteniendo los NRR de registros eliminados
¿De qué manera puedes reclamar espacios de registros eliminados en RLV?
Estrategia de peor ajuste (reclama el primer registro eliminado con tamaño suficiente para contenerlo, ordenado de mayor a menor)
Estrategia de mejor ajuste (reclama el registro eliminado con tamaño más similar a sí mismo, ordenado de menor a mayor)
¿Cuales son las desventajas del mejor ajuste sobe el menor ajuste?
Requerimos más esfuerzo debido a que tiene que moverse dentro de la lista para ordenar el tamaño del registro eliminado y para buscar registros cuyo espacio usar para nuevos
¿En qué consiste la búsqueda binaria?
Consiste en buscar la llave canónica en un archivo con registros ordenados, tomando la mitad del archivo donde va a estar la llave y repitiendo ese proceso para cada subconjunto del archivo
¿Cuál es el costo de un algoritmo de búsqueda binaria?
(Logaritmo base 2 de n) + 1 en el peor de los casos
(Logaritmo base 2 de n) + 1/2 en el caso promedio
¿Qué es el ordenamiento interno?
Es cuando los contenidos de un archivo se cargan en la RAM para ser ordenados
¿Cuáles son las limitaciones de ordenar internamente y luego hacer búsqueda binaria?
La búsqueda binaria aunque mejor que la búsqueda secuencial, requiere más de uno o dos accesos mientras el acceso por NRR requiere solo uno
Es costoso mantener a un archivo ordenado, especialmente porque las inserciones al archivo causarán la necesidad de reordenar nuestro archivo
Un sort interno solo funciona con archivos pequeños, porque debemos cargar el archivo entero en la RAM
¿Cómo podemos mejorar el ordenamiento de un archivo?
Keysort. tomar solamente las llaves de un registro asociadas a sus NRR, podemos ordenar sin tener que cargar el archivo entero!
