Are you fetching all of the results for your search? If so, you're
actually measuring the time to pull n stored documents out of the index,
not to search over an index of n documents. Which would of course be
linear, most of your cost there will be the i/o to actually pull the
document from disk,
I had a similar problem with threading, the problem turned out to be that in
the back end of the FSDirectory class I believe it was, there was a
synchronized block on the actual RandomAccessFile resource when reading a
block of data from it... high-concurrency situations caused threads to stack
up
