title: Does HBase uses a primary index?
body: <p>How does HBase performs a lookup and retrieves a record ?
  e.g., what is the equivalent in HBase for the RDBMS's B-Trees?</p>
  
  <p>[EDIT]</p>
  
  <p>I understand how HBase resolves the -ROOT-, and .META. tables to find out which region holds the data. But how is the local lookup performed?</p>
  
  <p>To better illustrated, here's an example:</p>
  
  <ol>
  <li>I am starting a search (get or scan) for record with key 77. </li>
  <li>HBase client figures that the key is contains in the 50-100 region,
  held by RegionServer X.</li>
  <li>HBase client contacts RegionServer X to get the data.</li>
  </ol>
  
  <p>How does RegionServer X finds out the location of record 77 ?</p>
  
  <p>Does the RegionServer uses some kind of lookup table (e.g. like the RDBMS's B-Trees ?) for the keys of a region ?
  Or does it need to read all contents of the StoreFiles, for records from 50 to 77 ?</p>