國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

111年關務三等資料庫應用

答：

MEMBER資料表：

(一)樹狀結構

1.定義：

  利用 B-Tree 的結構改良，將資料儲存於終端節點，最上階層的節點只包含鍵值和指向其他節點的指標。也就是說只有葉節點的索引記錄才含有資料指標，其餘的節點中僅含有單純的索引值。

2.節點結構：

  B⁺ 樹的內部節點，它有 q-1 個搜尋值；B⁺ 樹的葉端節點，它有 q-1 個搜尋值和 q-1 個資料指標。

3.內部節點(internal node)：

  (1)每個內部節點的形式如下：

    <P₁, K₁, P₂, K₂, …, P_q-1, K_q-1, P_q>

    其中 q ≤ p 且 P_i 是樹指標 (tree pointer)。

  (2)在每個內部節點中，K_l < K₂ < … < K_q-1。

  (3)對於 P_i 所指的子樹中所有的搜尋鍵值欄位值 X，以下條件會成立：

    當1 < i < q時，K_i-1 < X < K_i，當 i = 1 時，X < K_i， 當 i = q 時，K_i-1 < X。

  (4)每個內部節點最多有 p 個樹指標。

  (5)除了根節點之外的每個內部節點，至少有  個樹指標。假如它是個內部節點，則它至少有兩個樹指標。

  (6)內部節點有 q 個指標和 q-1 個搜尋欄位值，其中 q ≤ p。

4.葉節點(leaf node)：葉端節點

  (1)每個葉節點的形式如下：

    <<K₁, Pr₁>, <K₂, Pr₂>, … , <K_q-1, Pr_q-1>, P_next>

    其中 q ≤ p 且每個 Pr_i 是個資料指標，P_next 指向 B⁺ 樹的下一個樹葉節點。

  (2)在每個葉節點中，K_l < K₂ < … < K_q-1，其中 q ≤ p。

  (3)每個 Pr_i 是一個資料指標 (data pointer)，它指向搜尋欄位值為 K_i 的記錄，或者是包含該記錄的檔案區塊 (若搜尋欄位不是鍵值，則 Pr_i 指向一個包含數個指標的區塊，區塊中的指標指向搜尋欄位值為 K_i 的記錄)。

  (4)每個葉節點至少有 個值。

  (5)所有葉節點的層級相同。

(二)資料庫系統如何利用該索引結構，提升SQL查詢句的處理效能

1.假設透過某個函式可以取出末三碼的整數，例如 M001 透過某個函式可以取出1；M002 透過某個函式可以取出2；M128 透過某個函式可以取出128。並且將取出末三碼的整數產生一棵 B⁺ 樹。

2.當搜尋 M001 時，從樹根3往下搜尋，只需要比較2次。可以得知 M001 儲放在 p3 區塊中的第1筆紀錄；當搜尋 M005 時，從樹根3往下搜尋，只需要比較2次。可以得知 M005 儲放在 p7 區塊中的第1筆紀錄。如果搜尋 M005 時不是使用 B⁺ 樹索引結構，那麼必須逐筆搜尋，也就是要搜尋5次才能找到資料，因此使用此索引結構可以加快搜尋資料的速度。

※參考資料：

1.https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

2.黃三益-資料庫的核心理論與實務第五版 p.287~p.288