在上一章中提到了編碼壓縮，講了一個簡單的DataBlockEncoding.PREFIX算法，它用的是前序編碼壓縮的算法，它搜索到時候，是全掃描的方式搜索的，如此一來，搜索效率實在是不敢恭維，所以在hbase當中單獨拿了一個工程出來實現了Trie的數據結果，既達到了壓縮編碼的效果，亦達到了方便查詢的效果，一舉兩得，設置的方法是在上一章的末尾提了。
下面講一下這個Trie樹的原理吧。
樹里面有3中類型的數據結構，branch（分支）、leaf（葉子）、nub（節點）
1、branch 分支節點，比如圖中的t，以它為結果的詞并沒有出現過，但它是to、tea等次的分支的地方，單個t的詞沒有出現過。
2、leaf葉子節點，比如圖中的to，它下面沒有子節點了，并且出現了7次。
3、nub節點，它是結余兩者之間的，比如i，它獨立出現了11次。
下面我們就具體說一下在hbase的工程里面它是什么樣子的，下面是一個例子：
* Example inputs (numInputs=7):
* 0: AAA
* 1: AAA
* 2: AAB
* 3: AAB
* 4: AAB
* 5: AABQQ
* 6: AABQQ
* <br/><br/>
* Resulting TokenizerNodes:
* AA <- branch, numOccurrences=0, tokenStartOffset=0, token.length=2
* A <- leaf, numOccurrences=2, tokenStartOffset=2, token.length=1
* B <- nub, numOccurrences=3, tokenStartOffset=2, token.length=1
* QQ <- leaf, numOccurrences=2, tokenStartOffset=3, token.length=2這里面3個輔助字段，numOccurrences（出現次數）、tokenStartOffset（在原詞當中的位置）、token.length（詞的長度）。
描述這個數據結構用了兩個類Tokenizer和TokenizerNode。
好，我們先看一下發起點PrefixTreeCodec，這個類是繼承自DataBlockEncoder接口的，DataBlockEncoder是專門負責編碼壓縮的，它里面的有3個重要的方法，encodeKeyValues（編碼）、decodeKeyValues（反編碼）、createSeeker（創建掃描器）。
因此我們先看PrefixTreeCodec里面的encodeKeyValues方法，這個是我們的入口，我們發現internalEncodeKeyValues是實際編碼的地方。
private void internalEncodeKeyValues(DataOutputStream encodedOutputStream, ByteBuffer rawKeyValues, boolean includesMvccVersion) throws IOException { rawKeyValues.rewind(); PrefixTreeEncoder builder = EncoderFactory.checkOut(encodedOutputStream, includesMvccVersion);try{ KeyValue kv; while ((kv = KeyValueUtil.nextShallowCopy(rawKeyValues, includesMvccVersion)) != null) { builder.write(kv); } builder.flush(); }finally{ EncoderFactory.checkIn(builder); }
}可以看到從rawKeyValues里面不斷讀取kv出來，用PrefixTreeEncoder.write方法來進行編碼，最后調用flush進行輸出。
我們現在就進入PrefixTreeEncoder.write的方法里面吧。
rowTokenizer.addSorted(CellUtil.fillRowRange(cell, rowRange));
addFamilyPart(cell);
addQualifierPart(cell);
addAfterRowFamilyQualifier(cell);
這里就跳到Tokenizer.addSorted方法里面。
public void addSorted(final ByteRange bytes) { ++numArraysAdded; //先檢查最大長度，如果它是最大，改變最大長度 if (bytes.getLength() > maxElementLength) { maxElementLength = bytes.getLength(); } if (root == null) { // 根節點root = addNode(null, 1, 0, bytes, 0); } else { root.addSorted(bytes); } }如果root節點為空，就new一個root節點出來，有了根節點之后，就把節點添加到root節點的孩子隊列里面。
下面貼一下addSorted的代碼吧。
public void addSorted(final ByteRange bytes) {// recursively build the tree/* * 前綴完全匹配，子節點也不為空，取出最后一個節點，和最后一個節點也部分匹配 * 就添加到最后一個節點的子節點當中 */ if (matchesToken(bytes) && CollectionUtils.notEmpty(children)) { TokenizerNode lastChild = CollectionUtils.getLast(children); //和最后一個節點前綴部分匹配 if (lastChild.partiallyMatchesToken(bytes)) { lastChild.addSorted(bytes); return; } }
//匹配長度 int numIdenticalTokenBytes = numIdenticalBytes(bytes);// should be <= token.length //當前token的起始長度是不變的了，剩余的尾巴的其實位置 int tailOffset = tokenStartOffset + numIdenticalTokenBytes; //尾巴的長度 int tailLength = bytes.getLength() - tailOffset;if (numIdenticalTokenBytes == token.getLength()) { //和該節點完全匹配 if (tailLength == 0) {// identical to this node (case 1) incrementNumOccurrences(1); } else {// 加到節點的下面，作為孩子 int childNodeDepth = nodeDepth + 1; int childTokenStartOffset = tokenStartOffset + numIdenticalTokenBytes; TokenizerNode newChildNode = builder.addNode(this, childNodeDepth, childTokenStartOffset, bytes, tailOffset); addChild(newChildNode); } } else {split(numIdenticalTokenBytes, bytes); } }
1、我們先添加一個AAA進去，它是根節點，parent是null，深度為1，在原詞中起始位置為0。
2、添加一個AAA，它首先和之前的AAA相比，完全一致，走的是incrementNumOccurrences(1)，出現次數（numOccurrences）變成2。
3、添加AAB，它和AAA相比，匹配的長度為2，尾巴長度為1，那么它走的是這條路split(numIdenticalTokenBytes, bytes)這條路徑。
protected void split(int numTokenBytesToRetain, final ByteRange bytes) { int childNodeDepth = nodeDepth; int childTokenStartOffset = tokenStartOffset + numTokenBytesToRetain;//create leaf AA 先創建左邊的節點 TokenizerNode firstChild = builder.addNode(this, childNodeDepth, childTokenStartOffset, token, numTokenBytesToRetain); firstChild.setNumOccurrences(numOccurrences);// do before clearing this node's numOccurrences //這一步很重要，更改原節點的長度，node節點記錄的數據不是一個簡單的byte[] token.setLength(numTokenBytesToRetain);//shorten current token from BAA to B numOccurrences = 0;//current node is now a branchmoveChildrenToDifferentParent(firstChild);//point the new leaf (AA) to the new branch (B) addChild(firstChild);//add the new leaf (AA) to the branch's (B's) children//create leaf 再創建右邊的節點TokenizerNode secondChild = builder.addNode(this, childNodeDepth, childTokenStartOffset, bytes, tokenStartOffset + numTokenBytesToRetain); addChild(secondChild);//add the new leaf (00) to the branch's (B's) children// 遞歸增加左右子樹的深度 firstChild.incrementNodeDepthRecursively(); secondChild.incrementNodeDepthRecursively(); }
?split完成的效果：
1) 子節點的tokenStartOffset 等于父節點的tokenStartOffset 加上匹配的長度，這里是0+2=2
2)創建左孩子，token為A，深度為父節點一致，出現次數和父親一樣2次
3）父節點的token長度變為匹配長度2，即（AA），出現次數置為0
4）把原來節點的子節點指向左孩子
5）把左孩子的父節點指向當前節點
6）創建右孩子，token為B，深度為父節點一致
7）把右孩子的父節點指向當前節點
8）把左右孩子的深度遞歸增加。
4、 添加AAB，和AA完全匹配，最后一個孩子節點AAB也匹配，調用AAB節點的addSorted(bytes)，因為是完全匹配，所以和第二步一樣，B的出現次數加1
5、添加AABQQ，和AA完全匹配，最后一個孩子節點AAB也匹配，調用AAB節點的addSorted(bytes), 成為AAB的孩子
先走的這段代碼，走進遞歸:
if (matchesToken(bytes) && CollectionUtils.notEmpty(children)) { TokenizerNode lastChild = CollectionUtils.getLast(children); //和最后一個節點前綴部分匹配 if (lastChild.partiallyMatchesToken(bytes)) { lastChild.addSorted(bytes); return; }
}
然后再走的這段代碼：
int childNodeDepth = nodeDepth + 1;
int childTokenStartOffset = tokenStartOffset + numIdenticalTokenBytes;
TokenizerNode newChildNode = builder.addNode(this, childNodeDepth, childTokenStartOffset, bytes, tailOffset);
addChild(newChildNode);
6、添加AABQQ，和之前的一樣，這里就不重復了，增加QQ的出現次數。 構建玩Trie樹之后，在flush的時候還做了很多操作，為這棵樹構建索引信息，方便查詢，這塊博主真的無能為力了，不知道怎么才能把這塊講好。
總結
以上是生活随笔 為你收集整理的hbase源码系列（五）Trie单词查找树 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
