上接《 索引創建(3)：DocumentWriter 處理流程二 》
?
1.3.3 第三車間 —— TermsHashPerField & FreqProxTermsWriterPerField
?
TermsHashPerField和FreqProxTermsWriterPerField負責將token信息(字符串內容termTest，所在文檔編號docID，所在文檔中的位置position，所在文檔中的詞頻frequence)添加到索引的Hash表結構(postingsHash)中。事實上，這些信息并不是直接存放在Hash表中的，而是存放在三個很重要的數據緩存池中 (CharBlockPool、IntBlockPool、ByteBlockPool) 。而postingsHash中存放的只是數據在三個數據池中的地址偏移。
?
★ TermsHashPerField
?
這里首先簡單介紹一下這三個數據池， 想要深刻了解這三個數據池， 可見《 索引數據池及內存數據細節 》。
1) CharBlockPool: 存儲token的字面信息
2) ByteBlockPool: 存儲token所在文檔編號，位置和詞頻信息
3) IntBlockPool: 存儲對應的ByteBlockPool中slice的位置
TermsHashPerField類的主要職責就是建立和維護一張postingsHash的倒排索引表。這張表是一張以token字符串作為關鍵字的Hash表。其結構如下：
final class TermsHashPerField extends InvertedDocConsumerPerField {
private int postingsHashSize = 4;
//倒排索引表的Hash數組結構，初始大小為4
private RawPostingList[] postingsHash = new RawPostingList[postingsHashSize];
}
其中postingHash[]的每個元素都是RawPostingList類型的。該類在內存中表示一個由token唯一標示的posting list(倒排索引結構：token-> posting list)。
//該類在內存中表示一個由token唯一標示的posting list(倒排索引結構: token -> posting list)。
abstract class RawPostingList {
int textStart; //存儲token信息在CharBlockPool中的初始位置
int intStart; //存儲token信息在IntBlockPool中的初始位置
? int byteStart; //存儲token信息在ByteBlockPool中的初始位置
}
實際上postingHash[]的每個元素的實際類型是PostingList。這個類型包含的數據域如下：
static final class PostingList extends RawPostingList {
int docFreq; //此詞在當前文檔中出現的次數
int lastDocID; // 上次處理完的包含此詞的文檔號。
int lastDocCode; // 文檔號和詞頻按照或然跟隨原則形成的編碼
int lastPosition; // 上次處理完的此詞的位置
}
?
?
TermsHashPerField.add()方法是創建待排索引的核心方法，我們分功能段來解析它的源代碼：
// 將token加入到倒排索引的Hash鏈表結構中：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從末尾開始向前遍歷的字符。
//得到當前token的內容
final char[] tokenText = termAtt.termBuffer();
//得到當前token的長度
final int tokenTextLen = termAtt.termLength();
int downto = tokenTextLen;
int code = 0;
//計算token的hashcode(其中每個字符按照的UTF-16編碼方式進行編碼)
while (downto > 0) {
//從后往前取出token中的每一個字符
char ch = tokenText[--downto];
//判斷ch是不是Unicode編碼中的替代區域(surrogate area),這個區域不表示任何字符
if (ch >= UnicodeUtil.UNI_SUR_LOW_START && ch <= UnicodeUtil.UNI_SUR_LOW_END) {
if (0 == downto) {
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
} else {
//取出連續兩個字符進行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、 其次，根據token的hashcode定位到postingHash[]上的位置。 我們通過code & postingHashMask來找到當前token在postingHash[]上的位置(其中postingsHashMask = postingsHashSize-1)。當產生Hash沖突的時候，其解決辦法就是不斷計算新的位置直到不產生沖突為止。
?
這里順便提一下：code & postingHashMask 和code % postingHashMask是完全等價的，而且位運算效率更高，Lucene經常使用位運算。
//計算當前token將要插入在Hash表中的位置，code & postingsHashMask等價于code % postingHashMask
//postingsHashMask=postingsHashSize-1
int hashPos = code & postingsHashMask;
//取出原hash表中hashPos位置上的數據
p = postingsHash[hashPos];
//如果原Hash表中的該位置上有數據并且兩個token的字符串內容不等，則產生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的各種信息寫入數據池，并在PostingList中存儲數據池的地址偏移。 整個 過程有兩種可能：
?
(1) 如果當前token在前面從未遇到過，也就是已經加入索引結構的所有詞都沒有這個詞語。那么首先需要在postingHash中開辟一個新的PostingList準備存放當前token所對應信息(code line :18，33)。接著在CharBlackPool中創建一個新的區域來存儲當前token的字符串信息(line: 27)，并且將地址偏移記錄在新創建的PostingList.textStart中(line: 25)。然后就是在ByteBlockPool中開辟兩個slice (line:57，58)。并且在IntBlockPool中開辟兩個空間存儲ByteBlockPool中的新開辟的slice地址偏移(line:57，60)。最后調用 FreqProxTermsWriterPerField.newTerm() 將token的docID+freq和position信息存儲進去(line: 67)。
?
(2) 如果當前token在前面已經遇到過了，此時就不需要在三大數據池中分配新的空間存放了。直接調用 FreqProxTermsWriterPerField.addTerm() 將信息存儲進去(line:72)。
//說明當前token以前的文本中從未出現過
if (p == null) {
final int textLen1 = 1+tokenTextLen;
//當CharBlockPool當前的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;
//將當前token的內容寫入CharBlockPool中,此時text和CharBlockPool中的當前buffer都指向同一塊內存區域
final char[] text = charPool.buffer;
final int textUpto = charPool.charUpto;
//PostingList類中的textStart保存的是當前token首字母在CharBlockPool中的位置
p.textStart = textUpto + charPool.charOffset;
charPool.charUpto += textLen1;
System.arraycopy(tokenText, 0, text, textUpto, tokenTextLen);
//每個詞當中存放一個分隔符'#66535'(66535號字符,我們用“#66535”表示)
text[textUpto+tokenTextLen] = 0xffff;
assert postingsHash[hashPos] == null;
//將postingHash[hashPos]指向剛開辟的空閑RawPostList鏈表
postingsHash[hashPos] = p;
//記錄鏈表數量
numPostings++;
//如果postingsHash的加載因子達到了50%，則擴大2倍的postingsHash容量
if (numPostings == postingsHashHalfSize)
rehashPostings(2*postingsHashSize);
//當IntBlockPool中buffer容量不足時，分配一個新buffer
if (numPostingInt + intPool.intUpto > DocumentsWriter.INT_BLOCK_SIZE)
intPool.nextBuffer();
//當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對應在ByteBlockPool中兩個slice的地址偏移
intPool.intUpto += streamCount;
//PostingList類中的intStart保存的是當前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用于存儲當前token使用ByteBlckPool開辟的空間的初始位置
//也就是剛開辟的兩個塊中第一個塊的初始位置
p.byteStart = intUptos[intUptoStart];
//token原來沒有出現過的時候，FreqProxTermsWriterPerField調用newTerm()記錄docID,freq和position
consumer.newTerm(p);
} else { //如果此Token之前曾經出現過，FreqProxTermsWriterPerField調用addTerm()記錄docID,freq和position
intUptos = intPool.buffers[p.intStart >> DocumentsWriter.INT_BLOCK_SHIFT];
intUptoStart = p.intStart & DocumentsWriter.INT_BLOCK_MASK;
consumer.addTerm(p);
}
????
我們在《
全文檢索基本理論
》中講到的倒排索引結構是 token -> posting list的形式，而文檔結合的所有token組成了一個Dictionary。
TermsHashPerField類的作用就是建立這樣一個倒排索引結構——postingHash。其中
postingHash[](哈希數組)是以token的字面值作為關鍵字的，相當于Dictionary。而
postingHash的每一個元素都指向了PostingList對象，這個對象就是用來存儲指定token所對應的posting list信息(包括docID，freq，position)。實際上，真正的信息是存儲在三大數據池中的，但
PostingList對象只存儲三大數據池中的地址偏移。我們通過上面的代碼可以發現：
TermsHashPerField已經把token的字面值存儲在CharBlockPool中了，并且在ByteBlockPool中分配好的存儲空間，并將地址偏移記錄到了IntBlockPool中了。接下來要做的就是把
token所對應的docID，freq，position的信息通過
FreqProxTermsWriterPerField
的方法寫入ByteBlockPool。
?
?
★ FreqProxTermsWriterPerField ?
?
(1)當出現一個索引結構中沒有的token時，我們需要調用 newTerm()方法將token所對應的 docID，freq，position信息存儲到ByteBlockPool中。
final void newTerm(RawPostingList p0) {
assert docState.testPoint("FreqProxTermsWriterPerField.newTerm start");
FreqProxTermsWriter.PostingList p = (FreqProxTermsWriter.PostingList) p0;
//當一個新的term出現的時候，包含此Term的就只有本篇文檔，記錄其ID
p.lastDocID = docState.docID;
if (omitTermFreqAndPositions) {
p.lastDocCode = docState.docID;
} else {
//docCode是文檔ID左移一位，為什么左移，這就需要Lucene的索引文件結構來解釋了。
p.lastDocCode = docState.docID << 1;
p.docFreq = 1;
//寫入position信息到bytePool中，此時freq信息還不能寫入，因為當前的文檔還沒有處理完，尚不知道此文檔包含此token的總數。
writeProx(p, fieldState.position);
}
}
?
(2) 當出現的token在索引結構中已經存在，我們需要調用 addTerm()方法將token所對應的 docID，freq，position信息存儲到 ByteBlockPool中。
final void addTerm(RawPostingList p0) {
assert docState.testPoint("FreqProxTermsWriterPerField.addTerm start");
//取出postingHash已經存在的PostingList
FreqProxTermsWriter.PostingList p = (FreqProxTermsWriter.PostingList) p0;
assert omitTermFreqAndPositions || p.docFreq > 0;
if (omitTermFreqAndPositions) {
//p.lastDocID記錄了上一次token寫入索引結構的docID
//docState.docID記錄的是token將要寫入索引結構的當前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;
//如果當前的docID與上一次相同的token寫入的docID不同
//則表明上一篇文本中該token已經處理完畢，則將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 {
//當文檔ID不變的時候，說明此文檔中這個詞又出現了一次，從而freq加1，寫入再次出現的位置信息，用差值存儲。這里不寫入freq，因為該文檔還沒有結束
p.docFreq++;
//將position信息寫入ByteBlockPool中
writeProx(p, fieldState.position-p.lastPosition);
}
}
}
?
上面newTerm()和addTerm()方法都需要調用writeProx()方法將position信息寫入ByteBlockPool中
//將position信息寫入ByteBlockPool中
final void writeProx(FreqProxTermsWriter.PostingList p, int proxCode) {
final Payload payload;
//payloadAttribute是token的元數據信息
if (payloadAttribute == null) {
payload = null;
} else {
payload = payloadAttribute.getPayload();
}
//將position信息寫入ByteBlockPool中
//其中writeVInt()第一個參數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中的數據到底是什么樣子的呢？還有在CharBlockPool中是如何存儲token的字面值的呢？IntBlockPool又是怎么樣記錄ByteBlockPool中的地址偏移的呢？這些問題我們將在《 索引數據池及其存儲細節 》詳細闡明.
?
?
★ 總結：
?
???? 我們以前面所舉的例子為例，將《 索引數據池及內存數據細節 》中的content field的第一個token="lucene"(docID=0，position=1)創建索引結構，其圖示如下：
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
