LongTree的正确理解分析
在网上有一篇文件介绍LongTreer的原理的,但是对于leftChildren和rightSiblings的讲解似乎有些不完整。
leftChildren保存某结点儿子在keys[]中的数组索引值,同理rightSiblings保存其本结点兄弟在keys[]中的数组索引值。
通过一些测试让我理解这一功能:
下面是从JiveMessage表中截取的部分数据
messageID ParentMessageID threadID forumID 2 NULL 1 31 31 2 1 31 46 2 1 31 61 2 1 31 62 2 1 31 32 31 1 31 47 46 1 31
|
在LongTree中的addChild方法加入了部分代码,也修改了部分代码,目的是为了输出leftChildren 、rightSiblings的数值
public void addChild(long parentKey, long newKey) { // 找到一个给定的节点parentKey的父结点 char parentIndex = findKey(parentKey, (char) 1); //System.out.println("父节点索引号:" + (int)parentIndex + "-----父结点:" + parentKey + // "-----子结点:" + (int)newKey); if (parentIndex == 0) { throw new IllegalArgumentException("Parent key " + parentKey + " not found when adding child " + newKey + "."); }
keys[nextIndex] = newKey; leftChildren[nextIndex] = 0; rightSiblings[nextIndex] = 0; System.out.println("keys[" + (int) nextIndex + "] = " + (int) newKey);
// Adjust references. Check to see if the parent has any children. if (leftChildren[parentIndex] == 0) { // No children, therefore make the new key the first child. leftChildren[parentIndex] = nextIndex; System.out.println("leftChildren[" + (int) parentIndex + "] = " + (int) nextIndex); } else { // The parent has children, so find the right-most child. long siblingIndex = leftChildren[parentIndex];
while (rightSiblings[new Long(siblingIndex).intValue()] != 0) { siblingIndex = rightSiblings[new Long(siblingIndex).intValue()]; }
// Add the new entry as a sibling of that last child.
//rightSiblings[new Long(siblingIndex).intValue()] = nextIndex;
int tmpint = new Long(siblingIndex).intValue(); rightSiblings[tmpint] = nextIndex ; System.out.println("rightSiblings[" + tmpint +"] = " + (int)nextIndex); }
// Finally, increment nextIndex so it's ready for next add. nextIndex++; }
|
下面是输出值keys[2] = 31
leftChildren[1] = 2
keys[3] = 32
leftChildren[2] = 3
keys[4] = 46
rightSiblings[2] = 4
keys[5] = 47
leftChildren[4] = 5
keys[6] = 61
rightSiblings[4] = 6
keys[7] = 62
rightSiblings[6] = 7
得到了这么一组值,该如何理解呢?
假设有
leftChildren[X] = Y
正确理解是
keys[Y]是keys[X]的一个儿子结点
同理
rightSiblings[X] = Y
正确理解是
keys[Y]是keys[X]的一个兄弟结点
也就是说leftChildren、rightSiblings保存的是它们子结点、兄弟结点在keys[]中的数组索引值而已,而不能说leftChildren保存的是某一结点的子结点
时间有限,懒得去好好的整理文字,大家能理解就行
愿和更多的对Jive有深入研究的朋友交流
QQ:45214493(对JIVE没有研究者勿加)