數據庫索引：例

Question

我很快就會有一個考試，我想知道如何解決關於索引這些問題：

1.A數據庫由一個關係R（A，B，C）。 A和B是整數[0,10 000]（各4B），C是varchar（20）（20B）。關係R由10^6個元組組成。該塊大小爲2048 B.

A）有多少塊做，我們要讀（最佳和最差），如果我們問這個查詢，如果我們對B中的B +樹索引：

選擇C從r WHERE A = 100和B = 10

B）索引A有意義嗎？如果是的話，什麼類型的最好？

另一個類似的問題是：

2.A數據庫包括關係R（A，B，C）的。 A和B是整數[0,10 000]，C是varchar（150）。關係R由10^6個元組組成。塊大小是2048B，A，B是鍵。

A）有多少塊做我們，如果我們問查詢到在讀最好的和最壞的情況下「選擇C從r其中A = 4711和：

• 我們沒有索引
• 我們有一個b +上的一個樹索引和B.

二）是否有意義到索引A separetely和A的separetely而不是在A和b有一個索引什麼類型的indeces的是最好的？

EDIT：

以下是我已經做：

問題1 A）

元組是大小= 20 + 4 + 4 = 28乙

的

2048/28 = 73個元組/塊向下舍入

10^6/73 = 13 699個塊的整個關係向上取整

Indexreadings： 4 * N + 4（N + 1）< = 2048 B => N = 255捨去

B +樹的第一級= 255 < 10^6 否

B +樹的第二級= 255 * 256 < 10^6 否

B +樹的第三級= 255 * 256 * 257> 10^6 是10^6元組可以適合在高度爲3的B +樹中。

Datareadings： 如果我們假設A = 100具有概率一萬零一分之一和B = 10具有相同的概率則有：

10001分之1*10001分之1* 10^6圍捕= 1元組

在最壞和最好的情況：1元組= 1塊

那麼我們有3個+ 1 blockreadings

是不是？

我不知道該怎麼做了B）..

而且我真的不知道該怎麼回答問題2。請幫我

Answer 1

只是一些筆記。你的1A最好的情況看起來幾乎是正確的（有點，但補充：底部），但我認爲你的塊大小計算是錯誤的。只有（的值）B和對所需磁盤塊的指針/引用應存儲在b +索引樹中。 A和C都不應該在b +樹中。

而你最糟糕的情況確實是錯誤的。沒有要求B是唯一的，並且在談論最壞情況時不需要做概率。

想象一下，如果在所有元組中B = 10，會發生什麼情況。那麼你將不得不閱讀它們才能找到A = 100的值。 （請記住，你被要求的最好/最差情況不是平均）。

這個最糟糕的例子也是你解決問題1B的提示。如果具有相同B值的許多值並且它們不能位於幾個塊中，則索引可能很有用。 （你可以做確切的數學）。

2A似乎並不那麼困難。如果我們沒有索引，那麼你需要在最好的情況下讀取1個塊，在最壞的情況下讀取所有的塊。 （這個假設A是唯一的，這就是A是一個關鍵的手段吧？）

但是我對這個最後一個問題有點困惑。如果A和B是兩個不同的（foreign ???）鍵，那麼對它們組合索引似乎都是錯誤的。

PS：這是一個幾年前，我沒有這所大學，所以我可能是錯的，但我希望我至少給你一些思考：}

補充：------ -----------

我關於計算單個節點中可以有多少條目的說明看起來確實是關閉的。試試這個：（仍然從內存中，所以很抱歉有任何錯誤）。

b +樹中的條目包含B（最小/最大）的2個值和包含最小值和最大值之間的值的塊的磁盤塊參考。因此每個條目都是12個字節（假設4個字節塊引用），因此可以在每個塊中存儲2048/12 = 170個條目。