Mapa de bits de espacio libre

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Mapa de bits de espacio libre» – noticias  · periódicos  · libros  · académico  · JSTOR ( julio de 2011 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Los mapas de bits de espacio libre son un método que se utiliza para rastrear los sectores asignados por algunos sistemas de archivos . Si bien el diseño más simple es altamente ineficiente, algunos sistemas de archivos modernos utilizan implementaciones avanzadas o híbridas de mapas de bits de espacio libre ^{[ ¿cuáles? ]} .

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 indica 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 asumiremos que el mapa de bits en sí está almacenado en otro lugar. El disco de ejemplo requeriría 1.048.576 bits, uno para cada sector, o 128  KiB . Aumentar el tamaño de la unidad aumentará 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 (OS) necesita escribir un archivo, escanea el mapa de bits hasta encontrar suficientes ubicaciones libres para que quepa el archivo. Si se almacenara un archivo de 12 KiB en la unidad de ejemplo, se encontrarían tres bits cero, que se cambiarían por unos y los datos se escribirían en los tres sectores representados por esos bits. Si posteriormente el archivo se truncara hasta 8 KiB, el bit del sector final se volvería a establecer en cero, lo que indicaría que está nuevamente disponible para su uso.

Esta sección no cita ninguna fuente . Por favor, ayude a mejorar esta sección añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado . ( Julio de 2011 ) ( Aprenda cómo y cuándo eliminar este mensaje )

• Simple: cada bit corresponde directamente a un sector.
• Comprobación rápida de asignación de acceso aleatorio: comprobar si un sector está libre es tan sencillo como comprobar el bit correspondiente.
• Eliminación rápida: no es necesario sobrescribir los datos al eliminarlos; ^{[ aclaración necesaria ]} basta con invertir el bit correspondiente.
• Coste fijo: ventaja y desventaja a la vez. Otras técnicas para almacenar información en el espacio libre tienen una cantidad variable de gastos generales según la cantidad y el tamaño de las extensiones de espacio libre. Los mapas de bits nunca pueden funcionar tan bien como otras técnicas en sus respectivas circunstancias ideales, pero tampoco sufren casos patológicos. Dado que el mapa de bits nunca crece, se encoge ni se mueve, se requieren menos búsquedas para encontrar la información deseada.
• Bajo consumo de almacenamiento como fracción del tamaño de la unidad: incluso con tamaños de sectores relativamente pequeños, el espacio de almacenamiento necesario para el mapa de bits es pequeño. Una unidad de 2  TB podría representarse completamente con un mapa de bits de tan solo 64  MB (para sectores de 4096 bytes ).

• Desperdicio en discos más grandes: el diseño simplista comienza a desperdiciar grandes cantidades de espacio (en sentido absoluto) para volúmenes extremadamente grandes. ^[1]
• Baja escalabilidad: si bien el tamaño sigue siendo insignificante como fracción del tamaño del disco, encontrar espacio libre se vuelve más lento a medida que el disco se llena. Si el mapa de bits es más grande que la memoria disponible , el rendimiento cae abruptamente en todas las operaciones. ^[1]
• Fragmentación : si se toman los sectores libres a medida que se encuentran, las unidades con creación y eliminación de archivos frecuentes se fragmentarán rápidamente. Si la búsqueda intenta encontrar bloques contiguos, la búsqueda de espacio libre se vuelve mucho más lenta incluso para discos moderadamente llenos. Los datos fragmentados también reducen la velocidad de lectura en los discos duros mecánicos debido a la latencia de búsqueda del cabezal magnético, aunque esto no es un problema en la memoria flash .

A medida que aumenta el tamaño de la unidad, la cantidad de tiempo necesaria para buscar espacio libre puede llegar a ser irrazonable. Para solucionar este problema, las implementaciones reales de mapas de bits de espacio libre encontrarán formas de centralizar la información sobre el espacio libre. Un enfoque consiste en dividir el mapa de bits en muchos fragmentos. Una matriz separada almacena entonces la cantidad 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. Para encontrar espacio libre ahora es necesario buscar primero en la matriz de resumen y luego buscar en el fragmento de mapa de bits asociado los sectores exactos disponibles. ^[1]

Este enfoque reduce drásticamente el costo de encontrar espacio libre, pero no ayuda con el proceso de liberación de espacio. Si el tamaño combinado de la matriz de resumen y el mapa de bits es mayor que el que se puede almacenar fácilmente en la memoria, y se libera una gran cantidad de archivos con sectores dispersos, se necesita una enorme cantidad de acceso al disco para encontrar todos los sectores, disminuir el contador de resumen y volver a poner los bits a cero. Esto reduce en gran medida los beneficios del mapa de bits, ya que ya no realiza su función de resumir el espacio libre rápidamente sin leer desde el disco.

• Mapa de disponibilidad de bloques
• Sistema de archivos de alto rendimiento (HPFS)
• exFAT
• Índice de mapa de bits  : un medio de indexación de bases de datos que frecuentemente se superpone con diseños de mapa de bits de espacio libre eficientes
• B-tree  : un medio alternativo para rastrear el espacio libre mediante el almacenamiento de un conjunto ordenado de extensiones de espacio libre