IMS時代

• 問題
• 經(jīng)驗總結(jié)
• 分層數(shù)據(jù)邏輯模型
• 分層數(shù)據(jù)存儲格式
• 數(shù)據(jù)獨立性
• 數(shù)據(jù)操作
• 示例

問題

什么是數(shù)據(jù)獨立性筐高？為什么數(shù)據(jù)獨立性如此重要凡怎？

經(jīng)驗總結(jié)

1. 物理數(shù)據(jù)獨立性和邏輯數(shù)據(jù)獨立性非常重要芽腾；
2. 使用樹形數(shù)據(jù)模型有很大的約束，比如只有有限的物理數(shù)據(jù)獨立性等栈源；
3. 很難提供一種針對樹形數(shù)據(jù)的高效的邏輯重組逊抡；
4. 一次只操作一個記錄的接口需要程序員手動做查詢優(yōu)化，這很難火窒；

分層數(shù)據(jù)模型

• 記錄類型
  多個有數(shù)據(jù)類型的字段的集合硼补，比如Supplier(sno, sname, scity, sstate),Part (pno, pname, psize, pcolor)；
  所有記錄類型形成一個樹結(jié)構(gòu)熏矿；
  每個非根記錄類型都必須有一個父類記錄類型已骇；
  根記錄類型沒有父類記錄類型离钝；
• 記錄實例
  遵循記錄類型中對數(shù)據(jù)的定義；
• key
  唯一確定一個記錄實例褪储；
  由1個或者多個記錄類型的字段組成卵渴；
• HSK
  層級序列key；
  當(dāng)前記錄的HSK=先輩記錄的HSK+當(dāng)前記錄的HSK鲤竹；
  HSK定義為IMS數(shù)據(jù)庫中的所有記錄定義了一個全局序浪读，即：深度優(yōu)先，從左到右辛藻；
  為IMS數(shù)據(jù)操作語言DL/1提供了方便碘橘；
• IMS數(shù)據(jù)庫
  多個記錄類型的實例組成的集合；
  每個非根記錄實例都只有1個父類記錄類型揩尸；
  根記錄實例沒有父類記錄類型蛹屿；

數(shù)據(jù)操作語言DL/1

指令

• get next
  根據(jù)HSK順序，即深度優(yōu)先岩榆，從左到右错负，獲取下一個記錄；
• get next within parent
  在給定記錄的子樹中勇边，根據(jù)根據(jù)HSK順序犹撒，即按照從左到右的順序，獲取下一個記錄

實例

問題1 找出供應(yīng)商16提供的所有紅色零件粒褒。

Get unique Supplier (sno = 16) 
Until failure do
    Get next within parent (color = red)
    Enddo

思路：
第一步：找到供應(yīng)商16识颊；
先使用get next指令深入到供應(yīng)商記錄類型所在的層，然后再從左到右找到sno=16的供應(yīng)商奕坟；
第二步：遍歷供應(yīng)商16的子樹祥款，找出所有紅色零件；
備注：
(1) 多叉樹可以轉(zhuǎn)換為二叉樹月杉；
(2) 二叉樹中查詢效率最好的是什么樹刃跛？

層級數(shù)據(jù)存儲

先存儲根記錄，后存儲依賴根記錄的其他記錄苛萎；

如何存儲根記錄桨昙？

• 順序存儲；
• B-樹存儲腌歉，key是根記錄的HSK蛙酪；
• 哈希表存儲，key是根記錄的HSK翘盖；

在存儲好根記錄后桂塞，如何存儲相關(guān)的記錄？

• 順序存儲馍驯；
• 指針引用存儲藐俺；

為了避免可能產(chǎn)生的性能不佳問題炊甲，IMS對層級數(shù)據(jù)的存儲格式進(jìn)行了如下約束：

1. 如果根記錄和其他記錄都使用順序存儲，
   • 則不能使用DL/1命令來插入記錄欲芹；
   • 適用于這樣的批處理環(huán)境，即“old-master-new-master”處理：
     先將修改列表按照HSK排序吟吝，接著對舊數(shù)據(jù)庫進(jìn)行一次遷移菱父，同時將修改列表涉及的記錄插入到合適的位置，最后形成了新的數(shù)據(jù)庫剑逃；
2. 如果使用哈希表來存儲根記錄浙宜，則不能使用DL/1命令中的get next命令
   理由：使用哈希表實現(xiàn)順序查找并不容易；

這種約束有缺陷：

• 不能通過自由地切換存儲格式來對應(yīng)用進(jìn)行調(diào)優(yōu)蛹磺；
  理由：因為換了一種存儲格式后粟瞬，并不能保證針對原存儲格式編寫的DL/1程序能在新的存儲格式上繼續(xù)運行。

示例

假設(shè)有3個供應(yīng)商萤捆，分別是裙品，，俗或，其中的key是1市怎，的key是2，的key是3辛慰；
有3個零件区匠，分別是，帅腌，驰弄，其中的key是1，的key是2速客，的key是3戚篙；
其中，供應(yīng)零件和挽封，供應(yīng)零件已球，不供應(yīng)任何零件，沒有供應(yīng)商辅愿；
問題1：使用層級數(shù)據(jù)模型智亮，該如何描述上述信息？
(1) 假設(shè)Supplier記錄是Part記錄的父類点待，則有：

供應(yīng)商是零件的父類示意圖.png

• 零件的記錄實例存在重復(fù)存儲的問題阔蛉，不利于維護(hù)數(shù)據(jù)的一致性；
• 零件不存在任何供應(yīng)商癞埠，即不存在供應(yīng)商父類記錄状原，違反了IMS的數(shù)據(jù)模型約束規(guī)則：“任何一個非根記錄都必須有一個父類記錄”聋呢，則零件無法在這種IMS數(shù)據(jù)庫中存儲；

(2)假設(shè)Part記錄是Supplier記錄的父類颠区，則有：

零件是供應(yīng)商的父類示意圖.png

• 零件的記錄實例存在重復(fù)存儲的問題削锰，不利于維護(hù)數(shù)據(jù)的一致性；
• 零件不供應(yīng)任何零件毕莱，即不存在零件父類記錄器贩，違反了IMS的數(shù)據(jù)模型約束規(guī)則：“任何一個非根記錄都必須有一個父類記錄”，則零件無法在這種IMS數(shù)據(jù)庫中存儲朋截。

問題2 假設(shè)Supplier記錄是Part記錄的父類蛹稍，則如何計算上述信息的HSK?
答：的HSK是1，的HSK是2部服，的HSK是3唆姐；
的子類中的的HSK是11，的子類中的的HSK是21廓八，的HSK是12奉芦；