2013-01-02 30 views
20

Quale struttura dati è meglio utilizzare per l'organizzazione dei file? B-Trees è il migliore o esiste un'altra struttura dati che consente un accesso più rapido ai file e una buona organizzazione? GrazieStrutture dati utilizzate per creare file system?

+1

Sono un fan dell'utilizzo di database per memorizzare le informazioni. Credo che la maggior parte dei DB utilizzi una struttura b. C'è un compito specifico che stai cercando di realizzare? – kevingreen

+0

Sono solo curioso di sapere quale struttura dati viene utilizzata dai sistemi operativi per l'organizzazione dei file poiché sto imparando le strutture dati e ne ho implementate alcune: Red Black Trees, AVL tree, B-Trees, Skip Lists .. Mi piacerebbe so quale di loro posso usare per un compito più utile (non memorizzare i numeri) – Bernice

+0

Non sono specificamente sicuro di come la maggior parte dei sistemi operativi memorizzano i dati. Buona fortuna per la ricerca. – kevingreen

risposta

29

Tutti i file system sono diversi, quindi ci sono un numero enorme di strutture dati che vengono effettivamente utilizzate nei file system.

Molti file system utilizzano una sorta di bit vector (di solito indicata come bitmap) per tracciare dove sono determinati alcuni blocchi liberi, poiché hanno prestazioni eccellenti per interrogare se uno specifico blocco di disco è in uso e (per dischi che non sono 'stracompletamente pieno) supportano ricerche ragionevolmente veloci di blocchi liberi.

Molti sistemi di file precedenti (ext e ext2) memorizzano le strutture di directory utilizzando elenchi concatenati semplici. Apparentemente questo è stato abbastanza veloce per la maggior parte delle applicazioni, anche se alcuni tipi di applicazioni che hanno utilizzato molte grandi directory hanno subito notevoli risultati in termini di prestazioni.

Il file system XFS era famoso per l'utilizzo di B+-trees per quasi tutto, comprese le strutture di directory e il relativo sistema di registrazione. Da quello che ricordo dal mio corso di dottorato undergrad, la filosofia era che, dal momento che ci voleva tanto tempo per scrivere, eseguire il debug e ottimizzare le prestazioni per l'implementazione del B + -tree, era logico utilizzarlo il più possibile.

Altri file system (ext3 e ext4) utilizzano una variante dell'albero B denominata HTree che non mi è molto familiare. Apparentemente utilizza una sorta di schema di hashing per mantenere alto il fattore di ramificazione in modo che vengano utilizzati pochissimi accessi al disco.

Ho sentito in modo aneddotico che alcuni sistemi operativi hanno provato a utilizzare splay trees per archiviare le loro strutture di directory ma si sono scontrati con loro. In particolare, impediva l'accesso multithread alla stessa directory da più lettori (poiché in un albero di splay ogni accesso rimodella l'albero) e incontrava un caso limite in cui l'albero sarebbe degenerato in un elenco collegato se tutti gli elementi dell'albero erano accessi in sequenza. Detto questo, non so se questa è solo una leggenda metropolitana, dato che questi problemi sarebbero stati evidenti prima che qualcuno provasse a codificarli.

Il sistema FAT32 di Microsoft utilizzava un enorme array (la tabella di allocazione file) che memorizza quali file sono stati memorizzati e quali settori del disco si susseguono logicamente in un file. Lo svantaggio principale è che la tabella doveva essere impostata in anticipo, quindi finirono per essere i limiti superiori delle dimensioni dei file che potevano essere memorizzati sul disco. Tuttavia, il sistema basato su array è stato abbastanza facile da implementare.

Questo non è un elenco esaustivo: sono certo che altri file system utilizzano altre strutture di dati. Tuttavia, spero che ti aiuti a dare una spinta nella giusta direzione.

Spero che questo aiuti!

+0

Post molto utile grazie! Farò ricerche sui vettori bit allora, e fare qualche altra ricerca sugli altri sistemi operativi .. Ho sentito che gli alberi splay erano preoccupanti! Sono più familiare con B-Trees ma non vedo l'ora di imparare altre strutture di dati che serviranno per questo tipo di cose! Grazie per la tua lunga risposta :) – Bernice