title: Space complexity of a B-tree index in a database
body: <p>A traditional B-tree implementation has O(n) space complexity [<a href="http://en.wikipedia.org/wiki/B-tree" rel="nofollow">1</a>].</p>
  
  <p>So assume in a database (regardless of implementation, just consider general case), I have a table of 10GB data, currently the index size is 1GB, so can I assume that if the database grown to 100GB, my index size will be 10GB?</p>