Mapa de bits de espacio libre

Los mapas de bits de espacio libre son un método utilizado para rastrear sectores asignados por algunos sistemas de archivos . Si bien el diseño más simple es altamente ineficiente, ^{[ 1 ]} algunos sistemas de archivos modernos, como NTFS , utilizan implementaciones avanzadas o híbridas de mapas de bits de espacio libre ^{[ 2 ]} .

La forma más simple de un mapa de bits de espacio libre es una matriz de bits , es decir, un bloque de bits . En este ejemplo, un cero indicaría un sector libre, mientras que un uno indicaría un sector en uso. Cada sector tendría un tamaño fijo. Para fines explicativos, utilizaremos un disco duro de 4 GiB con sectores de 4096 bytes y supondremos que el mapa de bits se almacena en otro lugar. El disco de ejemplo requeriría 1.048.576 bits, uno por cada sector, o 128 KiB . Aumentar el tamaño del disco incrementará proporcionalmente el tamaño del mapa de bits, mientras que multiplicar el tamaño del sector producirá una reducción proporcional.   

Cuando el sistema operativo (SO) necesita escribir un archivo, escanea el mapa de bits hasta encontrar suficientes ubicaciones libres para alojarlo. Si un  archivo de 12 KiB estuviera almacenado en la unidad de ejemplo, se encontrarían tres bits cero, se cambiarían a unos y los datos se escribirían en los tres sectores representados por esos bits. Si posteriormente el archivo se truncara a 8  KiB, el bit del último sector volvería a cero, indicando que está disponible nuevamente.

A medida que aumenta el tamaño de la unidad, el tiempo necesario para escanear el espacio libre puede volverse excesivo. Para solucionar esto, las implementaciones reales de mapas de bits de espacio libre buscarán formas de centralizar la información sobre el espacio libre. Un enfoque consiste en dividir el mapa de bits en varios fragmentos. Una matriz independiente almacena entonces el número de sectores libres en cada fragmento, de modo que los fragmentos con espacio insuficiente se pueden omitir fácilmente y la cantidad total de espacio libre es más fácil de calcular. Encontrar espacio libre ahora implica buscar primero en la matriz de resumen y luego buscar en el fragmento del mapa de bits asociado los sectores exactos disponibles. ^{[ 1 ]}

Este enfoque reduce drásticamente el costo de encontrar espacio libre, pero no facilita el proceso de liberación de espacio. Si el tamaño combinado del array de resumen y el mapa de bits supera la capacidad de almacenamiento en memoria, y se liberan numerosos archivos con sectores dispersos, se requiere un acceso masivo al disco para localizar todos los sectores, decrementar el contador de resumen y restablecer los bits a cero. Esto reduce considerablemente las ventajas del mapa de bits, ya que deja de cumplir su función de resumir rápidamente el espacio libre sin necesidad de leer el disco.

• Mapa de disponibilidad de bloques
• Sistema de archivos de alto rendimiento (HPFS)
• exGRASA
• Índice de mapa de bits : un método para indexar bases de datos que frecuentemente se superpone con diseños de mapa de bits de espacio libre eficientes. 
• Árbol B : un método alternativo para rastrear el espacio libre mediante el almacenamiento de un conjunto ordenado de extensiones de espacio libre.