Changed the split in the rtree to be non-recursive by making sure the split can successfully insert the new tuple in either split pages assuming tuples are not bigger than half of the page size. Added test cases for the new rtree page split. Fixed a bug in the page header size calculations in btree and rtree.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@2359 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index e9f6603..c21fa79 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -118,7 +118,8 @@
int tupleCount = buf.getInt(tupleCountOff);
- // determine start of target free space (depends on assumptions stated above)
+ // determine start of target free space (depends on assumptions stated
+ // above)
int freeSpace = buf.getInt(freeSpaceOff);
int prefixTupleCount = buf.getInt(prefixTupleCountOff);
if (prefixTupleCount > 0) {
@@ -183,7 +184,8 @@
int length = tupleSlotOff - slotEndOff;
System.arraycopy(buf.array(), slotEndOff, buf.array(), slotEndOff + slotManager.getSlotSize(), length);
- // maintain space information, get size of tuple suffix (suffix could be entire tuple)
+ // maintain space information, get size of tuple suffix (suffix could be
+ // entire tuple)
int tupleSize = 0;
int suffixFieldStart = 0;
if (prefixSlotNum == FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
@@ -217,7 +219,8 @@
if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
return FrameOpSpaceStatus.SUFFICIENT_SPACE;
- // See if the tuple matches a prefix and will fit after truncating the prefix.
+ // See if the tuple matches a prefix and will fit after truncating the
+ // prefix.
int prefixSlotNum = slotManager.findPrefix(tuple, framePrefixTuple);
if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
int prefixSlotOff = slotManager.getPrefixSlotOff(prefixSlotNum);
@@ -266,7 +269,8 @@
int numPrefixFields = frameTuple.getNumPrefixFields();
int fieldCount = frameTuple.getFieldCount();
if (numPrefixFields != 0) {
- // Check the space requirements for updating the suffix of the original tuple.
+ // Check the space requirements for updating the suffix of the
+ // original tuple.
oldTupleBytes = frameTuple.getSuffixTupleSize();
newTupleBytes = tupleWriter.bytesRequired(newTuple, numPrefixFields, fieldCount - numPrefixFields);
} else {
@@ -284,7 +288,8 @@
int freeContiguous = buf.capacity() - buf.getInt(freeSpaceOff)
- ((buf.getInt(tupleCountOff) + buf.getInt(prefixTupleCountOff)) * slotManager.getSlotSize());
- // Enough space if we delete the old tuple and insert the new one without compaction?
+ // Enough space if we delete the old tuple and insert the new one
+ // without compaction?
if (newTupleBytes <= freeContiguous) {
return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
}
@@ -314,7 +319,8 @@
bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, fieldCount - numPrefixFields,
buf.array(), suffixTupleStartOff);
} else {
- // Insert the new tuple suffix at the end of the free space, and change
+ // Insert the new tuple suffix at the end of the free space, and
+ // change
// the slot value (effectively "deleting" the old tuple).
int newSuffixTupleStartOff = buf.getInt(freeSpaceOff);
bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, fieldCount - numPrefixFields,
@@ -382,14 +388,16 @@
int tupleIndex = slotManager.decodeSecondSlotField(targetTupleIndex);
// Examine the tuple index to determine whether it is valid or not.
if (tupleIndex != slotManager.getGreatestKeyIndicator()) {
- // We need to check the key to determine whether it's an insert or an update.
+ // We need to check the key to determine whether it's an insert or
+ // an update.
frameTuple.resetByTupleIndex(this, tupleIndex);
if (cmp.compare(searchTuple, frameTuple) == 0) {
// The keys match, it's an update.
return frameTuple;
}
}
- // Either the tuple index is a special indicator, or the keys don't match.
+ // Either the tuple index is a special indicator, or the keys don't
+ // match.
// In those cases, we are definitely dealing with an insert.
return null;
}
@@ -537,7 +545,7 @@
}
@Override
- public boolean split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
BTreeFieldPrefixNSMLeafFrame rf = (BTreeFieldPrefixNSMLeafFrame) rightFrame;
@@ -545,7 +553,8 @@
int tupleCount = getTupleCount();
int prefixTupleCount = getPrefixTupleCount();
- // Find split point, and determine into which frame the new tuple should be inserted into.
+ // Find split point, and determine into which frame the new tuple should
+ // be inserted into.
int tuplesToLeft;
int midSlotNum = tupleCount / 2;
ITreeIndexFrame targetFrame = null;
@@ -575,7 +584,8 @@
}
}
- // if we are splitting in the middle of a prefix both pages need to have the prefix slot and tuple
+ // if we are splitting in the middle of a prefix both pages need to have
+ // the prefix slot and tuple
int boundaryTupleSlotOff = rf.slotManager.getTupleSlotOff(tuplesToLeft - 1);
int boundaryTupleSlot = buf.getInt(boundaryTupleSlotOff);
int boundaryPrefixSlotNum = rf.slotManager.decodeFirstSlotField(boundaryTupleSlot);
@@ -585,7 +595,8 @@
prefixesToLeft++; // tuples on both pages share one prefix
}
- // move prefix tuples on right page to beginning of page and adjust prefix slots
+ // move prefix tuples on right page to beginning of page and adjust
+ // prefix slots
if (prefixesToRight > 0 && prefixesToLeft > 0 && prefixTupleCount > 1) {
int freeSpace = rf.getOrigFreeSpaceOff();
@@ -650,7 +661,8 @@
// insert last key
int targetTupleIndex;
- // it's safe to catch this exception since it will have been caught before reaching here
+ // it's safe to catch this exception since it will have been caught
+ // before reaching here
try {
targetTupleIndex = ((IBTreeLeafFrame) targetFrame).findInsertTupleIndex(tuple);
} catch (TreeIndexException e) {
@@ -665,7 +677,6 @@
splitKey.initData(splitKeySize);
tupleWriter.writeTupleFields(frameTuple, 0, cmp.getKeyFieldCount(), splitKey.getBuffer().array(), 0);
splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
- return true;
}
@Override
@@ -719,7 +730,8 @@
FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) {
int slot = slotManager.findSlot(searchKey, pageTuple, framePrefixTuple, cmp, ftm, ftp);
int tupleIndex = slotManager.decodeSecondSlotField(slot);
- // TODO: Revisit this one. Maybe there is a cleaner way to solve this in the RangeSearchCursor.
+ // TODO: Revisit this one. Maybe there is a cleaner way to solve this in
+ // the RangeSearchCursor.
if (tupleIndex == FieldPrefixSlotManager.GREATEST_KEY_INDICATOR
|| tupleIndex == FieldPrefixSlotManager.ERROR_INDICATOR)
return -1;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index 61fed72..f6c3963 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -94,9 +94,12 @@
System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple) + childPtrSize,
buf.array(), rightLeafOff, childPtrSize);
} else {
- // If slotOff has a right (slot-)neighbor then update its child pointer.
- // The only time when this is NOT the case, is when this is the very first tuple
- // (or when the splitkey goes into the rightmost slot but that case is handled in the if above).
+ // If slotOff has a right (slot-)neighbor then update its child
+ // pointer.
+ // The only time when this is NOT the case, is when this is the very
+ // first tuple
+ // (or when the splitkey goes into the rightmost slot but that case
+ // is handled in the if above).
if (buf.getInt(tupleCountOff) > 1) {
int rightNeighborOff = slotOff - slotManager.getSlotSize();
frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(rightNeighborOff));
@@ -176,7 +179,7 @@
}
@Override
- public boolean split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
ByteBuffer right = rightFrame.getBuffer();
int tupleCount = getTupleCount();
@@ -253,7 +256,6 @@
throw new IllegalStateException(e);
}
targetFrame.insert(savedSplitKey.getTuple(), targetTupleIndex);
- return true;
}
@Override
@@ -270,7 +272,8 @@
sortedTupleOffs.add(new SlotOffTupleOff(i, slotOff, tupleOff));
}
Collections.sort(sortedTupleOffs);
- // Iterate over the sorted slots, and move their corresponding tuples to the left, reclaiming free space.
+ // Iterate over the sorted slots, and move their corresponding tuples to
+ // the left, reclaiming free space.
for (int i = 0; i < sortedTupleOffs.size(); i++) {
int tupleOff = sortedTupleOffs.get(i).tupleOff;
frameTuple.resetByTupleOffset(buf, tupleOff);
@@ -293,11 +296,13 @@
if (buf.getInt(tupleCountOff) == 0) {
return buf.getInt(rightLeafOff);
}
- // Trivial cases where no low key or high key was given (e.g. during an index scan).
+ // Trivial cases where no low key or high key was given (e.g. during an
+ // index scan).
ITupleReference tuple = null;
FindTupleMode fsm = null;
// The target comparator may be on a prefix of the BTree key fields.
- MultiComparator targetCmp = pred.getLowKeyComparator();;
+ MultiComparator targetCmp = pred.getLowKeyComparator();
+ ;
tuple = pred.getLowKey();
if (tuple == null) {
return getLeftmostChildPageId();
@@ -369,7 +374,7 @@
@Override
public int getPageHeaderSize() {
- return rightLeafOff;
+ return rightLeafOff + 4;
}
private int getLeftChildPageOff(ITupleReference tuple) {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 3883b80..04b3077 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -137,7 +137,7 @@
}
@Override
- public boolean split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
ByteBuffer right = rightFrame.getBuffer();
int tupleCount = getTupleCount();
@@ -196,16 +196,11 @@
// Set the split key to be highest key in the left page.
int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- try {
frameTuple.resetByTupleOffset(buf, tupleOff);
- } catch (Exception e) {
- throw new IllegalStateException(e);
- }
int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
splitKey.initData(splitKeySize);
tupleWriter.writeTupleFields(frameTuple, 0, cmp.getKeyFieldCount(), splitKey.getBuffer().array(), 0);
splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
- return true;
}
@Override
@@ -227,7 +222,7 @@
@Override
public int getPageHeaderSize() {
- return nextLeafOff;
+ return nextLeafOff + 4;
}
@Override
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
index bc02d19..612af25 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
@@ -62,8 +62,7 @@
// for debugging
public String printHeader();
- // Return true if the new tuple has been successfully inserted.
- public boolean split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey);
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey);
public ISlotManager getSlotManager();
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java
index 2341b4e..b1d026a 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java
@@ -25,7 +25,7 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
public interface IRTreePolicy {
- public boolean split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
+ public void split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey);
public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java
index 039acc8..3341ace 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java
@@ -64,7 +64,7 @@
}
}
- public boolean split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
+ public void split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterleftRTreeFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -198,18 +198,19 @@
// compact both pages
rightFrame.compact();
leftRTreeFrame.compact();
-
- boolean insertedNewTuple = false;
+
+ // The assumption here is that the new tuple cannot be larger than page
+ // size, thus it must fit in either pages.
if (insertedNewTupleInRightFrame) {
if (rightFrame.hasSpaceInsert(tuple) == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
rightFrame.insert(tuple, -1);
- insertedNewTuple = true;
- }
- } else {
- if (leftRTreeFrame.hasSpaceInsert(tuple) == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
+ } else {
leftRTreeFrame.insert(tuple, -1);
- insertedNewTuple = true;
}
+ } else if (leftRTreeFrame.hasSpaceInsert(tuple) == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
+ leftRTreeFrame.insert(tuple, -1);
+ } else {
+ rightFrame.insert(tuple, -1);
}
int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
@@ -229,7 +230,6 @@
tupleEntries1.clear();
tupleEntries2.clear();
- return insertedNewTuple;
}
public void generateDist(ITreeIndexFrame leftRTreeFrame, ITreeIndexTupleReference frameTuple,
@@ -252,7 +252,8 @@
}
}
- public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple, MultiComparator cmp) {
+ public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
+ MultiComparator cmp) {
cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
frameTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -292,18 +293,22 @@
frameTuple.resetByTupleIndex(frame, j);
cmpFrameTuple.resetByTupleIndex(frame, tupleEntries1.get(i).getTupleIndex());
- int c = ((RTreeNSMInteriorFrame)frame).pointerCmp(frameTuple, cmpFrameTuple, cmp);
+ int c = ((RTreeNSMInteriorFrame) frame).pointerCmp(frameTuple, cmpFrameTuple, cmp);
if (c != 0) {
- double intersection = RTreeComputationUtils.overlappedArea(frameTuple, tuple, cmpFrameTuple, cmp, keyValueProviders);
+ double intersection = RTreeComputationUtils.overlappedArea(frameTuple, tuple,
+ cmpFrameTuple, cmp, keyValueProviders);
if (intersection != 0.0) {
- difference += intersection - RTreeComputationUtils.overlappedArea(frameTuple, null, cmpFrameTuple, cmp, keyValueProviders);
+ difference += intersection
+ - RTreeComputationUtils.overlappedArea(frameTuple, null, cmpFrameTuple, cmp,
+ keyValueProviders);
}
} else {
id = j;
}
}
- double enlargedArea = RTreeComputationUtils.enlargedArea(cmpFrameTuple, tuple, cmp, keyValueProviders);
+ double enlargedArea = RTreeComputationUtils.enlargedArea(cmpFrameTuple, tuple, cmp,
+ keyValueProviders);
if (difference < minOverlap) {
minOverlap = difference;
minEnlargedArea = enlargedArea;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
index 558ac19..eeada0a 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
@@ -54,7 +54,6 @@
} else {
rtreePolicy = new RStarTreePolicy(tupleWriter, keyValueProviders, cmpFrameTuple, totalFreeSpaceOff);
}
-
}
private static double computeDoubleEpsilon() {
@@ -112,8 +111,8 @@
}
@Override
- public boolean split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
- return rtreePolicy.split(this, buf, rightFrame, slotManager, frameTuple, tuple, splitKey);
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
+ rtreePolicy.split(this, buf, rightFrame, slotManager, frameTuple, tuple, splitKey);
}
abstract public int getTupleSize(ITupleReference tuple);
@@ -152,7 +151,7 @@
@Override
public int getPageHeaderSize() {
- return rightPageOff;
+ return rightPageOff + 4;
}
@Override
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java
index da9588d..1d76b0e 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java
@@ -55,8 +55,8 @@
}
}
- public boolean split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame,
- ISlotManager slotManager, ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey) {
+ public void split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
+ ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
@@ -170,14 +170,18 @@
rightFrame.compact();
leftRTreeFrame.compact();
- boolean insertedNewTuple = false;
- if (rec[0].enlargedArea(tuple, keyValueProviders) < rec[1].enlargedArea(tuple, keyValueProviders)
- && rightFrame.hasSpaceInsert(tuple) == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
- rightFrame.insert(tuple, -1);
- insertedNewTuple = true;
+ // The assumption here is that the new tuple cannot be larger than page
+ // size, thus it must fit in either pages.
+ if (rec[0].enlargedArea(tuple, keyValueProviders) < rec[1].enlargedArea(tuple, keyValueProviders)) {
+ if (rightFrame.hasSpaceInsert(tuple) == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
+ rightFrame.insert(tuple, -1);
+ } else {
+ leftRTreeFrame.insert(tuple, -1);
+ }
} else if (leftRTreeFrame.hasSpaceInsert(tuple) == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
leftRTreeFrame.insert(tuple, -1);
- insertedNewTuple = true;
+ } else {
+ rightFrame.insert(tuple, -1);
}
int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
@@ -193,7 +197,6 @@
rTreeTupleWriterRightFrame.writeTupleFields(((RTreeNSMFrame) rightFrame).getTuples(), 0,
rTreeSplitKey.getRightPageBuffer(), 0);
rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
- return insertedNewTuple;
}
public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 11742bb..40e0ff0 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -163,37 +163,35 @@
throw new IllegalArgumentException("The low key point has larger coordinates than the high key point.");
}
}
- boolean tupleInserted = false;
- while (!tupleInserted) {
- try {
- ICachedPage leafNode = findLeaf(ctx);
- int pageId = ctx.pathList.getLastPageId();
- ctx.pathList.moveLast();
- tupleInserted = insertTuple(leafNode, pageId, ctx.getTuple(), ctx, true);
+ try {
+ ICachedPage leafNode = findLeaf(ctx);
- while (true) {
- if (ctx.splitKey.getLeftPageBuffer() != null) {
- updateParentForInsert(ctx);
- } else {
- break;
- }
- }
- } finally {
- for (int i = ctx.NSNUpdates.size() - 1; i >= 0; i--) {
- ICachedPage node = ctx.NSNUpdates.get(i);
- ctx.interiorFrame.setPage(node);
- ctx.interiorFrame.setPageNsn(incrementGlobalNsn());
- }
+ int pageId = ctx.pathList.getLastPageId();
+ ctx.pathList.moveLast();
+ insertTuple(leafNode, pageId, ctx.getTuple(), ctx, true);
- for (int i = ctx.LSNUpdates.size() - 1; i >= 0; i--) {
- ICachedPage node = ctx.LSNUpdates.get(i);
- ctx.interiorFrame.setPage(node);
- ctx.interiorFrame.setPageLsn(incrementGlobalNsn());
- node.releaseWriteLatch();
- bufferCache.unpin(node);
+ while (true) {
+ if (ctx.splitKey.getLeftPageBuffer() != null) {
+ updateParentForInsert(ctx);
+ } else {
+ break;
}
}
+ } finally {
+ for (int i = ctx.NSNUpdates.size() - 1; i >= 0; i--) {
+ ICachedPage node = ctx.NSNUpdates.get(i);
+ ctx.interiorFrame.setPage(node);
+ ctx.interiorFrame.setPageNsn(incrementGlobalNsn());
+ }
+
+ for (int i = ctx.LSNUpdates.size() - 1; i >= 0; i--) {
+ ICachedPage node = ctx.LSNUpdates.get(i);
+ ctx.interiorFrame.setPage(node);
+ ctx.interiorFrame.setPageLsn(incrementGlobalNsn());
+ node.releaseWriteLatch();
+ bufferCache.unpin(node);
+ }
}
}
@@ -322,7 +320,7 @@
}
}
- private boolean insertTuple(ICachedPage node, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
+ private void insertTuple(ICachedPage node, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
throws HyracksDataException, TreeIndexException {
boolean succeeded = false;
FrameOpSpaceStatus spaceStatus;
@@ -332,7 +330,6 @@
spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple);
}
- boolean tupleInserted = true;
switch (spaceStatus) {
case SUFFICIENT_CONTIGUOUS_SPACE: {
try {
@@ -402,7 +399,7 @@
rightFrame.initBuffer((byte) 0);
rightFrame.setRightPage(ctx.interiorFrame.getRightPage());
ctx.modificationCallback.found(null);
- tupleInserted = ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
+ ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
ctx.leafFrame.setRightPage(rightPageId);
}
succeeded = true;
@@ -477,7 +474,6 @@
break;
}
}
- return tupleInserted;
}
private void updateParentForInsert(RTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
index 904de6d..fb2fb38 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
@@ -47,10 +47,10 @@
public static final int RTREE_HYRACKS_FRAME_SIZE = 128;
// Mem configuration for LSMRTree and LSMRTreeWithAntiMatterTuples.
- public static final int LSM_RTREE_DISK_PAGE_SIZE = 256;
+ public static final int LSM_RTREE_DISK_PAGE_SIZE = 512;
public static final int LSM_RTREE_DISK_NUM_PAGES = 1000;
public static final int LSM_RTREE_DISK_MAX_OPEN_FILES = 2000;
- public static final int LSM_RTREE_MEM_PAGE_SIZE = 256;
+ public static final int LSM_RTREE_MEM_PAGE_SIZE = 512;
public static final int LSM_RTREE_MEM_NUM_PAGES = 1000;
public static final int LSM_RTREE_HYRACKS_FRAME_SIZE = 128;
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeExamplesTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeExamplesTest.java
index e88a259..e911a98 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeExamplesTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeExamplesTest.java
@@ -27,12 +27,15 @@
import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.data.std.primitive.UTF8StringPointable;
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationCallback;
import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
@@ -58,10 +61,10 @@
throws TreeIndexException;
/**
- * Two Dimensions Example.
- * Create an RTree index of two dimensions, where they keys are of type
- * integer, and the payload is two integer values. Fill index with random
- * values using insertions (not bulk load). Perform scans and range search.
+ * Two Dimensions Example. Create an RTree index of two dimensions, where
+ * they keys are of type integer, and the payload is two integer values.
+ * Fill index with random values using insertions (not bulk load). Perform
+ * scans and range search.
*/
@Test
public void twoDimensionsExample() throws Exception {
@@ -162,10 +165,240 @@
}
/**
- * Two Dimensions Example.
- * Create an RTree index of three dimensions, where they keys are of type
- * double, and the payload is one double value. Fill index with random
- * values using insertions (not bulk load). Perform scans and range search.
+ * This test the rtree page split. Originally this test didn't pass since
+ * the rtree assumes always that there will be enough space for the new
+ * tuple after split. Now it passes since if there is not space in the
+ * designated page, then we will just insert it in the other split page.
+ */
+ @Test
+ public void rTreePageSplitTestExample() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("RTree page split test.");
+ }
+
+ // Declare fields.
+ int fieldCount = 5;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = UTF8StringPointable.TYPE_TRAITS;
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+
+ // Declare RTree keys.
+ int rtreeKeyFieldCount = 4;
+ IBinaryComparatorFactory[] rtreeCmpFactories = new IBinaryComparatorFactory[rtreeKeyFieldCount];
+ rtreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ rtreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ rtreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ rtreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // Declare BTree keys, this will only be used for LSMRTree
+ int btreeKeyFieldCount = 5;
+ IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+ btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[4] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ rtreeCmpFactories.length, IntegerPointable.FACTORY);
+
+ ITreeIndex treeIndex = createTreeIndex(typeTraits, rtreeCmpFactories, btreeCmpFactories,
+ valueProviderFactories, RTreePolicyType.RTREE);
+
+ treeIndex.create();
+ treeIndex.activate();
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ IIndexAccessor indexAccessor = (IIndexAccessor) treeIndex.createAccessor(TestOperationCallback.INSTANCE,
+ TestOperationCallback.INSTANCE);
+
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+ String data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ treeIndex.deactivate();
+ treeIndex.destroy();
+ }
+
+ /**
+ * This test the r*tree page split. Originally this test didn't pass since
+ * the r*tree assumes always that there will be enough space for the new
+ * tuple after split. Now it passes since if there is not space in the
+ * designated page, then we will just insert it in the other split page.
+ */
+ @Test
+ public void rStarTreePageSplitTestExample() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("R*Tree page split test.");
+ }
+
+ // Declare fields.
+ int fieldCount = 5;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = UTF8StringPointable.TYPE_TRAITS;
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+
+ // Declare RTree keys.
+ int rtreeKeyFieldCount = 4;
+ IBinaryComparatorFactory[] rtreeCmpFactories = new IBinaryComparatorFactory[rtreeKeyFieldCount];
+ rtreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ rtreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ rtreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ rtreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // Declare BTree keys, this will only be used for LSMRTree
+ int btreeKeyFieldCount = 5;
+ IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+ btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ btreeCmpFactories[4] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ rtreeCmpFactories.length, IntegerPointable.FACTORY);
+
+ ITreeIndex treeIndex = createTreeIndex(typeTraits, rtreeCmpFactories, btreeCmpFactories,
+ valueProviderFactories, RTreePolicyType.RSTARTREE);
+
+ treeIndex.create();
+ treeIndex.activate();
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ IIndexAccessor indexAccessor = (IIndexAccessor) treeIndex.createAccessor(TestOperationCallback.INSTANCE,
+ TestOperationCallback.INSTANCE);
+
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+ String data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ p1x = rnd.nextInt();
+ p1y = rnd.nextInt();
+ p2x = rnd.nextInt();
+ p2y = rnd.nextInt();
+ data = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
+ TupleUtils.createTuple(tb, tuple, fieldSerdes, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), data);
+ indexAccessor.insert(tuple);
+
+ treeIndex.deactivate();
+ treeIndex.destroy();
+ }
+
+ /**
+ * Two Dimensions Example. Create an RTree index of three dimensions, where
+ * they keys are of type double, and the payload is one double value. Fill
+ * index with random values using insertions (not bulk load). Perform scans
+ * and range search.
*/
@Test
public void threeDimensionsExample() throws Exception {
@@ -272,11 +505,10 @@
}
/**
- * Deletion Example.
- * Create an RTree index of two dimensions, where they keys are of type
- * integer, and the payload is one integer value. Fill index with random
- * values using insertions, then delete entries one-by-one. Repeat procedure
- * a few times on same RTree.
+ * Deletion Example. Create an RTree index of two dimensions, where they
+ * keys are of type integer, and the payload is one integer value. Fill
+ * index with random values using insertions, then delete entries
+ * one-by-one. Repeat procedure a few times on same RTree.
*/
@Test
public void deleteExample() throws Exception {
@@ -403,8 +635,7 @@
}
/**
- * Bulk load example.
- * Load a tree with 10,000 tuples.
+ * Bulk load example. Load a tree with 10,000 tuples.
*/
@Test
public void bulkLoadExample() throws Exception {
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java
index f97a001..57029cf 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java
@@ -52,7 +52,6 @@
protected static final Logger LOGGER = Logger.getLogger(LSMRTreeTestHarness.class.getName());
private static final long RANDOM_SEED = 50;
- private static final int DUMMY_FILE_ID = -1;
protected final int diskPageSize;
protected final int diskNumPages;