Lucene 源码分析之倒排索引（二）

本文以及后面几篇文章将讲解如何定位 Lucene 中的倒排索引。内容很多，唯有静下心才能跟着思路遨游。

我们可以思考一下，哪个步骤与倒排索引有关，很容易想到检索文档一定是要查询倒排列表的，那么就从此处入手。检索文档通过调用 IndexSearcher.search(Query query, int n) 方法返回匹配的文档。

public class IndexSearcher {
    public TopDocs search(Query query, int n) throws IOException {
        return searchAfter(null, query, n);
    }

    public TopDocs searchAfter(ScoreDoc after, Query query, int numHits) throws IOException {
        // ...
        return search(query, manager);
    }

    public <C extends Collector, T> T search(Query query, CollectorManager<C, T> collectorManager) throws IOException {
        if (executor == null) {
            final C collector = collectorManager.newCollector();
            search(query, collector);
            return collectorManager.reduce(Collections.singletonList(collector));
        }
        // ...
    }
}

上面是 search 的调用链，最终调用的核心方法是 reduce(...)，也就是说 reduce(...) 会返回匹配的文档。

下文通过聚焦 reduce(...) 方法定位 Lucene 中的倒排索引。

reduce(...) 方法的形参是 Collections.singletonList(collector)，collector 是由 CollectorManager.newCollector() 方法创建的，而 CollectorManager 创建于上面代码中第二个方法 searchAfter 方法中的匿名内部类，代码如下。

public class IndexSearcher {
    public TopDocs searchAfter(ScoreDoc after, Query query, int numHits) throws IOException {
        // ...
        final CollectorManager<TopScoreDocCollector, TopDocs> manager = new CollectorManager<TopScoreDocCollector, TopDocs>() {
            @Override
            public TopScoreDocCollector newCollector() throws IOException {
                return TopScoreDocCollector.create(cappedNumHits, after);
            }
            // ...
        };
        // ...
    }
}

public abstract class TopScoreDocCollector extends TopDocsCollector<ScoreDoc> {
    public static TopScoreDocCollector create(int numHits, ScoreDoc after) {
        return new SimpleTopScoreDocCollector(numHits);
    }
}

也就是说 reduce 的形参是一个集合，该集合包含一个 SimpleTopScoreDocCollector 对象。

回到 reduce 的内部实现，调用方也是 searchAfter 方法中的匿名内部类 CollectorManager，代码如下。

public class IndexSearcher {
    public TopDocs searchAfter(ScoreDoc after, Query query, int numHits) throws IOException {
        // ...
        final CollectorManager<TopScoreDocCollector, TopDocs> manager = new CollectorManager<TopScoreDocCollector, TopDocs>() {
            // ...
            @Override
            public TopDocs reduce(Collection<TopScoreDocCollector> collectors) throws IOException {
                final TopDocs[] topDocs = new TopDocs[collectors.size()];
                int i = 0;
                for (TopScoreDocCollector collector : collectors) {
                    topDocs[i++] = collector.topDocs();
                }
                return TopDocs.merge(0, cappedNumHits, topDocs, true);
            }

        };
        // ...
    }
}

由于 reduce(...) 方法的形参仅有一个元素，reduce(...) 方法退化成执行 SimpleTopScoreDocCollector.topDocs()，其结果就是匹配的文档。

public abstract class TopScoreDocCollector extends TopDocsCollector<ScoreDoc> {
    private static class SimpleTopScoreDocCollector extends TopScoreDocCollector {
        // ...
    }
}

public abstract class TopDocsCollector<T extends ScoreDoc> implements Collector {
    public TopDocs topDocs() {
        return topDocs(0, topDocsSize());
    }

    public TopDocs topDocs(int start, int howMany) {
        // ...
        ScoreDoc[] results = new ScoreDoc[howMany];
        // ...
        populateResults(results, howMany);
        return newTopDocs(results, start);
    }

    protected void populateResults(ScoreDoc[] results, int howMany) {
        for (int i = howMany - 1; i >= 0; i--) { 
            results[i] = pq.pop();
        }
    }
}

SimpleTopScoreDocCollector 继承自 TopScoreDocCollector 继承自 TopDocsCollector，实际执行 TopDocsCollector.topDocs()。

时刻记住 reduce() 返回匹配的文档，也就是说 TopDocsCollector. topDocs() 返回匹配的文档。 results 作为 NewTopDocs 的成员变量一定包含了匹配的文档，results 又来自于 pq.pop()，那么 pq 一定包含了匹配的文档。

下面通过聚焦 SimpleTopScoreDocCollector 对象的 pq 定位倒排索引。

回顾 CollectorManager.reduce(...) 所在的 search(...) 方法，在初始化 SimpleTopScoreDocCollector 和 reduce(...) 之间唯一的方法就是另一个 search(…) 方法，一定是在这个方法中赋值了 pq，代码如下。

public class IndexSearcher {
    public void search(Query query, Collector results) throws IOException {
        search(leafContexts, createNormalizedWeight(query, results.needsScores()), results);
    }

    protected void search(List<LeafReaderContext> leaves, Weight weight, Collector collector) throws IOException {
        for (LeafReaderContext ctx : leaves) { // search each subreader
            final LeafCollector leafCollector = collector.getLeafCollector(ctx);
            BulkScorer scorer = weight.bulkScorer(ctx);
            scorer.score(leafCollector, ctx.reader().getLiveDocs());
        }
    }
}

一共就三个方法，究竟是在哪个方法中赋值了 pq 呢？一个个分析。

第一个方法，collector.getLeafCollector(ctx) 实际调用的就是 SimpleTopScoreDocCollector.getLeafCollector(ctx)。

public abstract class TopScoreDocCollector extends TopDocsCollector<ScoreDoc> {
    private static class SimpleTopScoreDocCollector extends TopScoreDocCollector {
        @Override
        public LeafCollector getLeafCollector(LeafReaderContext context) throws IOException {
            final int docBase = context.docBase;
            return new ScorerLeafCollector() {
                @Override
                public void collect(int doc) throws IOException {
                    float score = scorer.score();
                    totalHits++;               
                    pqTop.doc = doc + docBase;
                    pqTop.score = score;
                    pqTop = pq.updateTop();
                }
            };
        }
    }
}

可以看到 getLeafCollector(...) 方法返回的 ScorerLeafCollector 类提供了 collect(doc) 方法对 pq 进行操作。也就是说找到调用 collect(doc) 方法的地方也就找到了倒排索引。

下面通过聚焦找到调用 collect() 方法的来源来定位倒排索引。

第二个方法，weight.bulkScorer(ctx) 创建 BulkScorer，而 weight 由 createNormalizedWeight(…) 创建。

public class IndexSearcher {
    public Weight createNormalizedWeight(Query query, boolean needsScores) throws IOException {
        // ...
        return createWeight(query, needsScores, 1f);
    }

    public Weight createWeight(Query query, boolean needsScores, float boost) throws IOException {
        // ...
        Weight weight = query.createWeight(this, needsScores, boost);
        // ...
        return weight;
    }
}

假设 query 是最简单的 TermQuery，createWeight(…) 代码如下。

public class TermQuery extends Query {
    @Override
    public Weight createWeight(IndexSearcher searcher, boolean needsScores, float boost) throws IOException {
        // ...
        return new TermWeight(searcher, needsScores, boost, termState);
    }
}

最终返回的是 TermWeight 对象，那么 weight.bulkScorer(ctx) 实现类代码如下。

public abstract class Weight implements SegmentCacheable {
    public BulkScorer bulkScorer(LeafReaderContext context) throws IOException {        
        // ...
        return new DefaultBulkScorer(scorer);
    }
}

最终返回的是一个 DefaultBulkScorer 对象。

第三个方法，scorer.score(…)，实际调用类是 DefaultBulkScorer，代码如下。

public abstract class Weight implements SegmentCacheable {
    protected static class DefaultBulkScorer extends BulkScorer {
        // ...
    }
}

public abstract class BulkScorer {
    public void score(LeafCollector collector, Bits acceptDocs) throws IOException {
        final int next = score(collector, acceptDocs, 0, DocIdSetIterator.NO_MORE_DOCS);
    }
}

BulkScorer.score(…) 内部调用的还是 DefaultBulkScorer 中重构的 score(…) 方法，代码如下。

public abstract class Weight implements SegmentCacheable {
    protected static class DefaultBulkScorer extends BulkScorer {
        @Override
        public int score(LeafCollector collector, Bits acceptDocs, int min, int max) throws IOException {
            collector.setScorer(scorer);
            if (scorer.docID() == -1 && min == 0 && max == DocIdSetIterator.NO_MORE_DOCS) {
                scoreAll(collector, iterator, twoPhase, acceptDocs);
                return DocIdSetIterator.NO_MORE_DOCS;
            }
        }

        static void scoreAll(LeafCollector collector, DocIdSetIterator iterator, TwoPhaseIterator twoPhase, Bits acceptDocs) throws IOException {
            if (twoPhase == null) {
                for (int doc = iterator.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = iterator.nextDoc()) {
                    if (acceptDocs == null || acceptDocs.get(doc)) {
                        collector.collect(doc);
                    }
                }
            }
        }
    }
}

看到了什么！找到了调用 collect(…) 方法的代码。

Android进阶之旅-(NDK实战篇之OpenCV）

Android进阶之旅-(Framework源码分析)

热门文章