習題題庫 [第九章：資料儲存結構]
習題9-1

假設一個硬碟頁佔 4KB，現在你有一個包括10 萬筆記錄的資料表，每一筆記錄長度為 128B，平均每一個資料頁是 50% 滿。請問該資料表需要幾個硬碟頁？
(資料頁最前面和最後面的指標可以忽略)。
 
習題9-2
假設一個硬碟頁佔 4KB，一個索引值 (欄位值) 佔20B，一個記錄指標佔18B，一個節點指標佔 16B，此外，除根節點外的每一節點是 70% 滿。請問要容納10 萬筆記錄需要幾層的 B+-tree？
 
習題9-3
假設一個硬碟頁有 2KB 容量，一個節點指標佔 8B，一個記錄指標佔 10B。考慮圖 4-3 的資料表 Product，假設 unitPrice 欄位值佔 8B，catalog 欄位值佔20B，並且資料表 Product 裡有 500,000 筆記錄。
考慮以下兩個索引：
CREATE INDEX I1
ON Product (unitPrice);
CREATE INDEX I2
ON Product (unitPrice, catalog);
請問，
1. I1 的B+-tree 至少有幾層？每一層各有幾個節點？
2. I2 的B+-tree 至少有幾層？每一層各有幾個節點？
 
習題9-4
假設你依以下SQL 敘述建立了一個索引I3。
CREATE INDEX I3
ON Product (catalog DESC, unitPrice DESC);
以圖4-4 的資料庫為例，請仿圖9-7 畫出I3 的索引結構。
 
習題9-5
有些 DBMS 在建立資料表時，會主動為主鍵建立一個群聚索引。考慮圖4-4的範例資料庫中的Product 資料表，假設DBMS 主動建立以下群聚索引：
CREATE INDEX ProductCluster
ON Product (pNo)
CLUSTER;
1. 以圖4-4 的資料庫為例，仿圖9-6 畫出資料表Product 和索引ProductCluster 的實體結構示意圖，假設一個硬碟頁只能容納4 個Product 記錄，B+-tree 的每一葉節點最多能容納2 個記錄指標，而每一中間節點最多能容納3 個節點指標。
2. 請畫出加入以下一筆Product 記錄後，資料表Product 和索引ProductCluster 的實體結構示意圖。
(‘b50000’, ‘資料庫微調’, 600, ‘Book’)
 
習題9-6
考慮圖4-4 線上購物系統的資料庫。假設 B+-tree 的每一葉節點最多能容納 2 個記錄指標，而每一中間節點最多能容納3 個節點指標。
1. 畫出以下索引的B+-tree (請參考圖9-7)
CREATE INDEX I2
ON Product (unitPrice DESC, catalog ASC);
2. 考慮以下的查詢句：
SELECT *
FROM Product
WHERE catalog = ‘Book’ AND unitPrice < 580;
若使用圖9-7 的I1 索引結構，要造訪幾個葉節點？若使用本題的I2 索引結構，要造訪幾個葉節點？
 
習題9-7

考慮圖4-4 的Product 資料表和以下兩個索引：

CREATE INDEX I1
ON Product (unitPrice, catalog)
CREATE INDEX I2
ON Product (catalog, unitPrice)

假設以上索引的 B+-tree 的每一葉節點最多能容納2 個記錄指標，而每一中間節點最多能容納3 個節點指標。

1. 仿圖9-7 畫出I1 和I2 的B+-tree。
2. 考慮以下的查詢句：
SELECT *
FROM Product
WHERE catalog = ‘Book’AND unitPrice >= 300;
A. 若採用I1 的索引，欲找出所有滿足條件的記錄指標，需造訪幾個葉節點？
B. 若採用I2 的索引，欲找出所有滿足條件的記錄指標，需造訪幾個葉節點？
3. 考慮以下的查詢：
SELECT *
FROM Product
WHERE catalog >= ‘CD’AND unitPrice >= 400;
A. 若採用I1 的索引，欲找出所有滿足條件的記錄指標，需造訪幾個葉節點？
B. 若採用I2 的索引，欲找出所有滿足條件的記錄指標，需造訪幾個葉節點？
4. 請討論為何B+-tree 不適合作多維度的查詢。
 
習題9-8
考慮以下的查詢句：
SELECT *
FROM Member
WHERE address LIKE ‘%中華%台北%’;
假設你有一個如圖9-12 的Suffix tree，請說明其搜尋過程。