DBMS - 索引

我們知道資料以記錄的形式儲存。每個記錄都有一個鍵欄位，它有助於唯一識別該記錄。

索引是一種資料結構技術，可以根據已進行索引的某些屬性有效地從資料庫檔案中檢索記錄。資料庫系統中的索引類似於我們在書籍中看到的索引。

索引基於其索引屬性定義。索引可以分為以下型別：

• 主索引 - 主索引定義在有序資料檔案上。資料檔案根據鍵欄位排序。鍵欄位通常是關係的主鍵。

• 次索引 - 次索引可以從候選鍵欄位（每個記錄中都有唯一值）或具有重複值的非鍵欄位生成。

• 聚簇索引 - 聚簇索引定義在有序資料檔案上。資料檔案根據非鍵欄位排序。

有序索引分為兩種型別：

• 稠密索引
• 稀疏索引

稠密索引

在稠密索引中，資料庫中的每個搜尋鍵值都有一個索引記錄。這使得搜尋速度更快，但需要更多空間來儲存索引記錄本身。索引記錄包含搜尋鍵值和指向磁碟上實際記錄的指標。

稀疏索引

在稀疏索引中，並非為每個搜尋鍵建立索引記錄。這裡的索引記錄包含一個搜尋鍵和指向磁碟上資料的實際指標。要搜尋記錄，我們首先透過索引記錄併到達資料的實際位置。如果我們正在查詢的資料不在我們直接透過索引到達的位置，則系統開始順序搜尋，直到找到所需的資料。

多級索引

索引記錄包含搜尋鍵值和資料指標。多級索引與實際資料庫檔案一起儲存在磁碟上。隨著資料庫大小的增長，索引的大小也會增長。迫切需要將索引記錄儲存在主記憶體中，以加快搜索操作。如果使用單級索引，則大型索引無法儲存在記憶體中，這會導致多次磁碟訪問。

多級索引有助於將索引分解成多個較小的索引，以便使最外層級別足夠小，可以儲存在單個磁碟塊中，這可以很容易地容納在主記憶體中的任何位置。

B⁺樹

B⁺樹是一種平衡的二叉搜尋樹，它遵循多級索引格式。B⁺樹的葉節點表示實際資料指標。B⁺樹確保所有葉節點保持相同的高度，因此是平衡的。此外，葉節點使用連結串列連結；因此，B⁺樹可以支援隨機訪問和順序訪問。

B⁺樹的結構

每個葉節點與根節點的距離相等。B⁺樹的階數為n，其中n對於每個B⁺樹都是固定的。

內部節點 -

• 內部（非葉）節點至少包含⌈n/2⌉個指標，根節點除外。
• 最多，一個內部節點可以包含n個指標。

葉節點 -

• 葉節點至少包含⌈n/2⌉個記錄指標和⌈n/2⌉個鍵值。
• 最多，一個葉節點可以包含n個記錄指標和n個鍵值。
• 每個葉節點都包含一個塊指標P，指向下一個葉節點並形成一個連結串列。

B⁺樹插入

• B⁺樹從底部填充，每個條目都在葉節點處完成。

• 如果葉節點溢位 -

  • 將節點分成兩部分。

  • 在i = ⌊(m+1)_/2⌋處劃分。

  • 前i個條目儲存在一個節點中。

  • 其餘條目（從 i+1 開始）移動到一個新節點。

  • i^th鍵在葉節點的父節點中被複制。

• 如果非葉節點溢位 -

  • 將節點分成兩部分。

  • 在i = ⌈(m+1)_/2⌉處劃分節點。

  • 最多i個條目儲存在一個節點中。

  • 其餘條目移動到一個新節點。

B⁺樹刪除

• B⁺樹條目在葉節點處刪除。

• 搜尋並刪除目標條目。

  • 如果是內部節點，則刪除並用左側條目的條目替換。

• 刪除後，測試下溢，

  • 如果發生下溢，則從左側節點分配條目。

• 如果無法從左側分配，則

  • 從右側節點分配條目。

• 如果無法從左側或右側分配，則

  • 將節點與其左側和右側節點合併。