HBase supports Bloom Filter to improve the overall throughput of the cluster. A HBase Bloom Filter is a space-efficient mechanism to test whether a StoreFile contains a specific row or row-col cell. Here are the details of Bloom Filter: http://en.wikipedia.org/wiki/Bloom_filter.
Without Bloom Filter, the only way to decide if a row key is contained in a StoreFile is to check the StoreFile's block index, which stores the start row key of each block in the StoreFile. It is very likely that the row key we are finding will drop in between two block start keys; if it does then HBase has to load the block and scan from the block's start key to figure out if that row key actually exists.
The problem here is that there will be a number of StoreFiles that exist before a major compaction aggregates them into a single one. Thus several StoreFiles may have some cells of the requested row key.
Think about the following example; it is an image showing...