資料結構 – 用於構建檔案系統的資料結構？
什麼資料結構最適合用於檔案組織？ B樹是最好的還是有另一種資料結構,可以更快地訪問檔案和良好的組織？謝謝
所有檔案系統都是不同的,所以在檔案系統中實際使用了大量的資料結構.
許多檔案系統使用某種型別的ofollow,noindex" target="_blank">bit vector (通常稱為點陣圖)來跟蹤某些空閒塊的位置,因為它們具有優異的效能,用於查詢特定的磁碟塊是否正在使用(對於不是壓倒多數的磁碟) )支援快速查詢空閒塊.
許多較舊的檔案系統(ext和ext2)使用簡單的連結串列儲存目錄結構.顯然,這對於大多數應用程式來說實際上足夠快,儘管使用大量大型目錄的某些型別的應用程式遭遇了顯著的效能匹配.
XFS檔案系統是著名的使用B+-trees 的一切,包括目錄結構和其日誌系統.從我本人的本科生操作課程,我的想法是,由於編寫,除錯和效能調整B樹的實現需要很長時間,因此儘可能多地使用它.
其他檔案系統(ext3和ext4)使用稱為HTree 的B-tree的變體,我不太熟悉.顯然,它使用某種雜湊方案來保持分支因子高,以便使用非常少的磁碟訪問.
我聽說有些作業系統試圖使用splay trees 儲存他們的目錄結構,但遇到麻煩.具體來說,它阻止多執行緒訪問同一個目錄(因為在一個播放樹中,每個訪問都會重構樹),並且遇到一個邊緣情況,如果樹的所有元素都被順序訪問,那麼樹將退化為連結串列.也就是說,我不知道這是否只是一個城市傳說,因為這些問題在任何人嘗試編寫程式碼之前都會顯而易見.
Microsoft的FAT32系統使用了一個龐大的陣列(檔案分配表),用於儲存哪些檔案儲存在哪裡,哪些磁碟扇區在邏輯上相互依存在一個檔案中.主要的缺點是表必須提前設定,所以最終可以儲存在磁碟上的檔案的大小上限.然而,基於陣列的系統很容易實現.
這不是詳盡的列表 – 我確信其他檔案系統使用其他資料結構.但是,我希望它有助於推動正確的方向.
希望這可以幫助！
程式碼日誌版權宣告：
翻譯自：http://stackoverflow.com/questions/14126575/data-structures-used-to-build-file-systems