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毫秒，我认为（磁盘读取可能意义），但我认为计算的罚款。