# Lookup complexity in B-trees [Database]

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)

• 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. – Raphael Apr 20 '16 at 0:09
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Apr 20 '16 at 0:09