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