上接《 索引創(chuàng)建(3)：DocumentWriter 處理流程二 》

?

1.3.3 第三車間 —— TermsHashPerField & FreqProxTermsWriterPerField

?

TermsHashPerField和FreqProxTermsWriterPerField負(fù)責(zé)將token信息(字符串內(nèi)容termTest，所在文檔編號docID，所在文檔中的位置position，所在文檔中的詞頻frequence)添加到索引的Hash表結(jié)構(gòu)(postingsHash)中。事實上，這些信息并不是直接存放在Hash表中的，而是存放在三個很重要的數(shù)據(jù)緩存池中 (CharBlockPool、IntBlockPool、ByteBlockPool) 。而postingsHash中存放的只是數(shù)據(jù)在三個數(shù)據(jù)池中的地址偏移。

?

★ TermsHashPerField

?

這里首先簡單介紹一下這三個數(shù)據(jù)池， 想要深刻了解這三個數(shù)據(jù)池， 可見《 索引數(shù)據(jù)池及內(nèi)存數(shù)據(jù)細(xì)節(jié) 》。

1) CharBlockPool: 存儲token的字面信息

2) ByteBlockPool: 存儲token所在文檔編號，位置和詞頻信息

3) IntBlockPool: 存儲對應(yīng)的ByteBlockPool中slice的位置

TermsHashPerField類的主要職責(zé)就是建立和維護(hù)一張postingsHash的倒排索引表。這張表是一張以token字符串作為關(guān)鍵字的Hash表。其結(jié)構(gòu)如下：

    final class TermsHashPerField extends InvertedDocConsumerPerField {

    private int postingsHashSize = 4;
    //倒排索引表的Hash數(shù)組結(jié)構(gòu)，初始大小為4
    private RawPostingList[] postingsHash = new RawPostingList[postingsHashSize];
}
  

其中postingHash[]的每個元素都是RawPostingList類型的。該類在內(nèi)存中表示一個由token唯一標(biāo)示的posting list(倒排索引結(jié)構(gòu)：token-> posting list)。

    //該類在內(nèi)存中表示一個由token唯一標(biāo)示的posting list(倒排索引結(jié)構(gòu): token -> posting list)。
abstract class RawPostingList {
     int textStart;   //存儲token信息在CharBlockPool中的初始位置 
     int intStart;     //存儲token信息在IntBlockPool中的初始位置
   ? int byteStart;  //存儲token信息在ByteBlockPool中的初始位置
}
  

實際上postingHash[]的每個元素的實際類型是PostingList。這個類型包含的數(shù)據(jù)域如下：

    static final class PostingList extends RawPostingList {
    int docFreq;  //此詞在當(dāng)前文檔中出現(xiàn)的次數(shù)
    int lastDocID;  // 上次處理完的包含此詞的文檔號。
    int lastDocCode;  // 文檔號和詞頻按照或然跟隨原則形成的編碼
    int lastPosition;  // 上次處理完的此詞的位置
}
  

?

?

TermsHashPerField.add()方法是創(chuàng)建待排索引的核心方法，我們分功能段來解析它的源代碼：

    // 將token加入到倒排索引的Hash鏈表結(jié)構(gòu)中：token -> posting list
@Override
void add() throws IOException {....}
  

?

1、首先，計算token的hashcode值。 很顯然，下面的代碼表明處理token中的字符采用的是UTF-16編碼方式(Java對字符串都是Unicode編碼的)。想要了解UTF-16編碼方式，可參見《 解析Unicode編碼和Java char 》。另外，token的hashcode計算公式是code=(code*31)+ch，其中ch是token從末尾開始向前遍歷的字符。

    //得到當(dāng)前token的內(nèi)容
final char[] tokenText = termAtt.termBuffer();
//得到當(dāng)前token的長度
final int tokenTextLen = termAtt.termLength();

int downto = tokenTextLen;
int code = 0;
//計算token的hashcode(其中每個字符按照的UTF-16編碼方式進(jìn)行編碼)
while (downto > 0) {
    //從后往前取出token中的每一個字符
    char ch = tokenText[--downto];
    //判斷ch是不是Unicode編碼中的替代區(qū)域(surrogate area),這個區(qū)域不表示任何字符
    if (ch >= UnicodeUtil.UNI_SUR_LOW_START && ch <= UnicodeUtil.UNI_SUR_LOW_END) {
           if (0 == downto) {
               ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
          } else {
              //取出連續(xù)兩個字符進(jìn)行hashcode計算(UTF-16編碼方式)
               final char ch2 = tokenText[downto-1];
               if (ch2 >= UnicodeUtil.UNI_SUR_HIGH_START && ch2 <= UnicodeUtil.UNI_SUR_HIGH_END) {
                   code = ((code*31) + ch)*31+ch2;
                   downto--;
                   continue;
               } else {
                   ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
               }            
          }
      } else if (ch >= UnicodeUtil.UNI_SUR_HIGH_START && (ch <= UnicodeUtil.UNI_SUR_HIGH_END ||
                                                          ch == 0xffff)) {
        ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
      }
      //如果ch是正常字符，則開始計算token的hashcode
      code = (code*31) + ch;
}//end while
  

?

2、 其次，根據(jù)token的hashcode定位到postingHash[]上的位置。 我們通過code & postingHashMask來找到當(dāng)前token在postingHash[]上的位置(其中postingsHashMask = postingsHashSize-1)。當(dāng)產(chǎn)生Hash沖突的時候，其解決辦法就是不斷計算新的位置直到不產(chǎn)生沖突為止。

?

這里順便提一下：code & postingHashMask 和code % postingHashMask是完全等價的，而且位運算效率更高，Lucene經(jīng)常使用位運算。

    //計算當(dāng)前token將要插入在Hash表中的位置，code & postingsHashMask等價于code % postingHashMask
//postingsHashMask=postingsHashSize-1
int hashPos = code & postingsHashMask; 
//取出原h(huán)ash表中hashPos位置上的數(shù)據(jù)
p = postingsHash[hashPos];
//如果原Hash表中的該位置上有數(shù)據(jù)并且兩個token的字符串內(nèi)容不等，則產(chǎn)生Hash沖突
if (p != null && !postingEquals(tokenText, tokenTextLen)) {
    // 沖突解決方法：不斷計算新的hashcode，直到避開沖突位置
    final int inc = ((code>>8)+code)|1;
    do {
        code += inc;
        hashPos = code & postingsHashMask;
        p = postingsHash[hashPos];
     } while (p != null && !postingEquals(tokenText, tokenTextLen));
}
  

?

3、最后，將token的各種信息寫入數(shù)據(jù)池，并在PostingList中存儲數(shù)據(jù)池的地址偏移。 整個 過程有兩種可能：

?

(1) 如果當(dāng)前token在前面從未遇到過，也就是已經(jīng)加入索引結(jié)構(gòu)的所有詞都沒有這個詞語。那么首先需要在postingHash中開辟一個新的PostingList準(zhǔn)備存放當(dāng)前token所對應(yīng)信息(code line :18，33)。接著在CharBlackPool中創(chuàng)建一個新的區(qū)域來存儲當(dāng)前token的字符串信息(line: 27)，并且將地址偏移記錄在新創(chuàng)建的PostingList.textStart中(line: 25)。然后就是在ByteBlockPool中開辟兩個slice (line:57，58)。并且在IntBlockPool中開辟兩個空間存儲ByteBlockPool中的新開辟的slice地址偏移(line:57，60)。最后調(diào)用 FreqProxTermsWriterPerField.newTerm() 將token的docID+freq和position信息存儲進(jìn)去(line: 67)。

?

(2) 如果當(dāng)前token在前面已經(jīng)遇到過了，此時就不需要在三大數(shù)據(jù)池中分配新的空間存放了。直接調(diào)用 FreqProxTermsWriterPerField.addTerm() 將信息存儲進(jìn)去(line:72)。

    //說明當(dāng)前token以前的文本中從未出現(xiàn)過
if (p == null) {
    final int textLen1 = 1+tokenTextLen;   
    //當(dāng)CharBlockPool當(dāng)前的buffer空間不足時，則重新分配一個新的buffer
    if (textLen1 + charPool.charUpto > DocumentsWriter.CHAR_BLOCK_SIZE) {
       if (textLen1 > DocumentsWriter.CHAR_BLOCK_SIZE) {
            if (docState.maxTermPrefix == null)
               docState.maxTermPrefix = new String(tokenText, 0, 30);
       consumer.skippingLongTerm();
       return;
       }  
       charPool.nextBuffer();
    }
      
    if (0 == perThread.freePostingsCount)
        perThread.morePostings();
    //從空閑的posting中分配新的posting
    p = perThread.freePostings[--perThread.freePostingsCount];
    assert p != null;

    //將當(dāng)前token的內(nèi)容寫入CharBlockPool中,此時text和CharBlockPool中的當(dāng)前buffer都指向同一塊內(nèi)存區(qū)域
    final char[] text = charPool.buffer;
    final int textUpto = charPool.charUpto;
    //PostingList類中的textStart保存的是當(dāng)前token首字母在CharBlockPool中的位置
    p.textStart = textUpto + charPool.charOffset;
    charPool.charUpto += textLen1;
    System.arraycopy(tokenText, 0, text, textUpto, tokenTextLen);
    //每個詞當(dāng)中存放一個分隔符'#66535'(66535號字符,我們用“#66535”表示)
    text[textUpto+tokenTextLen] = 0xffff;
          
    assert postingsHash[hashPos] == null;
    //將postingHash[hashPos]指向剛開辟的空閑RawPostList鏈表
    postingsHash[hashPos] = p;
    //記錄鏈表數(shù)量
    numPostings++;

    //如果postingsHash的加載因子達(dá)到了50%，則擴(kuò)大2倍的postingsHash容量
    if (numPostings == postingsHashHalfSize)
        rehashPostings(2*postingsHashSize);

    //當(dāng)IntBlockPool中buffer容量不足時，分配一個新buffer
    if (numPostingInt + intPool.intUpto > DocumentsWriter.INT_BLOCK_SIZE)
        intPool.nextBuffer();
    //當(dāng)ByteBlockPool中buffer容量不足時，分配一個新buffer
    if (DocumentsWriter.BYTE_BLOCK_SIZE - bytePool.byteUpto < numPostingInt*ByteBlockPool.FIRST_LEVEL_SIZE)
        bytePool.nextBuffer();

    intUptos = intPool.buffer;
    intUptoStart = intPool.intUpto;
    //streamCount=2在ByteBlockPool對一個token同時開辟兩個大小一樣的slice，一個存放docID+frequence，另一個存放positive.
    //并且在IntBlockPool中也同時開辟兩個空間，用于分別存放一個token對應(yīng)在ByteBlockPool中兩個slice的地址偏移
    intPool.intUpto += streamCount;
      
    //PostingList類中的intStart保存的是當(dāng)前token在IntBlockPool中的兩個存儲空間的第一個地址
    p.intStart = intUptoStart + intPool.intOffset;
    //每一次記錄一個token，都需要在ByteBlckPool中開辟兩個塊來記錄: docID+freq(文檔ID+詞頻) 和 prox(位置)
    for(int i=0;i<streamCount;i++) {
        final int upto = bytePool.newSlice(ByteBlockPool.FIRST_LEVEL_SIZE);
       //IntBlockPool用來存儲ByteBlockPool每次開辟的塊的初始位置
       intUptos[intUptoStart+i] = upto + bytePool.byteOffset;
    }
    //PostingList類中的byteStart用于存儲當(dāng)前token使用ByteBlckPool開辟的空間的初始位置
    //也就是剛開辟的兩個塊中第一個塊的初始位置
    p.byteStart = intUptos[intUptoStart];
      
    //token原來沒有出現(xiàn)過的時候，F(xiàn)reqProxTermsWriterPerField調(diào)用newTerm()記錄docID,freq和position
    consumer.newTerm(p);

} else { //如果此Token之前曾經(jīng)出現(xiàn)過，F(xiàn)reqProxTermsWriterPerField調(diào)用addTerm()記錄docID,freq和position
      intUptos = intPool.buffers[p.intStart >> DocumentsWriter.INT_BLOCK_SHIFT];
      intUptoStart = p.intStart & DocumentsWriter.INT_BLOCK_MASK;
      consumer.addTerm(p);
}

  

???? 我們在《 全文檢索基本理論 》中講到的倒排索引結(jié)構(gòu)是 token -> posting list的形式，而文檔結(jié)合的所有token組成了一個Dictionary。 TermsHashPerField類的作用就是建立這樣一個倒排索引結(jié)構(gòu)——postingHash。其中 postingHash[](哈希數(shù)組)是以token的字面值作為關(guān)鍵字的，相當(dāng)于Dictionary。而 postingHash的每一個元素都指向了PostingList對象，這個對象就是用來存儲指定token所對應(yīng)的posting list信息(包括docID，freq，position)。實際上，真正的信息是存儲在三大數(shù)據(jù)池中的，但 PostingList對象只存儲三大數(shù)據(jù)池中的地址偏移。我們通過上面的代碼可以發(fā)現(xiàn)： TermsHashPerField已經(jīng)把token的字面值存儲在CharBlockPool中了，并且在ByteBlockPool中分配好的存儲空間，并將地址偏移記錄到了IntBlockPool中了。接下來要做的就是把 token所對應(yīng)的docID，freq，position的信息通過 FreqProxTermsWriterPerField 的方法寫入ByteBlockPool。

?

?

★ FreqProxTermsWriterPerField ?

?

(1)當(dāng)出現(xiàn)一個索引結(jié)構(gòu)中沒有的token時，我們需要調(diào)用 newTerm()方法將token所對應(yīng)的 docID，freq，position信息存儲到ByteBlockPool中。

    final void newTerm(RawPostingList p0) {
    assert docState.testPoint("FreqProxTermsWriterPerField.newTerm start");
    FreqProxTermsWriter.PostingList p = (FreqProxTermsWriter.PostingList) p0;
    //當(dāng)一個新的term出現(xiàn)的時候，包含此Term的就只有本篇文檔，記錄其ID 
    p.lastDocID = docState.docID;
    if (omitTermFreqAndPositions) {
        p.lastDocCode = docState.docID;
    } else {
        //docCode是文檔ID左移一位，為什么左移，這就需要Lucene的索引文件結(jié)構(gòu)來解釋了。
        p.lastDocCode = docState.docID << 1;
        p.docFreq = 1;
       //寫入position信息到bytePool中，此時freq信息還不能寫入，因為當(dāng)前的文檔還沒有處理完，尚不知道此文檔包含此token的總數(shù)。 
       writeProx(p, fieldState.position);
    }
}
  

?

(2) 當(dāng)出現(xiàn)的token在索引結(jié)構(gòu)中已經(jīng)存在，我們需要調(diào)用 addTerm()方法將token所對應(yīng)的 docID，freq，position信息存儲到 ByteBlockPool中。

    final void addTerm(RawPostingList p0) {
    assert docState.testPoint("FreqProxTermsWriterPerField.addTerm start");
    //取出postingHash已經(jīng)存在的PostingList
    FreqProxTermsWriter.PostingList p = (FreqProxTermsWriter.PostingList) p0;

    assert omitTermFreqAndPositions || p.docFreq > 0;

    if (omitTermFreqAndPositions) {
      //p.lastDocID記錄了上一次token寫入索引結(jié)構(gòu)的docID
      //docState.docID記錄的是token將要寫入索引結(jié)構(gòu)的當(dāng)前docID
      if (docState.docID != p.lastDocID) {
        assert docState.docID > p.lastDocID;
        termsHashPerField.writeVInt(0, p.lastDocCode);
        p.lastDocCode = docState.docID - p.lastDocID;
        p.lastDocID = docState.docID;
      }
    } else {
      if (docState.docID != p.lastDocID) {
        assert docState.docID > p.lastDocID;
        //如果當(dāng)前的docID與上一次相同的token寫入的docID不同
        //則表明上一篇文本中該token已經(jīng)處理完畢，則將freq信息ByteBlockPool中
        if (1 == p.docFreq)
          termsHashPerField.writeVInt(0, p.lastDocCode|1);
        else {
          termsHashPerField.writeVInt(0, p.lastDocCode);
          termsHashPerField.writeVInt(0, p.docFreq);
        }
        p.docFreq = 1;//對于新的文檔，freq還是為1. 
        p.lastDocCode = (docState.docID - p.lastDocID) << 1;//文檔號存儲差值 
        p.lastDocID = docState.docID;
        writeProx(p, fieldState.position);
      } else {
    	//當(dāng)文檔ID不變的時候，說明此文檔中這個詞又出現(xiàn)了一次，從而freq加1，寫入再次出現(xiàn)的位置信息，用差值存儲。這里不寫入freq，因為該文檔還沒有結(jié)束
        p.docFreq++;
        //將position信息寫入ByteBlockPool中
        writeProx(p, fieldState.position-p.lastPosition);
      }
    }
}
  

?

上面newTerm()和addTerm()方法都需要調(diào)用writeProx()方法將position信息寫入ByteBlockPool中

    //將position信息寫入ByteBlockPool中
final void writeProx(FreqProxTermsWriter.PostingList p, int proxCode) {
    final Payload payload;
    //payloadAttribute是token的元數(shù)據(jù)信息
    if (payloadAttribute == null) {
      payload = null;
    } else {
      payload = payloadAttribute.getPayload();
    }
    
    //將position信息寫入ByteBlockPool中
    //其中writeVInt()第一個參數(shù)1表示將position寫入開辟在ByteBlockPool中兩個slice的第2個中
    //第一個slice存放docID+freq，第二個slice存放position
  ?if (payload != null && payload.length > 0) {
      termsHashPerField.writeVInt(1, (proxCode<<1)|1);
      termsHashPerField.writeVInt(1, payload.length);
      termsHashPerField.writeBytes(1, payload.data, payload.offset, payload.length);
      hasPayloads = true;      
    } else
      termsHashPerField.writeVInt(1, proxCode<<1);
    p.lastPosition = fieldState.position;
}
  

?

實際上，寫入ByteBlockPool中的數(shù)據(jù)到底是什么樣子的呢？還有在CharBlockPool中是如何存儲token的字面值的呢？IntBlockPool又是怎么樣記錄ByteBlockPool中的地址偏移的呢？這些問題我們將在《 索引數(shù)據(jù)池及其存儲細(xì)節(jié) 》詳細(xì)闡明.

?

?

★ 總結(jié)：

?

???? 我們以前面所舉的例子為例，將《 索引數(shù)據(jù)池及內(nèi)存數(shù)據(jù)細(xì)節(jié) 》中的content field的第一個token="lucene"(docID=0，position=1)創(chuàng)建索引結(jié)構(gòu)，其圖示如下：

【Lucene3.0 初窺】索引創(chuàng)建(4)：DocumentWriter 處理流程三