文件管理

文件的結構

無結構文件

有結構文件（重點）

定長與不定長記錄

• 定長記錄：
  
• 不定長記錄
• 其實這個東西就可以類比于我們在學習線性表中所解決的稀疏多項式問題，也就是一旦當數組當中的某些項的差異比較大的時候，我們如果還是采用定長記錄的方式就會使得存儲空間的利用率大大下降，
• 例如下圖，有的同學沒有特長有的同學特長卻非常多
  

順序文件（類線性表）

它的邏輯結構

而這里所提到的關鍵字可以看做是一個特征 這個特征唯一可以標識每個數據項（結點）
eg:就像上面的校園管理系統的例子中，我們的關鍵字就是學號，為什么不選擇姓名 作為我們的關鍵字呢，因為在一個龐大的校園里面很有可能出現重名的情況，而現在我們說的是單級目錄，單級目錄是不允許有重復項出現的

• “順序結構” 通常指線性結構（數據元素按線性關系排列，如線性表）
• “串結構” 是特殊的線性結構（數據元素僅為字符，如字符串）。

它的物理結構（存儲結構）

類似于我們順序表 我們對于它的存儲結構可以分為鏈式存儲（鏈表）和順序存儲（數組）
當然 對于鏈式存儲 不論采用上面哪種記錄方式 我們都得首元結點開始尋找，但是如果要進行增刪目錄是比較方便的

來看順序存儲結合我們前面提到的兩種記錄方式 ：

定長記錄下：

• 我們最理想的狀態就是采取順序存儲的定長記錄方式，這樣一來就可以擁有了數組的一大優勢，隨機存取，我們只需要知道首地址我們就可以根據每個記錄長度（數組每個元素的大小）以O(1)的時間來得到目標元素的位置
• 當前進一步采用順序結構（邏輯結構），那么我們是不是此時是不是就可以將它看做一個有序的數組，此時如果給定關鍵字（學號）我們是不是就可以采用二分查找的快速鎖定對應的記錄在這個目錄的位置呢
• 但是進一步采用串結構是不能做到快速查找這點的 具體原因如下（了解）：
• 串是 “字符序列” 的邏輯結構，沒有 “元素包含關鍵字” 的邏輯設計，缺乏 “關鍵字→元素” 的映射基礎；
• 串的操作圍繞字符序列處理，而非關鍵字的高效檢索，無法支持快速查找所需的索引或映射機制；
• 關鍵字目錄的本質是 “基于唯一標識的元素索引”，這與串結構的設計目標（處理字符序列）完全不匹配

可變長記錄下：

• 那么如果是可變長記錄那么就可以聯想到我們稀疏多項式的情況 這個時候由于采取的是可變長記錄方式我們并不知道每個記錄內容的長度，所以我們必須得一個一個順序的找

小結

索引順序文件與多級索引順序文件

形象化理解（很清晰）

• 對于單級：
  
• 對于多級索引：
  

結語

我覺得如果想要學好文件這一章，需要扎實的數據結構基礎，而這一章跟前面我們剛剛學習的基本存儲管理方式又有很多相似之處，
所以我建議把前面一章消化吸收之后 再來學這一章的內容更為合適一些 我感覺操作系統當中很多知識的大體框架都是差不多的 甚至于介紹順序和前因后果都差不多 只不過應用于不同的方面罷了 、
下一篇我會更新文件目錄部分 如果弄清楚了前面的多級頁表和DS當中的樹 會更好理解一些
******************************************************************************************* signed by 曦月逸霜