chap6數(shù)據(jù)庫的存儲結(jié)構(gòu)(已改無錯字)
2022-09-01 10:11:49 本頁面
【正文】 2 2 LIU A102 600 3 3 WEN B103 750 4 4 LI C104 800 5 5 CAI D105 600 6 6 Dong E201 800 7 7 Qiao F304 700 He 1 Wen 3 Cai 5 36 （ 3）多級索引 ? 如果索引塊數(shù)多，那么可以為索引塊再建立一級稀疏索引，即對每個索引塊建立一個索引記錄。 ? 為了查找記錄，可以在外層索引使用二分法查找，找到一個索引記錄，該索引記錄的查找鍵值小于或等于給出查找鍵值的最大一個鍵值；然后沿著索引記錄中的指針到達(dá)內(nèi)層索引塊；在內(nèi)層索引塊可用順序查找或二分查找也可找到相應(yīng)的索引記錄；然后沿著這個索引記錄中的指針到達(dá)主文件的某個數(shù)據(jù)塊；在數(shù)據(jù)塊中沿著指針鏈查找記錄。 167。 主索引 37 多級索引 167。 主索引 …… …… 數(shù)據(jù)塊 0 數(shù)據(jù)塊 1 數(shù)據(jù)塊 n1 數(shù)據(jù)塊 n … 索引塊 1 索引塊 0 …… 外層索引 38 （ 4）索引更新 ? 刪除操作 – 找到被刪記錄，如果被刪除的記錄在文件中只有一個，那么刪除后肯定要修改索引 – 對于稠密索引，要刪除相應(yīng)的索引記錄； – 對于稀疏索引，如果被刪記錄的查找鍵值在索引塊中出現(xiàn)，那么用下一個鍵值替換，如果下一個鍵值在索引中存在，那么刪除相應(yīng)的索引記錄 167。 主索引 39 （ 4）索引更新 ? 插入操作 – 用插入記錄的查找鍵值找到插入位置 – 對于稠密索引，如果沒有該鍵值，則插入到索引塊中 – 對于稀疏索引，如果當(dāng)前數(shù)據(jù)塊能放下新記錄，則不必修改索引；如果要插入新的數(shù)據(jù)塊，那么插入記錄的查找鍵值將成為新數(shù)據(jù)塊的第一個查找鍵值，并在索引塊中插入一個新的索引記錄。 167。 主索引 40 ? 可以根據(jù)另一個查找鍵值尋找主文件的記錄 ? 實現(xiàn)方法： 仍然為每個查找鍵值建立一個索引記錄，內(nèi)容包括查找鍵值和一個指針，指針指向一個桶，桶內(nèi)存放指向具有同一查找鍵值的主記錄的指針。 167。 41 輔助索引 167。 2 800 F128 He 1 7 6 5 4 3 2 6 600 D105 CAI 7 800 E201 Dong 700 F304 Qiao 5 800 C104 LI 4 750 B103 WEN 3 600 A102 LIU 800 750 700 600 桶 42 平衡樹的概念 定義 一棵 m階平衡樹或者為空，或者滿足以 下條件： 1)每個結(jié)點至多有 m棵子樹； 2)根結(jié)點或為葉結(jié)點，或至少有兩棵子樹； 3)每個非葉結(jié)點至少有 [m/2]棵子樹； 4)從根結(jié)點到葉結(jié)點的每一條路徑都有同樣的長度，即葉結(jié)點在同一層次上。 平衡樹又分兩類： B+樹和 B樹 167。 B+樹索引文件 43 B+樹的結(jié)構(gòu) 在實際使用中， B+樹有很多形式，下面介紹其中的一種。 一棵 m階 B+樹是平衡樹，按下列方式組織： 1) 每個結(jié)點中至多有 m1個查找鍵值 K1,K2,… ,KM1, m個指針 P1,P2,… ,PM ,如圖所示。 2）葉結(jié)點的組織方式 葉結(jié)點中的指針（ 1=i=m1）指向主文件中的記錄。例如 Pi指向查找鍵值為 Ki的主記錄。 167。 B+樹索引文件 P1 K1 P2 … PM1 KM1 PM 44 3）非葉結(jié)點的組織方式 B+樹中的非葉結(jié)點形成了葉結(jié)點上的一個多級稀疏索引。每個非葉結(jié)點（不包括根結(jié)點）中至少有 [m/2]個指針，至多有 m個指針。 B+樹的查詢 如果用戶要檢索查找鍵值 K的所有記錄，那么
研究報告相關(guān)推薦
鄂ICP備17016276號-1