軟件設計2

1、文件管理

1.1、索引文件結構

索引文件結構中，直接索引即索引直接指向物理塊，有多少個直接索引，通過直接索引就能訪問多少個物理塊。

一級索引，即索引節點指向的物理塊用來存放地址項，一個物理塊能表示多少個地址項，則一個一級索引就能表示多少個物理塊。

二級索引，即索引節點指向的物理塊，存放的是一級索引的地址塊地址，一個物理塊能表示 n 個地址項，則一個二級索引就能表示 n² 個物理塊。

例題：

2、設備管理

2.1、數據傳輸控制方式

程序控制方式：程序控制方式也叫查詢控制方式。當程序要傳輸數據時，CPU發出I/O指令。CPU定期地查詢I/O系統，確定操作是否已經完成。由CPU主動查詢I/O系統，完成主機與外部設備間的數據傳輸。方法簡單，硬件開銷小，但CPU因要不停執行查詢操作，降低了效率。
程序中斷方式：使用程序中斷方式，當I/O系統與外部設備傳輸數據時，CPU無須等待，也不必去查詢I/O系統的狀態，當I/O系統完成了數據傳輸后，以中斷信號通知CPU。CPU保存正在執行程序的現場，轉入I/O中斷服務程序完成與I/O系統的數據交換，然后返回原主程序繼續執行。中斷方式因為CPU無需等待而提高了效率。
DMA（直接內存存取）方式：DMA控制方式是在主存和外設之間直接建立數據通路進行數據的交換處理。DMA方式是使用DMA控制器來管理和控制數據傳輸的。

2.2、微內核操作系統

3、數據庫系統

3.1、三級模式兩級映射

數據庫領域公認的標準結構是三級模式結構，它包括外模式、概念模式和內模式，有效地組織、管理數據，提高了數據庫的邏輯獨立性和物理獨立性。外模式 --- 視圖，內模式 --- 存儲文件，概念模式 --- 基本表

外模式又稱子模式或用戶模式，對應于用戶級。它是某個或某幾個用戶所看到的數據庫的數據視圖，是與某一應用有關的數據的邏輯表示。用戶可以通過外模式描述語言來描述、定義對應于用戶的數據記錄(外模式)，也可以利用數據操縱語言(Data Manipulation Language，DML)對這些數據記錄進行操作。

概念模式又稱模式或邏輯模式，對應于概念級。它是由數據庫設計者綜合所有用戶的數據，按照統一的觀點構造的全局邏輯結構，是對數據庫中全部數據的邏輯結構和特征的總體描述，是所有用戶的公共數據視圖(全局視圖)。它是由數據庫管理系統提供的數據模式描述語言(Data Description Language，DDL)來描述、定義的。

內模式又稱存儲模式，對應于物理級。它是數據庫中全體數據的內部表示或底層描述，是數據庫最低一級的邏輯描述，它描述了數據在存儲介質上的存儲方式和物理結構，對應著實際存儲在外存儲介質上的數據庫。

總之，數據按外模式的描述提供給用戶；按內模式的描述存儲在磁盤上；而概念模式提供了連接這兩級模式的相對穩定的中間層，并使得兩級中任意一級的改變都不受另一級的牽制。

3.2、關系代數

笛卡爾積（x）也就是S1的每個記錄分別跟S2的所有記錄的組合。

自然連接（）：

3.3、規范化理論

超鍵就是能唯一確定記錄的屬性集，比如：學號+姓名+年齡。候選鍵就是超鍵去除掉多余屬性后的屬性，比如學號本身就可以確定唯一記錄，所以姓名和年齡都是多余的，學號就是候選鍵。候選鍵可能有多個，比如學號、身份證號，此時可以任選一個作為數據庫表的主鍵。

如何求候選鍵：

也就是，先畫有向圖，如果有入度為0的屬性（入度為0就是說沒有箭頭指向它），那就找入度為0的屬性，以它為起點，如果能走遍全部結點（不一定要一次性走遍），那該屬性就是候選鍵。如果入度為0的屬性不能遍歷全部結點，那就找既有入度又有出度的結點，如果該結點能遍歷全部屬性，那該結點就是候選鍵。

例題：

第一題，先畫出有向圖，可以知道A1入度為0，以A1為起點，能走遍全部結點，所以A1就是候選鍵。

第二題，畫出有向圖，可以看到只有ABCD組合起來才能遍歷全部屬性，所以候選鍵就是ABCD。

第三題，有向圖中沒有入度為0的屬性，那就找到既有入度又有出度的結點，可以看到A和B都能遍歷所有結點，所以答案選B：A和B

3.4、范式

范式級別越高越規范，想達到高范式，必先達到低范式的要求。一個低一級的關系模式通過模式分解可以轉化為若干個高一級范式的關系模式的集合，這個過程叫做規范化。

3.4.1、第一范式

屬于第一范式關系的所有屬性都不可再分，即數據項不可分。第一范式強調數據表的原子性，是其他范式的基礎。如下圖所示數據庫就不符合第一范式：

上表將商品這一數據項又劃分為名稱和數量兩個數據項，故不符合第一范式關系。改正之后如下圖所示：

上表就符合第一范式關系。

但日常生活中僅用第一范式來規范表格是遠遠不夠的，依然會存在數據冗余過大、刪除異常、插入異常、修改異常的問題，此時就需要引入規范化概念，將其轉化為更標準化的表格，減少數據依賴。

3.4.2、第二范式（消除了部分函數依賴）

第二范式存在數據冗余、更新異常、插入異常、刪除異常的問題。如果滿足第一范式，并且主鍵只有一個屬性的那就一定是第二范式。如果主鍵只有一個屬性值那就意味著已經消除了部分函數依賴。

比如：一個表中有學號、課程號、成績、學分。學號+課程號組成主鍵，成績完全依賴主鍵，而學分部分依賴主鍵，因為課程號就能確定學分，所以不符合第二范式。

3.4.3、第三范式（消除部分函數依賴和傳遞函數依賴）

滿足第二范式，并且非主屬性沒有傳遞依賴于主鍵時，就是第三范式。

比如：學號、姓名、系號、系名、系樓層，學號是主鍵，此時就不滿足第三范式，因為學號確定系號，系號又確定系名、系樓層，此時存在傳遞依賴。也就是非主屬性全部都是直接依賴于主鍵，而不是間接依賴于主鍵。

3.4.4、BCNF（BC范式）

也就是說把所有的依賴集都列出來，而左邊的部分必定是候選鍵的就滿足BC范式。

例題：

候選鍵有SJ和TJ，所有的依賴集有：SJ -> T，T -> J，而依賴集所有的左邊部分SJ是候選鍵，但T不是候選鍵，所以不滿足BC范式。

3.5、并發控制

3.6、數據庫完整性約束

實體完整性：實體完整性是指關系中的主屬性值不能為Null且不能有相同值。

參照完整性：參照完整性是指關系中的外鍵必須是另一個關系的主鍵有效值，或者是NULL。

用戶定義的完整性：

3.7、數據備份

4、計算機網絡

基于TCP：HTTP、FTP、Telnet、SMTP等等

基于UDP：SNMP、DNS等等

4.1、特殊含義的IP地址

5、加密技術

5.1、對稱秘鑰加密算法

對稱加密算法又稱共享秘鑰加密。

5.2、非對稱秘鑰加密算法

非對稱秘鑰加密算法又稱公開秘鑰加密。

例題：設計一個郵件加密系統

郵件內容大，所以使用對稱加密算法加密郵件內容。對稱加密算法的秘鑰使用 B 的公鑰進行加密，B接收到后就可以使用自己的私鑰進行解密，得到對稱加密的秘鑰，解密出郵件內容。要想做到不可抵賴，先生成一個郵件摘要，然后使用 A 的私鑰加密，B 接收到后使用 A 的公鑰解密得到摘要明文，并且用郵件內容生成摘要，摘要對比正確就說明內容沒有被篡改。因為是用 A 的公鑰進行解密的，可以證明這個文件確確實實是 A 發送來的，因為其他人并沒有 A 的私鑰。