四、數(shù)據(jù)庫的存儲結(jié)構(gòu) 數(shù)據(jù)庫的存儲結(jié)構(gòu)不同于一般文件系統(tǒng)的存儲結(jié)構(gòu)。數(shù)據(jù)庫數(shù)據(jù)的特點是各種記錄型之間彼此有聯(lián)系，數(shù)據(jù)是結(jié)構(gòu)化的。數(shù)據(jù)的存儲結(jié)構(gòu)不僅涉及每種記錄型的記錄如何存儲，而且要使數(shù)據(jù)的存儲反映各種記錄型之間的聯(lián)系。在DB多級模式中引入內(nèi)模式（存儲模式）的主要目的是使模式的數(shù)據(jù)結(jié)構(gòu)的描述同它的存儲表示的描述分開，以致DBA為了協(xié)調(diào)數(shù)據(jù)庫性能而對數(shù)據(jù)庫數(shù)據(jù)的存儲方法進行修改時，可不必修改模式，以提高數(shù)據(jù)庫的物理獨立性。在各個數(shù)據(jù)庫管理系統(tǒng)中，對內(nèi)模式的定義功能各不相同。在關(guān)系數(shù)據(jù)庫管理系統(tǒng)中有些DDL語句可影響數(shù)據(jù)庫的存儲結(jié)構(gòu)。在DBMS中各級模式的存儲結(jié)構(gòu)是恒定的或唯一的，而數(shù)據(jù)庫內(nèi)容（或其記錄）的存儲方式是不唯一的。
數(shù)據(jù)庫存儲結(jié)構(gòu)設計的好壞直接影響系統(tǒng)的性能。在存儲結(jié)構(gòu)中主要是涉及存儲記錄的設計。存儲記錄與概念記錄之間具有對應關(guān)系，如果存儲記錄與概念記錄之間具有一一對應關(guān)系，在這種情況下存儲記錄的設計就比較簡單，不需要進一步討論。概念記錄是指在邏輯結(jié)構(gòu)中的記錄。但當一個概念記錄對應多個不同類型的存儲記錄時，存在如何設計存儲記錄的問題。對于這樣的概念記錄，其存儲記錄可以有以下幾種設計:
1.順序組織
將存儲記錄設計成與概念記錄一一對應，按SNO大�。ɑ虬从涗浀絹恚┑捻樞�?qū)⒂涗浗M成一個順序組織的文件。這樣組織的優(yōu)點是結(jié)構(gòu)簡單，缺點是會浪費存儲空間。
2.順序帶鏈的組織
順序帶鏈組織允許記錄中帶有指針（Pointer），這樣可以大大節(jié)省存儲空間。
3.帶次關(guān)鍵字索引的順序組織
為了適應對多項內(nèi)容的檢索，可以建立索引文件，上述組織可改為帶次關(guān)鍵字索引的順序組織。
4.多表組織
在次關(guān)鍵字索引中，由于一個次關(guān)鍵字值對應于多個記錄值，它們的個數(shù)是不固定的，所以對應的指針數(shù)目是可變的。這種可變性給管理帶來困難，為了解決這個困難，引入了多表組織。多表組織的實現(xiàn)思想比較簡單，在索引中多個指針分散存放在每個記錄值中，索引項中的指針指向第一個記錄，在第一個記錄中的指針指向第二個記錄等等。
5.完全倒排組織
在一個記錄型中，對主關(guān)鍵字以外的數(shù)據(jù)項都建立索引，這樣的組織稱之為完全倒排組織。
6.Hash定址組織
對于每一個存儲記錄值存放在數(shù)據(jù)庫的什么地方，可通過對該記錄的主關(guān)鍵字值的雜湊函數(shù)計算得出。這種組織為Hash定址組織。雜湊函數(shù)種類很多，如質(zhì)數(shù)除余法、基數(shù)轉(zhuǎn)換法、平方取中法、折疊法、位移法及各位數(shù)字分析法等等。關(guān)鍵是如何選擇一個雜湊函數(shù)，盡可能避免發(fā)生碰撞。對于不同的主關(guān)鍵字值通過計算而得到同一個地址的映象，稱之為碰撞。
7.聯(lián)系的存儲
在關(guān)系數(shù)據(jù)庫中，通過外來關(guān)鍵字（Foreign Key）來表示概念記錄之間的聯(lián)系。例如，為了表達學生和學校的聯(lián)系，可以在學生記錄中增加外來關(guān)鍵字“學校號”來表示聯(lián)系。如下圖所示。引入外來關(guān)鍵字實質(zhì)上是在邏輯結(jié)構(gòu)中就完成了聯(lián)系表示。在物理存儲時，只是把外來關(guān)鍵字作為一個普遍的屬性（或域）來處理。一般情況下，由于外來關(guān)鍵字要存儲多次，為節(jié)約空間和提高查詢速度而存其編號。
但在非關(guān)系模式的數(shù)據(jù)庫中，聯(lián)系是以特殊的方法實現(xiàn)的。有幾種方法，如鄰接法、鏈接法、位圖法和目錄法等等。在本書中不予以詳細討論。但是由于聯(lián)系和屬性本身的存儲不同，操作起來很不方便，也不直觀。
學生文件
學校號 學生號 姓名 年齡 其它
1 850301 小龍女 19 -
1 850302 王軍 20 -
3 850307 李明 21 -
4 850309 陳亮 22 -
2 850311 王海 20 -
學校文件
學校號 學校名 地址 其它
1 北方交大 北京 -
2 北 航 北京 -
3 北 大 北京 -
4 清 華 北京 -
5 哈工大 哈爾濱 -
外來關(guān)鍵字的引入
希望與更多計算機等級考試的網(wǎng)友交流，請進入計算機等級考試論壇
更多信息請訪問：考試吧計算機等級考試欄目
