第九章索引技術 本章的基本内容是 索引的基本概念線性索引技術樹形索引 9 1索引的基本概念 資料結構的最終目的是提高資料的處理速度 索引是為了加快查找速度而設計的一種資料結構 索引技術是組織大型資料庫以及磁盤檔案的一種重要技術 在索引問題以及資料庫中 常常将資料元素稱為記錄 檔案 通常指存儲在外存上的記錄集合 索引 把一個關鍵碼與它對應的記錄相關聯的過程 索引由若幹索引項構成 索引項至少應包含關鍵碼和關鍵碼對應的記錄在存儲器中的位置等資訊 靜态索引 索引結構在檔案建立時生成 一旦生成就固定下來 隻有當檔案再組織時才允許改變 動态索引 在檔案建立時生成索引結構 在檔案執行插入 删除等操作時 索引結構本身也随之發生改變 9 1索引的基本概念 線性索引 若将索引項組織為線性結構 則稱其為線性索引或索引表 樹形索引 若将索引項組織為樹結構 則稱其為樹形索引 多級索引 對索引再建立一個索引 就構成了多級索引 9 1索引的基本概念 對一些大型檔案 其索引本身可能也很大 在這種情況下 可以建立多級索引 稠密索引 線上性索引中 若檔案中的每個記錄對應一個索引項 則這種索引稱為稠密索引 在稠密索引中 無論檔案是否按關鍵碼有序 索引項總是按關鍵碼順序排列 隻要記憶體空間允許 通常把稠密索引存儲在記憶體中 進而大大提高記錄的查找速度 9 2 1稠密索引 稠密索引主要适用于靜态索引 稠密索引示例 有序 無序或有序 優點 實作對資料庫記錄有效的查找 采用折半查找技術 和随機通路 按記錄号通路 缺點 如果檔案中包含的記錄太多 索引表本身可能會因為太大而無法在記憶體中存儲 檔案中插入或删除記錄 必須更新稠密索引 而稠密索引的插入和删除操作代價很高 稠密索引 檔案 外存 稠密索引 記憶體 9 2 2分塊索引 稠密索引空間代價很大 分塊索引 分塊索引需要将檔案劃分為若幹塊 且要求分塊有序 多級索引 分塊索引 有序 分塊索引 在分塊索引表中進行的查找稱為分塊查找 也稱為索引順序查找 分兩步進行 在索引表中确定待查關鍵碼所在的塊 在相應塊中查找待查關鍵碼 塊内查找 順序查找 設有n個記錄的檔案分為m個塊 每個塊均為t個記錄 則n m t 設Lb為查找索引表确定關鍵碼所在塊的平均查找長度 Lw為在塊内查找關鍵碼的平均查找長度 則分塊查找的平均查找長度為 ASL Lb Lw若采用順序查找對索引表進行查找 則分塊查找的平均查找長度為 分塊索引 ASL Lb Lw 9 2 3多重表 稠密索引 分塊索引 對主關鍵碼建立索引 為檔案建立索引的目的是什麼 對主關鍵碼進行查找 對次關鍵碼進行查找 對次關鍵碼建立索引 多重表 倒排表 多重表 多重表除了為檔案建立一個主索引外 還為每個需要查找的次關鍵碼建立一個索引 在檔案中 為建立索引的次關鍵碼分别增設一個指針域 用于将次關鍵碼相同的記錄鍊結在一起 稠密索引 或将在同一塊中的記錄鍊結在一起 分塊索引 多重表 9 2 4倒排表 9 3樹形索引 9 3 12 3樹 2 3樹 是具有下列特性的樹 一個結點包含1個或者2個關鍵碼 每個内部結點有2個子女 包含一個關鍵碼 或者3個子女 包含兩個關鍵碼 所有葉子結點都在樹的同一層 2 3樹示例 形狀上有什麼特性 2 3樹示例 包含1個或者2個關鍵碼 有2個子女或者3個子女 葉子結點在同一層 2 3樹示例 結點的值有什麼特性 2 3樹示例 左子樹中所有結點的值均小于第一個關鍵碼的值 中間子樹中所有結點的值均大于第一個關鍵碼的值 且小于第二個關鍵碼的值 右子樹中所有結點的值均大于第二個關鍵碼的值 2 3樹 查找操作 21 18 21 33 21 23 2 3樹 插入操作 新記錄将插入到相應的葉子結點中 1833 2 3樹 插入操作 新記錄将插入到相應的葉子結點中 2 3樹 插入操作 新記錄将插入到相應的葉子結點中 2 3樹 插入操作 新記錄将插入到相應的葉子結點中 1833 12 2330 48 10 15 2021 24 31 4547 505255 插入 2 3樹 插入操作 新記錄将插入到相應的葉子結點中 1833 12 2330 48 10 15 2021 24 31 4547 分裂 50 55 52 2 3樹 插入操作 新記錄将插入到相應的葉子結點中 1833 12 2330 10 15 2021 24 31 4547 提升 50 55 4852 2 3樹 删除操作 情況1 從包含2個記錄的葉子結點删除1個記錄 解決方法 直接删除這個記錄 1833 12 2330 48 10 15 24 31 4547 5052 2 3樹 删除操作 情況1 從包含2個記錄的葉子結點删除1個記錄 解決方法 直接删除這個記錄 21 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 向兄弟結點借一個記錄 同時修改雙親結點的記錄 1833 12 2130 48 10 15 20 23 31 4547 5052 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 向兄弟結點借一個記錄 同時修改雙親結點的記錄 1833 12 2130 48 10 15 20 23 31 4547 5052 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 兄弟結點不夠借 需要合并相鄰結點 并影響雙親結點 1833 12 2021 48 10 15 30 31 4547 5052 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 兄弟結點不夠借 需要合并相鄰結點 并影響雙親結點 1833 12 2021 48 10 15 30 31 4547 5052 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 兄弟結點不夠借 需要合并相鄰結點 并影響雙親結點 2021 48 33 31 4547 5052 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 1012 1830 解決方法 兄弟結點不夠借 需要合并相鄰結點 并影響雙親結點 48 33 30 4547 5052 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 兄弟結點不夠借 需要合并相鄰結點 并影響雙親結點 這可能減少樹的高度 25 20 2 3樹 删除操作 情況2 從包含1個記錄的葉子結點中删除這個記錄 解決方法 兄弟結點不夠借 需要合并相鄰結點 并影響雙親結點 這可能減少樹的高度 2 3樹的優點 能夠以相對較低的代價保持樹高平衡 2 3樹 删除操作 情況3 從内部結點删除一個記錄 解決方法 将被删除記錄用右邊子樹中的最小關鍵碼Y代替 Y一定在某個葉子結點中 然後再删除Y 2 3樹 删除操作 情況3 從内部結點删除一個記錄 解決方法 将被删除記錄用右邊子樹中的最小關鍵碼Y代替 Y一定在某個葉子結點中 然後再删除Y 2033 12 2330 48 10 15 21 24 31 4547 5052 9 3 2B 樹 m階B 樹 是滿足下列特性的樹 所有葉子結點都在同一層上 并且不帶資訊 葉子的雙親稱為終端結點 樹中每個結點至多有m棵子樹 若根結點不是終端結點 則至少有兩棵子樹 除根結點外 其他非終端結點至少有 m 2 棵子樹 B 樹是2 3樹的推廣 2 3樹是一個3階B 樹 所有非終端結點都包含以下資料 n A0 K1 A1 K2 Kn An 其中 n m 2 1 n m 1 為關鍵碼的個數 Ki 1 i n 為關鍵碼 且Ki Ki 1 1 i n 1 Ai 0 i n 為指向子樹根結點的指針 且指針Ai所指子樹中所有結點的關鍵碼均小于Ki 1大于Ki B 樹 118 111 127 139 3475364 199 F F F F F F F F F F F F 24378 135 B 樹示例 一棵4階B 樹 思考4階B 樹的最少關鍵字和最多關鍵字數 B 樹的查找 查找47 查找成功 B 樹的查找 查找23 查找不成功 B 樹的查找分析 B 樹的查找包含兩種基本操作在B 樹中找結點 在磁盤上找 找到結點塊後 調入記憶體 在結點中找關鍵字 結點塊調入記憶體後 在記憶體中找 記憶體的查找速度遠遠高于磁盤的查找速度B 樹的查找效率取決于在磁盤上查找的次數 即待查關鍵字所在結點在B 樹的層次數 也就是N個關鍵字的m階B 樹的最大深度是多少 按最壞情況計算 B 樹的插入 基本思想每次插入一個關鍵字是在最底層的某個非終端結點添加一個關鍵字 若該結點的關鍵字個數不超過m 1 則插入完成 否則 産生 分裂 B 樹就是從空樹開始 逐個插入關鍵字而生成的 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 3037 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 3037 263037 2430 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 45 2430 5390 312 50 6170 100 a b c e f g h bt 617085 537090 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 45 2430 5390 312 50 100 a b c e f h bt 537090 4570 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 45 2430 312 a b c bt 4570 3712 72430 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 45 2430 a b bt 4570 72430 244570 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 45 a bt 4570 244570 在3階B 樹 略去葉子 中插入關鍵字30 26 85 7 B 樹的删除 基本思想首先找到該關鍵字所在的結點 并從中删除該關鍵字 若該結點為最下層的非終端結點 且其關鍵字數目不少于 m 2 則删除完成 否則進行 合并 結點的操作 若所删關鍵字為非終端結點中Ki 則可以指針Ai所指子樹中的最小關鍵字Y替代Ki 然後在相應的結點中删去Y 在3階B 樹 略去葉子 中删除關鍵字12 50 53 37 6190 70 53 6170 90 3 在3階B 樹 略去葉子 中删除關鍵字12 50 53 37 45 24 90 3 37 6170 100 324 324 在3階B 樹 略去葉子 中删除關鍵字12 50 53 37 45 90 6170 100 4590 90 9 3 4B 樹 m階B 樹 是滿足下列特性的樹 含有m個關鍵碼 每一個關鍵碼對應一棵子樹 關鍵碼Ki是它所對應的子樹的根結點中的最大 或最小 關鍵碼 所有終端結點中包含了全部關鍵碼資訊 以及指向關鍵碼記錄的指針 所有終端結點按關鍵碼的大小鍊在一起 形成單連結清單 并設定頭指針 L B 樹示例 5090 2050 608090 121620 263050 5560 627080 828690 一棵3階的B 樹 指向相應的記錄 指向樹根 可以随機查找 指向最小葉結點 可以進行順序查找 查找時 若非終端結點的關鍵字等于給定值 并不終止 而是繼續向下 直到葉子結點
展開閱讀全文