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.

Nick
NEW: Monitor These Apps!
elasticsearch, apache solr, apache hbase, hadoop, redis, casssandra, amazon cloudwatch, mysql, memcached, apache kafka, apache zookeeper, apache storm, ubuntu, centOS, red hat, debian, puppet labs, java, senseiDB