title: logarithmic time count(*) range query on any DBMS
body: <p>Suppose there is a table T, with column C indexed by a B-tree, and a given constant k. Assume the result of the following query would be n:</p>
  
  <pre><code>select count(*) from T where C &gt; k;
  </code></pre>
  
  <p>I tried such a query in MySQL(InnoDB) ,with column C indexed by B-tree, and realized the bigger the value of n, the slower the query. On a large table (GBs), I even have to wait for minutes. So, I speculate the time complexity is linear with respect to n. But I know if one stores aggregate information on B-Tree internal nodes that can be done in logarithmic time with respect to the size of table.</p>
  
  <p>Can anybody please suggest any DBMS with the logarithmic solution implemented, or any trick to reduce the query time in MySQL?</p>