Lucene學習筆記之-核心數據結構PriorityQueue的實現原理

Luene的核心應用場景是全文檢索。簡單來說，就是通過用戶輸入的關鍵詞來匹配相關文檔，然后根據匹配程度返回TopN的查詢結果給用戶。 這里需要解決的一個核心問題就是如何快速返回TopN的結果，這本質上是一個排序的問題。說起排序，我們有很多選擇，冒泡，快排，歸并...。 這些排序算法在數據量小的時候，不是問題。一旦數據量過大，就成為問題了。

例如對1000萬的數組排序:

        Integer[] a = new Integer[10000000];

        for(int i=0;i<10000000;i++){
            a[i] = (int) (Math.random()*10000000);
        }
        long start = System.currentTimeMillis();
        Arrays.sort(a);
        System.out.println((System.currentTimeMillis() - start) +" 毫秒");

在我的電腦耗時需要5秒左右， 這個等待時間對于用戶體驗來說，就不那么feeling good了。

這時候，該考慮優化了。優化基本上是一個做減法的過程。再回到我們的核心需求: 基于搜索關鍵詞返回TopN的結果。 也就是說，我們只需要TopN的結果有序就可以了。 基于上述需求，我們引入一個新的數據結構: 堆(Heap)。

堆是一種特殊的二叉樹。所謂二叉樹就是每個節點最多有兩個子節點: 最多生二胎，超生不被允許的。

對于二叉樹這種樹形結構，最核心的關系就是父子節點關系。 定義不同的節點關系，我們就能得到豐富多彩的數據結構，以應對不同場景的業務問題。比如:

規定“子節點不能大于父節點”， 我們可以得出根節點是最大的節點， 得到大頂堆。

規定“子節點不能小于父節點”， 我們可以得出根節點是最小的節點， 得到小頂堆。

規定“根節點大于左子樹，小于右子樹；子樹亦是如此”， 我們得到二叉搜索樹；為了使二叉搜索樹的左右盡量平衡，我們又得到了“紅黑樹”，“AVL樹”，Treap等不同策略的平衡樹。

這些概念性的東西，能理解就OK.

理解了堆的來龍去脈， 我們可能會有點困惑，它并沒有直接維護一個有序的結構。 是的，它沒有直接維護有序的結構，它是通過刪除數據實現排序功能的。理解這一點特別重要。 以大頂堆為例: 由于堆頂是最大的元素，所以我們能確信，對于一個堆: 我們只要不斷地刪除堆頂的數據，直至空堆，就能得到一個有序的結果。這就是堆排序的思想。

那么如何利用堆實現TopN的有序輸出呢？ 以搜索的打分作為排序項，我們希望輸出得分最高的N個結果。 我們先遍歷N個結果，得到有N個元素的小頂堆。由于堆頂的元素最小， 遍歷剩下的打分結果，只需要跟堆的根節點對比即可。如果打分結果小于堆的根節點，棄之；如果打分結果大于堆的根節點，刪除根節點；然后使用該打分結果更新到堆中。 這樣最后這個堆就維護了我們想要的TopN。

例如對1000萬的數據，我們給出最大的前100個數，代碼如下:

Integer[] a = new Integer[10000000];

        for(int i=0;i<10000000;i++){
            a[i] = (int) (Math.random()*10000000);
        }
        long start = System.currentTimeMillis();

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(100) {
            @Override
            protected boolean lessThan(Integer t1, Integer t2) {
                return t1 < t2;
            }
        };

        for(int i=0;i<10000000;i++){
            pq.insertWithOverflow(a[i]);
        }
        Integer[] b = new Integer[100];
        for(int i=99;i>=0;i--){
            b[i] = pq.pop();
        }
        System.out.println((System.currentTimeMillis() - start) +" 毫秒");
        System.out.println(Arrays.asList(b));

這個耗時只需要50多毫秒。 這個性能差距幾乎是100倍。可見堆這種數據結構在TopN這個場景下是多么適合。

其實JDK有自己基于堆實現的優先隊列PriorityQueue, 為啥Lucene要再造一遍輪子呢？

JDK默認的PriorityQueue是可以自動擴展的，Lucene需要定長的。
JDK默認的PriorityQueue將數據結構封裝得比較緊密，而Lucene需要一定的靈活性，比如調整堆頂。

小頂堆是一種二叉樹，所以其邏輯結構大致如下:

    1
 3    2
5 8  7 6

如果觀察，可以發現這個一個規律，就是第一層只有1個元素;第二層最多有2個元素; 第三層最多有4個元素， 即第N層有2^(n-1)個元素。 這個規律后面有用。

那么怎么編碼實現一個堆呢？ 最簡單的實現方式是基于數組，以Lucene的實現為例，學習一下:

public abstract class PriorityQueue<T> {
    private int size;
    private final int maxSize;
    private final T[] heap;

定義了一個數組。 只需要做如下的規定，那么就能滿足對的邏輯結構:

1. heap[0]位空置不用。
2. heap[1]為根節點。
3. heap[2~3]為第二層，heap[4~7] 為第三層 ... heap[2^n ~ 2^(n+1)-1]為第n+1層

這樣，元素在數組的哪個位置，我們就能知道它屬于哪一層了。

接下來要解決的問題是:

1. 如何插入一個元素到堆中？

假設前面有N個元素了， 那么代碼很簡單

    public final T add(T element) {
        ++this.size;
        this.heap[this.size] = element;
        this.upHeap(this.size);
        return this.heap[1];
    }

兩步走： s1 將元素添加到尾巴上。 s2: 由于這個元素有可能比其父節點小，所以遞歸地跟其父節點比較，換位置即可，這里有點冒泡的感覺。即想象把乒乓球按入水中，松手后就會上浮。

2. 如何從堆中刪除一個元素？

   public final T pop() {
        if (this.size > 0) {
            T result = this.heap[1];
            this.heap[1] = this.heap[this.size];
            this.heap[this.size] = null;
            --this.size;
            this.downHeap(1);
            return result;
        } else {
            return null;
        }
    }

兩步走: s1: 用數組尾巴上的元素覆蓋跟節點元素。 s2: 由于這個元素是否能勝任根節點這個位置還不確定，因此需要跟兩個子節點比較，調整位置。這里有絲下沉的感覺。即想象把鐵球丟入水中，自己就沉了下去。

這里，堆的插入和刪除操作還是思路還是比較輕奇的，值得好好揣摩一番。

在Lucene中，PriorityQueue有那些應用場景呢？

1. HitQueue， 搜索打分的核心。
2. FieldValueHitQueue， 按字段排序的核心。
   ....

總之，該數據結構在Lucene中有30～40個子類，應用十分廣泛。了解其實現機制，對于了解其他的功能大有裨益。