Chao Shi created HBASE-9969:
-------------------------------
Summary: Improve KeyValueHeap using loser tree
Key: HBASE-9969
URL: https://issues.apache.org/jira/browse/HBASE-9969
Project: HBase
Issue Type: Improvement
Reporter: Chao Shi
LoserTree is the better data structure than binary heap. It saves half of the
comparisons on each next(), though the time complexity is on O(logN).
Currently A scan or get will go through two KeyValueHeaps, one is merging KVs
read from multiple HFiles in a single store, the other is merging results from
multiple stores. This patch should improve the both cases whenever CPU is the
bottleneck (e.g. scan with filter over cached blocks, HBASE-9811).
All of the optimization work is done in KeyValueHeap and does not change its
public interfaces. The new code looks more cleaner and simpler to understand.
--
This message was sent by Atlassian JIRA
(v6.1#6144)
