On 23/02/2017 01:07, kasilak wrote:

No, it's the classic binary search algorithm that works on a sorted array:


It's implemented in LexIndex_Seek:


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.

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