He enviado software comercial que hace precisamente eso. En la última iteración, terminamos ordenando los bloques del archivo en "tipo" e "índice", para que pudiera leer o escribir "el tercer bloque de tipo foo". El archivo terminó estructurado como:
1) Cabecera del archivo. Puntos en la lista de tipos principales. 2) Datos. Cada bloque tiene un encabezado con tipo, índice, tamaño lógico y tamaño acolchado. 3) matrices de (tuplas de compensación, tamaño) para cada tipo dado. 4) Matriz de (tipo, desplazamiento, recuento) que realiza un seguimiento de los tipos.
Lo definimos para que cada bloque sea una unidad atómica. Comenzó a escribir un nuevo bloque, y terminó de escribir eso antes de comenzar cualquier otra cosa. También podría "establecer" el contenido de un bloque. A partir de un nuevo bloque siempre se agrega al final del archivo, para que pueda agregar todo lo que desee sin fragmentar el bloque. "Configurar" un bloque podría reutilizar un bloque vacío.
Al abrir el archivo, cargamos todos los índices en la RAM. Cuando vació o cerró un archivo, volvimos a escribir cada índice que cambió, al final del archivo, luego volvimos a escribir el índice índice al final del archivo, y luego actualizamos el encabezado al frente. Esto significa que los cambios en el archivo fueron todos atómicos: o se compromete al punto donde se actualiza el encabezado, o no. (Algunos sistemas usan dos copias del encabezado de 8 kB para preservar los encabezados, incluso si el sector de un disco sale mal, no lo llevamos tan lejos)
Uno de los "tipos" de bloque era "bloque libre". Al volver a escribir los índices cambiados, y al reemplazar los contenidos de un bloque, el espacio anterior en el disco se fusionó en la lista libre que se guardaba en la matriz de bloques libres. Los bloques libres adyacentes se fusionaron en un solo bloque más grande. Los bloques gratuitos se reutilizaron cuando "establecía el contenido" o para los índices de bloque de tipo actualizados, pero no para el índice del índice, que siempre se escribió al final.
Dado que los índices siempre se conservaron en la memoria, trabajar con un archivo abierto fue realmente rápido, normalmente solo una lectura para obtener los datos de un bloque (o manejar un bloque para la transmisión). La apertura y el cierre fueron un poco más complejos, ya que necesitaban cargar y eliminar los índices. Si se convierte en un problema, podemos cargar el índice de tipo secundario a pedido en lugar de hacerlo por adelantado para amortizar ese costo, pero nunca fue un problema para nosotros.
Prioridad máxima para el almacenamiento persistente (en disco): ¡Robustez! ¡No pierda datos incluso si la computadora pierde potencia mientras trabaja con el archivo! Segunda prioridad para el almacenamiento en disco: ¡No haga más E/S de lo necesario! Las búsquedas son costosas. En unidades Flash, cada E/S individual es costosa, y las escrituras lo son doblemente. Intenta alinear y procesar por lotes I/O. Usar algo como malloc() para el almacenamiento en disco generalmente no es genial, porque hace demasiadas búsquedas. Esta es también una razón por la que no me gustan mucho los archivos mapeados en memoria: las personas tienden a tratarlos como RAM, y luego el patrón de E/S se vuelve muy costoso.
Hay hay muchos intercambios en el diseño de un sistema de archivos (usted está haciendo la parte de asignación de espacio). Creo que es mejor comenzar a leer sobre ellos, porque las respuestas darán una imagen completa. –
Um, los sistemas de archivos generalmente tienen muy mal representaciones de espacio libre ... –
@Helen Esto se debe a que el sistema de archivos habitual no está ajustado a una aplicación especial. Puede diseñar su política de asignación y representación de acuerdo con sus necesidades. Recuerde comenzar sus comentarios con @nombre de usuario , entonces la otra parte recibe una notificación. –