data structures - propósito - ¿Estructuras de datos utilizadas para construir sistemas de archivos?
sistemas de archivos pdf (1)
¿Qué estructura de datos es mejor utilizar para la organización de archivos? ¿Son los B-Trees los mejores o hay otra estructura de datos que obtiene un acceso más rápido a los archivos y una buena organización? Gracias
Todos los sistemas de archivos son diferentes, por lo que hay una gran cantidad de estructuras de datos que realmente se utilizan en los sistemas de archivos.
Muchos sistemas de archivos utilizan algún tipo de vector de bits (generalmente denominado mapa de bits) para rastrear dónde se encuentran ciertos bloques libres, ya que tienen un excelente rendimiento para consultar si un bloque de disco específico está en uso y (para discos que no son abrumadoramente completo) soporta búsquedas razonablemente rápidas de bloques libres.
Muchos sistemas de archivos más antiguos (ext y ext2) almacenaron estructuras de directorios utilizando listas enlazadas simples. Al parecer, esto era en realidad lo suficientemente rápido para la mayoría de las aplicaciones, aunque algunos tipos de aplicaciones que usaban muchos directorios grandes sufrían notables impactos de rendimiento.
El sistema de archivos XFS era famoso por usar B+-trees para casi todo, incluidas las estructuras de directorios y su sistema de registro por diario. Por lo que recuerdo de mi curso de licenciatura en sistemas operativos, la filosofía era que, dado que tardó tanto tiempo en escribir, depurar y ajustar el rendimiento de la implementación del árbol B +, tenía sentido utilizarlo lo más posible.
Otros sistemas de archivos (ext3 y ext4) usan una variante del árbol B llamada HTree que no estoy muy familiarizado. Aparentemente, utiliza algún tipo de esquema de hashing para mantener el factor de bifurcación alto, de modo que se usan muy pocos accesos de disco.
He escuchado anecdóticamente que algunos sistemas operativos intentaron usar árboles de distribución para almacenar sus estructuras de directorio pero tuvieron problemas con ellos. Específicamente, impidió el acceso multiproceso al mismo directorio desde múltiples lectores (ya que en un árbol de distribución, cada acceso remodela el árbol) y encontró un caso de borde donde el árbol degeneraría en una lista vinculada si todos los elementos del árbol fueran accesos secuencialmente. Dicho esto, no sé si esto es solo una leyenda urbana, ya que estos problemas habrían sido evidentes antes de que alguien intentara codificarlos.
El sistema FAT32 de Microsoft usó una gran matriz (la tabla de asignación de archivos) que almacena qué archivos se almacenaron dónde y qué sectores del disco se siguen lógicamente en un archivo. El principal inconveniente es que la tabla tuvo que configurarse por adelantado, por lo que terminaron siendo los límites superiores en el tamaño de los archivos que podrían almacenarse en el disco. Sin embargo, el sistema basado en arreglos fue bastante fácil de implementar.
Esta no es una lista exhaustiva; estoy seguro de que otros sistemas de archivos usan otras estructuras de datos. Sin embargo, espero que te ayude a dar un empujón en la dirección correcta.
¡Espero que esto ayude!