在上一章中提到了编码压缩，讲了一个简单的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
*
* 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的时候还做了很多操作，为这棵树构建索引信息，方便查询，这块博主真的无能为力了，不知道怎么才能把这块讲好。
总结
以上是尊龙游戏旗舰厅官网 为你收集整理的的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得尊龙游戏旗舰厅官网 网站内容还不错，欢迎将尊龙游戏旗舰厅官网 推荐给好友。
