Revision cb7a00227ff3565000af4859664c77224106dcb5 authored by Dhruba Borthakur on 05 November 2012, 07:47:06 UTC, committed by Dhruba Borthakur on 06 November 2012, 00:08:01 UTC
Summary:
The method Version::GetOverlappingInputs used a sequential search
to map a kay-range to a set of files. But the files are arranged
in ascending order of key, so a biary search is more effective.

This patch implements Version::GetOverlappingInputsBinarySearch
that finds one file that corresponds to the specified key range
and then iterates backwards and forwards to find all overlapping
files.

This patch is critical for making compactions efficient, especially
when there are thousands of files in a single level.

I measured that 1000 iterations of TEST_MaxNextLevelOverlappingBytes
takes 16000 microseconds without this patch. With this patch, the
same method takes about 4600 microseconds.

Test Plan: Almost all unit tests in db_test uses this method to lookup keys.

Reviewers: heyongqiang

Reviewed By: heyongqiang

CC: MarkCallaghan, emayanke, sheki

Differential Revision: https://reviews.facebook.net/D6465
1 parent 5273c81
History
File Mode Size
leveldb
leveldbjni
README -rw-r--r-- 873 bytes

README

back to top