B +樹CPU搜索時間

Question

我只是想知道你將如何計算最壞情況下的時間非集羣和集羣B +樹？

例如，說我有1,000,000記錄時，（1行= 100個字節），磁盤頁面是4000個字節，一個關鍵是20個字節，一個頁面的訪問時間爲40ms。我將如何計算使用這些變量的非聚集和聚集b +樹更差的情況下？

我知道，來計算你用下面的B +樹的高度/水平（我認爲）：

logF(keys) 

其中F = praches分支機構的數量。

隨着高度，你可以用它來計算出最終的最壞情況下的時間，但我不知道該怎麼做。我已經試過周圍尋找，但我能罰款倍的平均情況或不太清楚的例子。

任何幫助表示讚賞！

Answer 1

我要說logF（鍵）其最壞的情況下尋找的頁面，但在這之後最壞的情況下將與所有的RID指向不同頁面的unclustured指數，至極的意思

logF（鍵） + N是索引節點中rid的數量。

所以最後這將是

H =樹至極的高度將會像3或4

H + N = 4 +（二十〇分之四千）= 204的I/O

讓他們說，他們在內存中，並希望看到CPU時間，那麼它將是

CPU = 204 * 0.04 = 8.16秒。在內存中移動頁面其相當多的時間althought 40毫秒，我認爲（磁盤讀取可能意義），但我認爲計算的罰款。