title: analyzing height of b-tree
body: <p>I am reading about B-trees at following location </p>
  
  <p><a href="http://www.brpreiss.com/books/opus4/" rel="nofollow">http://www.brpreiss.com/books/opus4/</a></p>
  
  <p>Here author is analyzing B-tree height.</p>
  
  <p>The minimum number of keys in a B-tree of order M >= 2 and height  is >= 0 is Nk = 2 * ceiling (M/2) ^ h -1</p>
  
  <p>:Proof Clearly, a B-tree of height zero contains at least one node. Consider a B-tree order M and height h>0. By Definition each internal node (except the root) has at least ceiling (M/2) subtrees. This implies the minimum number of keys contained in an internal node is celing (M/2)-1. The minimum number of keys a level zero is 1; at level one, 2(celing(M/2)-1) ;, at level two 2(ceiling (m/2)(Ceiling(M/2)-1)</p>
  
  <p>My question is how author concluded that level 1 minimum number of kesy are 2(celing(M/2)-1) and for level 2?</p>
  
  <p>for example if M is 2 then minimum number of keys at level1 is coming as 0, is that right?</p>