On 23/02/2017 01:07, kasilak wrote:
No, it's the classic binary search algorithm that works on a sorted array: https://en.wikipedia.org/wiki/Binary_search_algorithm
It's implemented in LexIndex_Seek: https://git1-us-west.apache.org/repos/asf?p=lucy.git;a=blob;f=core/Lucy/Index/LexIndex.c;h=0d7a0ea4f4d4f2d720df13be2919691d0977c8ab;hb=HEAD#l141
What do you mean by "fixed cost"?
No, IxSearcher_Hits always returns sorted documents. The search process can be
divided into three steps:
1. Find all N documents matching a query.
2. Find and sort the top M documents according to the SortSpec. Lucy
uses a priority queue implemented as a heap (HitQueue), so time
complexity is O(N * log(M)).
3. Retrieve the stored fields for each of the top M documents.
Steps 2 and 3 are obviously faster for smaller values of M.