Stavo osservando come sono progettati i file system e ho notato che la maggior parte delle posizioni indica che la gerarchia delle directory può essere implementata utilizzando una tabella hash.
Qualcuno potrebbe spiegarmi come funziona usando una tabella hash per memorizzare una struttura di directory?
Ad esempio, cosa succederebbe se aggiungessi un file / directory o spostassi una directory, come influisce sulla tabella hash?
Inoltre, in che modo sono coinvolti i percorsi?
Il più semplice è avere una tabella hash per directory. Per seguire un percorso, basta ottenere la tabella hash di root, interrogarlo per la prima directory nel percorso. Quindi, se si tratta di una directory, prendi la successiva tabella hash e interrogala con la parte successiva, e così via fino all'ultima parte.
Poiché le tabelle hash sono strutture non ordinate, di solito li ordinate in memoria per elencare un'intera directory. Inoltre, l'hash non aiuterebbe a far corrispondere i caratteri jolly; devi fare un'intera scansione della directory per vedere quali nomi corrispondono a un determinato modello. Ovviamente, una struttura ordinata (come una lista ordinata o un albero B *) aiuta solo se c'è un prefisso costante.
Un modo diverso (usato dal sistema HFS di Mac) è usare una struttura ordinata (un albero B * nel caso HFS) e indicizzare per directory / nome. In HFS, c'era una struttura dirID / nomefile che fungeva da chiave principale per un singolo albero B *. Una volta che questo file è stato gestito, una singola query ha restituito la voce della directory, senza dover attraversare l'intero percorso. Per ottenere un elenco di directory, basta leggere l'intervallo [dirID, dirID + 1), l'intervallo risultante comprendeva tutti i nomi di file memorizzati in tale directory, in ordine lessicografico binario.
Leggi altre domande sui tag file-systems directory-structure hashing