Given that:

B = n/R blocks in the file
2d index records per block (blocking factor): 2d > R
an extra block access from the index to the datafile

I am not able to wrap my head around as why the lookup would incur an cost[number of block accesses] of
less than or equal to

2 + log(base to d) (n/2)
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Apr 20 '16 at 0:09
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Apr 20 '16 at 0:09

Nvm, figured it out. One access would be required to find the root of B-tree. And then Logd(n/2) access to find the correct leaf containing the right key. And then another another block access to reach the requested data for the given key.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.