[LUCENE-9045] Do not use TreeMap/TreeSet in BlockTree and PerFieldPostingsFormat

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 8.4
• Lucene Fields: New
• Assignee: Bruno Roustant
• Reporter: Bruno Roustant
• Created: 13/Nov/19 09:25
• Updated: 22/Sep/22 14:07
• Resolved: 02/Dec/19 15:44

Description

TreeMap/TreeSet is a heavy structure designed to dynamically sort keys. It's iterator is much less performant than a list iterator. We should not use it when we don't need the sorting capability once built.

And this is the case in BlockTreeTermsReader and PerFieldPostingsFormat. We need a Map and to sort keys at building time. But once built, we don't need to sort anymore, we can use a simple list for iteration efficiency.

Issue Links

• is a child of: LUCENE-8041 All Fields.terms(fld) impls should be O(1) not O(log(N))
• links to: GitHub Pull Request #1007