adding btree tests
git-svn-id: https://hyracks.googlecode.com/svn/trunk/hyracks@89 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/test/java/BTreeFieldPrefixNSMTest.java b/hyracks-storage-am-btree/src/test/java/BTreeFieldPrefixNSMTest.java
new file mode 100644
index 0000000..4ad5e05
--- /dev/null
+++ b/hyracks-storage-am-btree/src/test/java/BTreeFieldPrefixNSMTest.java
@@ -0,0 +1,167 @@
+package edu.uci.ics.asterix.test.storage;
+
+import java.io.File;
+import java.io.RandomAccessFile;
+import java.util.ArrayList;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import edu.uci.ics.asterix.common.config.GlobalConfig;
+import edu.uci.ics.asterix.indexing.btree.frames.FieldPrefixNSMLeaf;
+import edu.uci.ics.asterix.indexing.btree.impls.FieldPrefixSlotManager;
+import edu.uci.ics.asterix.indexing.btree.impls.MultiComparator;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IComparator;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IFieldAccessor;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IPrefixSlotManager;
+import edu.uci.ics.asterix.indexing.types.Int32Accessor;
+import edu.uci.ics.asterix.indexing.types.Int32Comparator;
+import edu.uci.ics.asterix.om.AInt32;
+import edu.uci.ics.asterix.storage.buffercache.BufferAllocator;
+import edu.uci.ics.asterix.storage.buffercache.BufferCache;
+import edu.uci.ics.asterix.storage.buffercache.ClockPageReplacementStrategy;
+import edu.uci.ics.asterix.storage.buffercache.IBufferCache;
+import edu.uci.ics.asterix.storage.buffercache.ICacheMemoryAllocator;
+import edu.uci.ics.asterix.storage.buffercache.ICachedPage;
+import edu.uci.ics.asterix.storage.buffercache.IPageReplacementStrategy;
+import edu.uci.ics.asterix.storage.file.FileInfo;
+import edu.uci.ics.asterix.storage.file.FileManager;
+
+public class BTreeFieldPrefixNSMTest {
+
+ //private static final int PAGE_SIZE = 8192;
+ //private static final int PAGE_SIZE = 8192;
+ //private static final int PAGE_SIZE = 32768; // 32K
+ //private static final int PAGE_SIZE = 65536; // 64K
+ private static final int PAGE_SIZE = 131072; // 128K
+ private static final int NUM_PAGES = 40;
+
+ // to help with the logger madness
+ private void print(String str) {
+ if(GlobalConfig.ASTERIX_LOGGER.isLoggable(Level.FINEST)) {
+ GlobalConfig.ASTERIX_LOGGER.finest(str);
+ }
+ }
+
+ private void tupleInsert(FieldPrefixNSMLeaf frame, MultiComparator cmp, int f0, int f1, int f2, boolean print, ArrayList<byte[]> records) throws Exception {
+ if(print) System.out.println("INSERTING: " + f0 + " " + f1 + " " + f2);
+
+ byte[] record = new byte[12];
+ AInt32 field0 = new AInt32(f0);
+ AInt32 field1 = new AInt32(f1);
+ AInt32 field2 = new AInt32(f2);
+ System.arraycopy(field0.toBytes(), 0, record, 0, 4);
+ System.arraycopy(field1.toBytes(), 0, record, 4, 4);
+ System.arraycopy(field2.toBytes(), 0, record, 8, 4);
+ frame.insert(record, cmp);
+
+ if(records != null) records.add(record);
+ }
+
+ @Test
+ public void test01() throws Exception {
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ int numFields = 3;
+ IFieldAccessor[] fields = new IFieldAccessor[numFields];
+ fields[0] = new Int32Accessor(); // first key field
+ fields[1] = new Int32Accessor(); // second key field
+ fields[2] = new Int32Accessor(); // third key field
+
+ int keyLen = 3;
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new Int32Comparator();
+ cmps[1] = new Int32Comparator();
+ cmps[2] = new Int32Comparator();
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ ICachedPage page = bufferCache.pin(FileInfo.getDiskPageId(fileId, 0), false);
+ try {
+
+ IPrefixSlotManager slotManager = new FieldPrefixSlotManager();
+ FieldPrefixNSMLeaf frame = new FieldPrefixNSMLeaf();
+ frame.setPage(page);
+ frame.initBuffer((byte)0);
+ slotManager.setFrame(frame);
+ frame.setNumPrefixRecords(0);
+
+ String before = new String();
+ String after = new String();
+
+ int compactFreq = 5;
+ int compressFreq = 5;
+ int smallMax = 10;
+ int numRecords = 5000;
+ ArrayList<byte[]> records = new ArrayList<byte[]>();
+ records.ensureCapacity(numRecords);
+
+ // insert records with random calls to compact and compress
+ for(int i = 0; i < numRecords; i++) {
+
+ if((i+1) % 100 == 0) print("INSERTING " + (i+1) + " / " + numRecords + "\n");
+
+ int a = rnd.nextInt() % smallMax;
+ int b = rnd.nextInt() % smallMax;
+ int c = i;
+ tupleInsert(frame, cmp, a, b, c, false, records);
+
+ if(rnd.nextInt() % compactFreq == 0) {
+ before = frame.printKeys(cmp);
+ frame.compact(cmp);
+ after = frame.printKeys(cmp);
+ Assert.assertEquals(before, after);
+ }
+
+ if(rnd.nextInt() % compressFreq == 0) {
+ before = frame.printKeys(cmp);
+ frame.compress(cmp);
+ after = frame.printKeys(cmp);
+ Assert.assertEquals(before, after);
+ }
+ }
+
+ // delete records with random calls to compact and compress
+ for(int i = 0; i < records.size(); i++) {
+
+ if((i+1) % 100 == 0) print("DELETING " + (i+1) + " / " + numRecords + "\n");
+
+ frame.delete(records.get(i), cmp, true);
+
+ if(rnd.nextInt() % compactFreq == 0) {
+ before = frame.printKeys(cmp);
+ frame.compact(cmp);
+ after = frame.printKeys(cmp);
+ Assert.assertEquals(before, after);
+ }
+
+ if(rnd.nextInt() % compressFreq == 0) {
+ before = frame.printKeys(cmp);
+ frame.compress(cmp);
+ after = frame.printKeys(cmp);
+ Assert.assertEquals(before, after);
+ }
+ }
+
+ } finally {
+ bufferCache.unpin(page);
+ }
+
+ bufferCache.close();
+ fileManager.close();
+ }
+}
diff --git a/hyracks-storage-am-btree/src/test/java/BTreeTest.java b/hyracks-storage-am-btree/src/test/java/BTreeTest.java
new file mode 100644
index 0000000..1d0ff55
--- /dev/null
+++ b/hyracks-storage-am-btree/src/test/java/BTreeTest.java
@@ -0,0 +1,966 @@
+package edu.uci.ics.asterix.test.storage;
+
+import java.io.File;
+import java.io.RandomAccessFile;
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.asterix.common.config.GlobalConfig;
+import edu.uci.ics.asterix.indexing.btree.impls.BTree;
+import edu.uci.ics.asterix.indexing.btree.impls.BTreeDiskOrderScanCursor;
+import edu.uci.ics.asterix.indexing.btree.impls.BTreeMetaFactory;
+import edu.uci.ics.asterix.indexing.btree.impls.BTreeNSMInteriorFactory;
+import edu.uci.ics.asterix.indexing.btree.impls.BTreeNSMLeafFactory;
+import edu.uci.ics.asterix.indexing.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.asterix.indexing.btree.impls.MultiComparator;
+import edu.uci.ics.asterix.indexing.btree.impls.OrderedSlotManagerFactory;
+import edu.uci.ics.asterix.indexing.btree.impls.RangePredicate;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeCursor;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameInterior;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameInteriorFactory;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameLeaf;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameLeafFactory;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameMeta;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameMetaFactory;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IComparator;
+import edu.uci.ics.asterix.indexing.btree.interfaces.IFieldAccessor;
+import edu.uci.ics.asterix.indexing.btree.interfaces.ISlotManagerFactory;
+import edu.uci.ics.asterix.indexing.types.Int32Accessor;
+import edu.uci.ics.asterix.indexing.types.Int32Comparator;
+import edu.uci.ics.asterix.indexing.types.StringAccessor;
+import edu.uci.ics.asterix.indexing.types.StringComparator;
+import edu.uci.ics.asterix.om.AInt32;
+import edu.uci.ics.asterix.storage.buffercache.BufferAllocator;
+import edu.uci.ics.asterix.storage.buffercache.BufferCache;
+import edu.uci.ics.asterix.storage.buffercache.ClockPageReplacementStrategy;
+import edu.uci.ics.asterix.storage.buffercache.IBufferCache;
+import edu.uci.ics.asterix.storage.buffercache.ICacheMemoryAllocator;
+import edu.uci.ics.asterix.storage.buffercache.IPageReplacementStrategy;
+import edu.uci.ics.asterix.storage.file.FileInfo;
+import edu.uci.ics.asterix.storage.file.FileManager;
+
+public class BTreeTest {
+ private static final int PAGE_SIZE = 128;
+ // private static final int PAGE_SIZE = 8192;
+ private static final int NUM_PAGES = 10;
+
+ // to help with the logger madness
+ private void print(String str) {
+ if(GlobalConfig.ASTERIX_LOGGER.isLoggable(Level.FINEST)) {
+ GlobalConfig.ASTERIX_LOGGER.finest(str);
+ }
+ }
+
+ // FIXED-LENGTH KEY TEST
+ // create a B-tree with one fixed-length "key" field and one fixed-length "value" field
+ // fill B-tree with random values using insertions (not bulk load)
+ // perform ordered scan and range search
+ @Test
+ public void test01() throws Exception {
+
+ print("FIXED-LENGTH KEY TEST\n");
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
+ ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+ IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
+ IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
+ IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
+
+ IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
+ IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
+ IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
+
+ IFieldAccessor[] fields = new IFieldAccessor[2];
+ fields[0] = new Int32Accessor(); // key field
+ fields[1] = new Int32Accessor(); // value field
+
+ int keyLen = 1;
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new Int32Comparator();
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, interiorSlotManagerFactory, leafSlotManagerFactory, cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ long start = System.currentTimeMillis();
+
+ print("INSERTING INTO TREE\n");
+
+ byte[] record = new byte[8];
+ for (int i = 0; i < 10000; i++) {
+ AInt32 field0 = new AInt32(rnd.nextInt() % 10000);
+ AInt32 field1 = new AInt32(5);
+
+ byte[] f0 = field0.toBytes();
+ byte[] f1 = field1.toBytes();
+
+ System.arraycopy(f0, 0, record, 0, 4);
+ System.arraycopy(f1, 0, record, 4, 4);
+
+ if (i % 1000 == 0) {
+ long end = System.currentTimeMillis();
+ print("INSERTING " + i + " : " + field0.getIntegerValue() + " " + field1.getIntegerValue() + " " + (end - start) + "\n");
+ }
+
+ try {
+ btree.insert(record, leafFrame, interiorFrame, metaFrame);
+ } catch (Exception e) {
+ }
+ }
+ //btree.printTree(leafFrame, interiorFrame);
+
+ print("TOTALSPACE: " + f.length() + "\n");
+
+ String stats = btree.printStats();
+ print(stats);
+
+ long end = System.currentTimeMillis();
+ long duration = end - start;
+ print("DURATION: " + duration + "\n");
+
+ // ordered scan
+ print("ORDERED SCAN:\n");
+ IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
+ RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ byte[] array = scanCursor.getPage().getBuffer().array();
+ int recOffset = scanCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ scanCursor.close();
+ }
+
+ // disk-order scan
+ print("DISK-ORDER SCAN:\n");
+ BTreeDiskOrderScanCursor diskOrderCursor = new BTreeDiskOrderScanCursor(leafFrame);
+ btree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame);
+ try {
+ while (diskOrderCursor.hasNext()) {
+ diskOrderCursor.next();
+ byte[] array = diskOrderCursor.getPage().getBuffer().array();
+ int recOffset = diskOrderCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ diskOrderCursor.close();
+ }
+
+ // range search in [-1000, 1000]
+ print("RANGE SEARCH:\n");
+
+ IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
+
+ AInt32 lk = new AInt32(-1000);
+ byte[] lowKey = lk.toBytes();
+
+ AInt32 hk = new AInt32(1000);
+ byte[] highKey = hk.toBytes();
+
+ IComparator[] searchCmps = new IComparator[1];
+ searchCmps[0] = new Int32Comparator();
+ MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
+
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ byte[] array = rangeCursor.getPage().getBuffer().array();
+ int recOffset = rangeCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ rangeCursor.close();
+ }
+
+ btree.close();
+
+ bufferCache.close();
+ fileManager.close();
+ print("\n");
+ }
+
+ // COMPOSITE KEY TEST (NON-UNIQUE B-TREE)
+ // create a B-tree with one two fixed-length "key" fields and one fixed-length "value" field
+ // fill B-tree with random values using insertions (not bulk load)
+ // perform ordered scan and range search
+ @Test
+ public void test02() throws Exception {
+
+ print("COMPOSITE KEY TEST\n");
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
+ ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+ IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
+ IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
+ IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
+
+ IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
+ IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
+ IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
+
+ IFieldAccessor[] fields = new IFieldAccessor[3];
+ fields[0] = new Int32Accessor(); // key field 1
+ fields[1] = new Int32Accessor(); // key field 2
+ fields[2] = new Int32Accessor(); // value field
+
+ int keyLen = 2;
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new Int32Comparator();
+ cmps[1] = new Int32Comparator();
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ BTree btree = new BTree(bufferCache,
+ interiorFrameFactory,
+ leafFrameFactory,
+ interiorSlotManagerFactory,
+ leafSlotManagerFactory,
+ cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ long start = System.currentTimeMillis();
+
+ print("INSERTING INTO TREE\n");
+ byte[] record = new byte[12];
+ for (int i = 0; i < 10000; i++) {
+ AInt32 field0 = new AInt32(rnd.nextInt() % 2000);
+ AInt32 field1 = new AInt32(rnd.nextInt() % 1000);
+ AInt32 field2 = new AInt32(5);
+
+ byte[] f0 = field0.toBytes();
+ byte[] f1 = field1.toBytes();
+ byte[] f2 = field2.toBytes();
+
+ System.arraycopy(f0, 0, record, 0, 4);
+ System.arraycopy(f1, 0, record, 4, 4);
+ System.arraycopy(f2, 0, record, 8, 4);
+
+ if (i % 1000 == 0) {
+ print("INSERTING " + i + " : " + field0.getIntegerValue() + " " + field1.getIntegerValue() + "\n");
+ }
+
+ try {
+ btree.insert(record, leafFrame, interiorFrame, metaFrame);
+ } catch (Exception e) {
+ }
+ }
+ //btree.printTree(leafFrame, interiorFrame);
+
+ long end = System.currentTimeMillis();
+ long duration = end - start;
+ print("DURATION: " + duration + "\n");
+
+ // try a simple index scan
+ print("ORDERED SCAN:\n");
+ IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
+ RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ byte[] array = scanCursor.getPage().getBuffer().array();
+ int recOffset = scanCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ scanCursor.close();
+ }
+
+ // range search in [(-3),(3)]
+ print("RANGE SEARCH:\n");
+ IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
+
+ AInt32 lk = new AInt32(-3);
+ byte[] lowKey = lk.toBytes();
+
+ AInt32 hk = new AInt32(3);
+ byte[] highKey = hk.toBytes();
+
+ IComparator[] searchCmps = new IComparator[1];
+ searchCmps[0] = new Int32Comparator();
+ MultiComparator searchCmp = new MultiComparator(searchCmps, fields); // use only a single comparator for searching
+
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ byte[] array = rangeCursor.getPage().getBuffer().array();
+ int recOffset = rangeCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ rangeCursor.close();
+ }
+
+ btree.close();
+
+ bufferCache.close();
+ fileManager.close();
+
+ print("\n");
+ }
+
+ // VARIABLE-LENGTH TEST
+ // create a B-tree with one variable-length "key" field and one variable-length "value" field
+ // fill B-tree with random values using insertions (not bulk load)
+ // perform ordered scan and range search
+ @Test
+ public void test03() throws Exception {
+
+ print("VARIABLE-LENGTH KEY TEST\n");
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
+ ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+ IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
+ IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
+ IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
+
+ IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
+ IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
+ IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
+
+ IFieldAccessor[] fields = new IFieldAccessor[2];
+ fields[0] = new StringAccessor(); // key
+ fields[1] = new StringAccessor(); // value
+
+ int keyLen = 1;
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new StringComparator();
+
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ BTree btree = new BTree(bufferCache,
+ interiorFrameFactory,
+ leafFrameFactory,
+ interiorSlotManagerFactory,
+ leafSlotManagerFactory,
+ cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ int maxLength = 10; // max string length to be generated
+ for (int i = 0; i < 10000; i++) {
+ String field0 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
+ String field1 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
+
+ byte[] f0 = field0.getBytes();
+ byte[] f1 = field1.getBytes();
+
+ byte[] record = new byte[f0.length + f1.length + 8];
+ ByteBuffer buf = ByteBuffer.wrap(record);
+
+ int start = 0;
+ buf.putInt(start, f0.length);
+ start += 4;
+ System.arraycopy(f0, 0, record, start, f0.length);
+ start += f0.length;
+ buf.putInt(start, f1.length);
+ start += 4;
+ System.arraycopy(f1, 0, record, start, f1.length);
+ start += f1.length;
+
+ if (i % 1000 == 0) {
+ print("INSERTING " + i + ": " + cmp.printRecord(record, 0) + "\n");
+ }
+
+ try {
+ btree.insert(record, leafFrame, interiorFrame, metaFrame);
+ } catch (Exception e) {
+ }
+ }
+ // btree.printTree();
+
+ // ordered scan
+ print("ORDERED SCAN:\n");
+ IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
+ RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ byte[] array = scanCursor.getPage().getBuffer().array();
+ int recOffset = scanCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ scanCursor.close();
+ }
+
+ // range search in ["cbf", cc7"]
+ print("RANGE SEARCH:\n");
+
+ IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
+
+ byte[] lowKey = new byte[7];
+ ByteBuffer lkByteBuf = ByteBuffer.wrap(lowKey);
+ lkByteBuf.putInt(0, 3);
+ System.arraycopy("cbf".getBytes(), 0, lowKey, 4, 3);
+
+ byte[] highKey = new byte[7];
+ ByteBuffer hkByteBuf = ByteBuffer.wrap(highKey);
+ hkByteBuf.putInt(0, 3);
+ System.arraycopy("cc7".getBytes(), 0, highKey, 4, 3);
+
+ IComparator[] searchCmps = new IComparator[1];
+ searchCmps[0] = new StringComparator();
+ MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
+
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ byte[] array = rangeCursor.getPage().getBuffer().array();
+ int recOffset = rangeCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ rangeCursor.close();
+ }
+
+ btree.close();
+
+ bufferCache.close();
+ fileManager.close();
+
+ print("\n");
+ }
+
+ // DELETION TEST
+ // create a B-tree with one variable-length "key" field and one variable-length "value" field
+ // fill B-tree with random values using insertions, then delete entries one-by-one
+ // repeat procedure a few times on same B-tree
+ @Test
+ public void test04() throws Exception {
+
+ print("DELETION TEST\n");
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
+ ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+ IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
+ IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
+ IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
+
+ IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
+ IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
+ IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
+
+ IFieldAccessor[] fields = new IFieldAccessor[2];
+ fields[0] = new StringAccessor(); // key
+ fields[1] = new StringAccessor(); // value
+
+ int keyLen = 1;
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new StringComparator();
+
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ BTree btree = new BTree(bufferCache,
+ interiorFrameFactory,
+ leafFrameFactory,
+ interiorSlotManagerFactory,
+ leafSlotManagerFactory,
+ cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ int runs = 3;
+ for (int run = 0; run < runs; run++) {
+
+ print("DELETION TEST RUN: " + (run+1) + "/" + runs + "\n");
+
+ print("INSERTING INTO BTREE\n");
+ int maxLength = 10;
+ int ins = 10000;
+ byte[][] records = new byte[ins][];
+ int insDone = 0;
+ int[] insDoneCmp = new int[ins];
+ for (int i = 0; i < ins; i++) {
+ String field0 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
+ String field1 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
+
+ byte[] f0 = field0.getBytes();
+ byte[] f1 = field1.getBytes();
+
+ byte[] record = new byte[f0.length + f1.length + 8];
+ ByteBuffer buf = ByteBuffer.wrap(record);
+
+ int start = 0;
+ buf.putInt(start, f0.length);
+ start += 4;
+ System.arraycopy(f0, 0, record, start, f0.length);
+ start += f0.length;
+ buf.putInt(start, f1.length);
+ start += 4;
+ System.arraycopy(f1, 0, record, start, f1.length);
+ start += f1.length;
+
+ records[i] = record;
+
+ if (i % 1000 == 0) {
+ print("INSERTING " + i + ": " + cmp.printRecord(record, 0) + "\n");
+ }
+
+ try {
+ btree.insert(record, leafFrame, interiorFrame, metaFrame);
+ insDone++;
+ } catch (Exception e) {
+ }
+
+ insDoneCmp[i] = insDone;
+ }
+ // btree.printTree();
+ // btree.printStats();
+
+ print("DELETING FROM BTREE\n");
+ int delDone = 0;
+ for (int i = 0; i < ins; i++) {
+
+ if (i % 1000 == 0) {
+ print("DELETING " + i + ": " + cmp.printRecord(records[i], 0) + "\n");
+ }
+
+ try {
+ btree.delete(records[i], leafFrame, interiorFrame, metaFrame);
+ delDone++;
+ } catch (Exception e) {
+ }
+
+ if (insDoneCmp[i] != delDone) {
+ print("INCONSISTENT STATE, ERROR IN DELETION TEST\n");
+ print("INSDONECMP: " + insDoneCmp[i] + " " + delDone + "\n");
+ break;
+ }
+ // btree.printTree();
+ }
+ //btree.printTree(leafFrame, interiorFrame);
+
+ if (insDone != delDone) {
+ print("ERROR! INSDONE: " + insDone + " DELDONE: " + delDone);
+ break;
+ }
+ }
+
+ btree.close();
+
+ bufferCache.close();
+ fileManager.close();
+
+ print("\n");
+ }
+
+ // BULK LOAD TEST
+ // insert 100,000 records in bulk
+ // B-tree has a composite key to "simulate" non-unique index creation
+ // do range search
+ @Test
+ public void test05() throws Exception {
+
+ print("BULK LOAD TEST\n");
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
+ ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+ IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
+ IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
+ IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
+
+ IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
+ IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
+ IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
+
+ int keyLen = 2;
+
+ IFieldAccessor[] fields = new IFieldAccessor[3];
+ fields[0] = new Int32Accessor();
+ fields[1] = new Int32Accessor();
+ fields[2] = new Int32Accessor();
+
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new Int32Comparator();
+ cmps[1] = new Int32Comparator();
+
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ BTree btree = new BTree(bufferCache,
+ interiorFrameFactory,
+ leafFrameFactory,
+ interiorSlotManagerFactory,
+ leafSlotManagerFactory,
+ cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ // generate sorted records
+ int ins = 100000;
+ byte[][] records = new byte[ins][];
+ for (int i = 0; i < ins; i++) {
+ byte[] record = new byte[12];
+
+ AInt32 field0 = new AInt32(i);
+ AInt32 field1 = new AInt32(i);
+ AInt32 field2 = new AInt32(rnd.nextInt() % 100);
+
+ byte[] f0 = field0.toBytes();
+ byte[] f1 = field1.toBytes();
+ byte[] f2 = field2.toBytes();
+
+ System.arraycopy(f0, 0, record, 0, 4);
+ System.arraycopy(f1, 0, record, 4, 4);
+ System.arraycopy(f2, 0, record, 8, 4);
+ records[i] = record;
+ }
+
+ print("BULK LOADING " + ins + " RECORDS\n");
+ long start = System.currentTimeMillis();
+
+ BTree.BulkLoadContext ctx = btree.beginBulkLoad(0.7f, leafFrame, interiorFrame, metaFrame);
+ for (int i = 0; i < ins; i++) {
+ btree.bulkLoadAddRecord(ctx, records[i]);
+ }
+ btree.endBulkLoad(ctx);
+
+ long end = System.currentTimeMillis();
+ long duration = end - start;
+ print("DURATION: " + duration + "\n");
+
+ // range search
+ print("RANGE SEARCH:\n");
+ IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
+
+ AInt32 lowKey = new AInt32(44444);
+ AInt32 highKey = new AInt32(44500);
+
+ IComparator[] searchCmps = new IComparator[1];
+ searchCmps[0] = new Int32Comparator();
+ MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
+
+ RangePredicate rangePred = new RangePredicate(false, lowKey.toBytes(), highKey.toBytes(), searchCmp);
+ btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ byte[] array = rangeCursor.getPage().getBuffer().array();
+ int recOffset = rangeCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ rangeCursor.close();
+ }
+
+ btree.close();
+
+ bufferCache.close();
+ fileManager.close();
+
+ print("\n");
+ }
+
+ // TIME-INTERVAL INTERSECTION DEMO FOR EVENT PEOPLE
+ // demo for Arjun to show easy support of intersection queries on time-intervals
+ @Test
+ public void test06() throws Exception {
+
+ print("TIME-INTERVAL INTERSECTION DEMO\n");
+
+ FileManager fileManager = new FileManager();
+ ICacheMemoryAllocator allocator = new BufferAllocator();
+ IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
+ IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
+
+ File f = new File("/tmp/btreetest.bin");
+ RandomAccessFile raf = new RandomAccessFile(f, "rw");
+ int fileId = 0;
+ FileInfo fi = new FileInfo(fileId, raf);
+ fileManager.registerFile(fi);
+
+ ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
+ ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+ IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
+ IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
+ IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
+
+ IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
+ IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
+ IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
+
+ int keyLen = 2;
+
+ IFieldAccessor[] fields = new IFieldAccessor[3];
+ fields[0] = new Int32Accessor();
+ fields[1] = new Int32Accessor();
+ fields[2] = new Int32Accessor();
+
+ IComparator[] cmps = new IComparator[keyLen];
+ cmps[0] = new Int32Comparator();
+ cmps[1] = new Int32Comparator();
+
+ MultiComparator cmp = new MultiComparator(cmps, fields);
+
+ BTree btree = new BTree(bufferCache,
+ interiorFrameFactory,
+ leafFrameFactory,
+ interiorSlotManagerFactory,
+ leafSlotManagerFactory,
+ cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ long start = System.currentTimeMillis();
+
+ byte[] record = new byte[12];
+
+ int intervalCount = 10;
+ int[][] intervals = new int[intervalCount][2];
+
+ intervals[0][0] = 10;
+ intervals[0][1] = 20;
+
+ intervals[1][0] = 11;
+ intervals[1][1] = 20;
+
+ intervals[2][0] = 12;
+ intervals[2][1] = 20;
+
+ intervals[3][0] = 13;
+ intervals[3][1] = 20;
+
+ intervals[4][0] = 14;
+ intervals[4][1] = 20;
+
+ intervals[5][0] = 20;
+ intervals[5][1] = 30;
+
+ intervals[6][0] = 20;
+ intervals[6][1] = 31;
+
+ intervals[7][0] = 20;
+ intervals[7][1] = 32;
+
+ intervals[8][0] = 20;
+ intervals[8][1] = 33;
+
+ intervals[9][0] = 20;
+ intervals[9][1] = 35;
+
+ // int exceptionCount = 0;
+ for (int i = 0; i < intervalCount; i++) {
+ AInt32 field0 = new AInt32(intervals[i][0]);
+ AInt32 field1 = new AInt32(intervals[i][1]);
+ AInt32 field2 = new AInt32(rnd.nextInt() % 100);
+
+ byte[] f0 = field0.toBytes();
+ byte[] f1 = field1.toBytes();
+ byte[] f2 = field2.toBytes();
+
+ System.arraycopy(f0, 0, record, 0, 4);
+ System.arraycopy(f1, 0, record, 4, 4);
+ System.arraycopy(f2, 0, record, 8, 4);
+
+ print("INSERTING " + i + " : " + field0.getIntegerValue() + " " + field1.getIntegerValue() + "\n");
+
+ try {
+ btree.insert(record, leafFrame, interiorFrame, metaFrame);
+ } catch (Exception e) {
+ // e.printStackTrace();
+ }
+ }
+ // btree.printTree(leafFrame, interiorFrame);
+ // btree.printStats();
+
+ long end = System.currentTimeMillis();
+ long duration = end - start;
+ print("DURATION: " + duration + "\n");
+
+ // try a simple index scan
+
+ print("ORDERED SCAN:\n");
+ IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
+ RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ byte[] array = scanCursor.getPage().getBuffer().array();
+ int recOffset = scanCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ scanCursor.close();
+ }
+
+ // try a range search
+ print("RANGE SEARCH:\n");
+ IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
+
+ AInt32 lowerBound = new AInt32(12);
+ AInt32 upperBound = new AInt32(19);
+ byte[] lbBytes = lowerBound.toBytes();
+ byte[] hbBytes = upperBound.toBytes();
+
+ byte[] lowKey = new byte[8];
+ byte[] highKey = new byte[8];
+
+ System.arraycopy(lbBytes, 0, lowKey, 0, 4);
+ System.arraycopy(lbBytes, 0, lowKey, 4, 4);
+
+ System.arraycopy(hbBytes, 0, highKey, 0, 4);
+ System.arraycopy(hbBytes, 0, highKey, 4, 4);
+
+ IComparator[] searchCmps = new IComparator[2];
+ searchCmps[0] = new Int32Comparator();
+ searchCmps[1] = new Int32Comparator();
+ MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
+
+ print("INDEX RANGE SEARCH ON: " + cmp.printKey(lowKey, 0) + " " + cmp.printKey(highKey, 0) + "\n");
+
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ byte[] array = rangeCursor.getPage().getBuffer().array();
+ int recOffset = rangeCursor.getOffset();
+ String rec = cmp.printRecord(array, recOffset);
+ print(rec + "\n");
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ rangeCursor.close();
+ }
+
+ btree.close();
+
+ bufferCache.close();
+ fileManager.close();
+
+ print("\n");
+ }
+
+ public static String randomString(int length, Random random) {
+ String s = Long.toHexString(Double.doubleToLongBits(random.nextDouble()));
+ StringBuilder strBuilder = new StringBuilder();
+ for (int i = 0; i < s.length() && i < length; i++) {
+ strBuilder.append(s.charAt(Math.abs(random.nextInt()) % s.length()));
+ }
+ return strBuilder.toString();
+ }
+}
\ No newline at end of file