Qual è la complessità temporale della lettura di un file da un filesystem Linux?

Supponiamo di avere un numero molto elevato di directory (ad esempio 100.000) nel mio file system e all'interno di ciascuna directory c'è un numero simile di directory. Ogni directory può contenere qualsiasi numero di file, ma in genere non più di pochi. Questa struttura va a una profondità costante (10).Qual è la complessità temporale della lettura di un file da un filesystem Linux?

La mia domanda è che è una differenza di tempo di complessità (nell'operazione di lettura) se ho letto in un file da questa struttura di directory come: /dir-34/dir-215/dir-345/file1 usando Paths.get() rispetto alla lettura di un file formano un semplice file di sistema come questo:

/dir1 
    /dir2 
    /dir3 
    file1 
    /dir4 
    file2

Nota: Questa è solo una questione teorica voglio solo sapere se il numero di directory/file nella directory sto cercando di aprire un file da ha alcun effetto sulla velocità di operazione di lettura.

fonte

2014-12-18 Adam Arold

Non è chiaro cosa stai confrontando qui. In entrambi i casi sembra che tu abbia una struttura di directory nidificata ... –

Inoltre, per "complessità temporale" intendi big-O o qualcosa del genere, o stai semplicemente parlando di "run time"? –

100.000 dirs e ciascuno (!) Contiene 100.000 - e questo a un livello di 10? Googol? – laune

Se il /path/to/file è disponibile, (Nota: ancora la complessità delle prestazioni e il tempo in gran parte dipende dalla on- le strutture del disco e l'implementazione del file system sottostante. Ex btrfs, tutto è b-tree, ext4 e XFS utilizzano alberi ad H)

Pertanto, per attraversare la struttura della directory fino al nodo foglia (directory che contiene il file), la media la complessità del caso dovrebbe essere O (logN), mentre il caso peggiore sarebbe O (N), N = no delle directory nell'albero. Il caso peggiore è quando si ha la directory Nth creata in N-1 e la directory N-1th creata in N-2, e così via ... fino alla directory root, formando un singolo ramo nell'albero. Idealmente non devi attraversare tutte le directory dell'albero dalla radice se hai il percorso completo.

Quindi se l'FS sottostante supporta indici di directory e hashing, ogni ricerca richiederebbe un altro O (1) nel trovare il file all'interno della directory. Pertanto, O (logN) + O (1), vale a dire ignorando i termini dell'ordine inferiore, dovrebbe essere solo O (logN), dove N è il livello.

fonte

2014-12-20 08:26:07 askb

Dato una profondità di directory costante di 10, la complessità è O (1), non O (log n). Il nucleo di questa domanda sembra essere la porzione in corsivo alla fine relativa alle prestazioni delle directory di grandi dimensioni. Quel caso è interamente una funzione dell'indice di directory sottostante, non della struttura dell'albero della sottodirectory. –

@DougLuce Salve, quando si calcola la complessità temporale è sempre bene prendere la media e il caso peggiore, quindi sto considerando N = no delle directory nell'albero, che è un numero abbastanza grande. Per qualsiasi struttura ad albero, le ricerche sono sempre O (logN) e non possono essere O (1), diciamo che abbiamo un percorso '/ A/B/C/D/E/file' per un file, per arrivare alla direzione sotto' E', devi fare almeno quattro ricerche() partendo dalla radice. La questione nella questione è in gran parte vaga e dipende dalle strutture dati utilizzate per implementare la stessa FS. – askb

Il numero di livelli non è O (log N) nella media o nel caso peggiore. È O (10) al massimo, come è stato esplicitato nella domanda. Inoltre, ci sono un numero qualsiasi di strutture ad albero per le quali le ricerche non sono O (log N) (liste collegate, alberi esponenziali, ecc.). –

Alcuni file system più diffusi utilizzano strutture dati più efficienti rispetto ai vecchi file system. ext4 ha l'hashing della directory attivato per impostazione predefinita (come indicato da @ninjalj), così come XFS. Ciò significa che le ricerche in una singola directory richiedono in media lo O(1) (quindi un tempo costante se il percorso ha un numero massimo fisso di sottodirectory). Questo segue il performance of the hash function itself.

Anche se si dispone di zillioni di file per directory, l'accesso a un singolo file è molto veloce, ma solo se si ha il percorso completo. Se NON si ha il percorso completo, e invece si deve guardare attraverso una directory per un pattern, si è di fronte a O(n) sul numero di voci nella directory. Ciò è ulteriormente esacerbato da una piccola dimensione di lettura (32k) per le chiamate di lettura di directory di livello di sistema predefinite.

(. Mentre ext4 directory possono avere enormi quantità di file, si sono limitati a 64000 voci sottodirectory)

fonte

2014-12-20 04:14:55

Qual è la complessità temporale della lettura di un file da un filesystem Linux?

risposta

Problemi correlati