Sto per conoscere i (moderni) filesystem. Come parte di questo, mi sono imbattuto in file system strutturati di log che gestiscono anche le allocazioni in un modo strutturato di log. Mi chiedo come gestiscono l'allocazione dello spazio nel modo più efficiente e se probabilmente usano una struttura dati, non ne sono a conoscenza.
Per quanto ho capito, una voce di log relativa all'allocazione, memorizzata sul disco, consiste fondamentalmente in:
+------------------------+
| offset | length | type |
+------------------------+
Dove offset è l'offset su disco (o all'interno di una regione di esso), length come quantità di blocchi (o byte) e type come operazione di allocazione o operazione libera.
Una volta letti dal disco, queste voci vengono gestite e unite all'interno di una struttura dati specifica (ad albero) usando un solo tipo, cioè unisci tutte le allocazioni che sono in grado di dire su offsets che avvia un'area di spazio libero fino a length di lunghezza.
È facile ordinare questa struttura per offset, poiché questo valore è unico. Ma per le operazioni di allocazione, sarebbe più semplice avere una struttura separata dove i dati sono gestiti da length , cioè voglio allocare x di blocchi, cercare x e se il risultato è inferiore a x , dammi la voce successiva che è maggiore di x e usala offset per un'operazione di allocazione del tipo alloc(offset, x) .
Naturalmente, una tale struttura dati dovrebbe gestire i duplicati, poiché lo stesso length (dei blocchi liberi) può essere disponibile a più offsets .
- Quindi quale struttura dati sarebbe la migliore per questo lavoro? Per quanto ne so, rb-tree, AVL tree o b-tree (e le sue varianti) richiedono chiavi univoche ?!
- Domanda aggiuntiva: qual è la strategia di allocazione dei file system che utilizzano una struttura basata su log? Ho frainteso la voce di registro sul disco?
Un approccio a cui potrei pensare, userebbe un albero rb simile a quello fornito dal kernel Linux ed estendi il nodo rb-tree (con length come chiave) da un array / elenco collegato di offsets con la stessa lunghezza. Ma entrambi, array e elenco collegato, sembrano essere approcci non ottimali al problema.