用於構建文件系統的數據結構？

什麼數據結構最適合用於文件組織？ B-Tree是最好的，還是有另一種數據結構可以更快地訪問文件和良好的組織？謝謝用於構建文件系統的數據結構？

來源

2013-01-02 Bernice

我是使用數據庫來存儲信息的粉絲。我相信大多數DB使用B結構。有沒有你想要完成的具體任務？ – kevingreen

我只是好奇哪些數據結構被操作系統用於文件組織，因爲我正在學習數據結構，並且實現了其中的一些：紅黑樹，AVL樹，B-樹，跳過列表..我想知道哪些我可以用於更有用的任務（不存儲數字） – Bernice

我不確定大多數操作系統如何存儲數據。祝你好運。 – kevingreen

所有的文件系統都不同，所以實際上在文件系統中使用了大量的數據結構。

許多文件系統使用某種類型的bit vector（通常稱爲位圖）來跟蹤某些空閒塊的位置，因爲它們在查詢特定塊磁盤是否正在使用時具有出色的性能，絕對滿）支持合理快速查找空閒塊。

許多較舊的文件系統（ext和ext2）使用簡單鏈接列表存儲目錄結構。顯然這對於大多數應用程序來說足夠快，儘管某些使用大量大型目錄的應用程序遭受了明顯的性能提升。

XFS文件系統以使用B+-trees而聞名於世，包括目錄結構及其日誌系統。從我從本科生的OS課程中記憶中，我的理念是，由於編寫，調試和性能調整B +樹的實現需要花費很長時間，因此儘可能多地使用它是有意義的。

其他文件系統（ext3和ext4）使用我不太熟悉的名爲HTree的B-樹變體。顯然它使用某種哈希方案來保持分支因子高，因此很少使用磁盤訪問。

我聽說有些操作系統試圖使用splay trees來存儲它們的目錄結構，但卻遇到了麻煩。特別是，它阻止多線程訪問多個讀取器中的相同目錄（因爲在一個splay樹中，每個訪問都會重塑樹），並遇到一個邊緣情況，如果樹的所有元素都是順序訪問，樹會退化爲鏈表。這就是說，我不知道這是否只是一個城市傳說，因爲在任何人嘗試編碼之前，這些問題都會顯而易見。

微軟的FAT32系統使用了一個巨大的數組（文件分配表），用於存儲哪些文件存儲在哪裏以及哪些磁盤扇區在邏輯上相互依次存儲在一個文件中。主要缺點是必須預先設置表格，所以最終會限制磁盤上可以存儲的文件的大小。但是，基於陣列的系統很容易實現。

這不是一個詳盡的列表 - 我確定其他文件系統使用其他數據結構。不過，我希望它能幫助你朝着正確的方向前進。

希望這會有所幫助！

來源

2013-01-02 18:03:10 templatetypedef

非常有用的帖子謝謝！我會研究位矢量，然後對其他操作系統進行更多的研究。我聽說斜紋樹很麻煩！我對B-Tree非常熟悉，但我期待學習其他數據結構，這些數據結構將用於這種類型的東西！感謝您的長時間回答:) – Bernice

用於構建文件系統的數據結構？

回答

相關問題