Virtual Machinery logoBTree logo
BTree Tips and Tricks
Home BTree Guide BTree Performance Sample Applications BTree Roadmap Other Products

Click here to see details of our JHawk Java Metrics product

*** NEW *** Android Demo for Android 2.3 and above and How to run the J2ME Demo in Java ME SDK 3.0 - Click Here ***

Tips and tricks for using BTrees

BTrees are the programmers secret weapon. More efficient than databases you can think of them as persistent hashmaps. They are one of the oldest structured storage options and they are at the heart of many applications that we use daily - databases, file systems and operating systems. Here we present some ways to make the best use of your Virtual Machinery BTree implementation but many of these can be applied to any BTree implementation. There is also some more general information on our BTree FAQ page.

How do I make sure numeric keys are sorted in order?

Most people think of Btrees as having string indices. This gives rise to a problem where you have numeric indices (say account numbers). Lets say you have the indices 1,2,3,4,5,6,7,8,9,10,11. The Btree will sort these in the order 1,10,11,2,3,4,5,6,7,8,9 - which is their string order. You could make all your keys the same length by padding them with leading zeroes but this is laborious. In Virtual Machinery's BTree implementation the indices can be any array of bytes so you can just translate each numeric index to a byte array. The following code illustrates the point and the output is shown afterwards-


public class TestNumericIndices {
	
	public static void main(String[] args) {
		BTreeInterface b;
		try {
			
			System.out.println ("Test Using standard string");
			b = BTree.createNewTree("TESTING");
			for (int i=1; i<12; i++) b.put(""+i, "Record"+i);
			BTreeRecordInterface[] next= {new BTreeRecord("")};
			while (next[0] != null) {
				next = b.getNext();
				if (next[1] != null) System.out.println(next[0]+" : "+next[1]);
			}
			b.closeBTree();
		
			System.out.println ("Test Using bytes");
			b = BTree.createNewTree("TESTING");
			for (int i=1; i<12; i++) b.put(new BTreeRecord(convertToByteArray(i)), new BTreeRecord("Record"+i));
			next[0]= new BTreeRecord("");
			while (next[0] != null) {
				next = b.getNext();
				if (next[1] != null) System.out.println(convertToInt(next[0].getValue())+" : "+next[1]);
			}
			b.closeBTree();
		} catch (BTreeException e) {
			e.printStackTrace();
		}
		
	}
	
	public static  byte[] convertToByteArray(int aNumber) {
        return new byte[] {
                (byte)(aNumber >>> 24),
                (byte)(aNumber >>> 16),
                (byte)(aNumber >>> 8),
                (byte)aNumber};
	}
	
	public static int convertToInt(byte [] bytes) {
        return (bytes[0] << 24)
                + ((bytes[1] & 0xFF) << 16)
                + ((bytes[2] & 0xFF) << 8)
                + (bytes[3] & 0xFF);
	}

}
 

The output displayed is as follows -


Test Using standard string
1 : Record1
10 : Record10
11 : Record11
2 : Record2
3 : Record3
4 : Record4
5 : Record5
6 : Record6
7 : Record7
8 : Record8
9 : Record9

Test Using bytes
1::Record1
2::Record2
3::Record3
4::Record4
5::Record5
6::Record6
7::Record7
8::Record8
9::Record9
10::Record10
11::Record11

 

If I was using a Database I would have a lot of tables - what do I do with a BTree?

There are a number of possible approaches. The simplest is to have one table per btree. So if you had two tables - Accounts and Transactions you can open two btrees one called 'Accounts' and the other called 'Transactions'. This means that when you want to access the data relating to the accounts you can use the 'Accounts' BTree and when you want to access the transactions you use the 'Transactions' BTree.

Another option is to put all your Tables in the one BTree. In this case you use different keys to access the Transactions or Accounts. So you might use ACC as the prefix for all your account records and TRN for all your transaction records.

Lets look at these two approaches using an example which creates an account then adds a transaction which updates the balance of the account. We will describe the Account and Transaction objects in the next example so don't worry too much about them for the moment. So here is the code for each of our implementations. -

	
	public static void main(String[] args) {
		BTreeInterface accounts = null;
		BTreeInterface transactions = null;
		BTreeInterface both = null;
		try {
			
			//Example using separate BTrees
			accounts = BTree.createNewTree("ACCOUNTS");
			transactions = BTree.createNewTree("TRANSACTIONS");
			//Create a new account with a balance of zero
			Account account1 = new Account("FirstAccount",1,0); 
			accounts.put("1", account1.toString());
			//Create a transaction for 10 and add 10 to the balance
			//Use a transaction so mark commit as false
			Transaction transaction1 = new Transaction("1",1,10);
			account1.updateBalance(10);
			transactions.put("1",transaction1.toString(),false);
			accounts.put("1", account1.toString(),false);
			transactions.commit();
			accounts.commit();
			accounts.closeBTree();
			transactions.closeBTree();
		} catch (BTreeException e) {
			e.printStackTrace();
			if (accounts != null) accounts.rollback();
			if (transactions != null) transactions.rollback();
		}
		try {			
			//Example using the same Btree
			both = BTree.createNewTree("BOTH");
			//Create a new account with a balance of zero
			Account account2 = new Account("FirstAccount",1,0); 
			both.put("ACC_1", account2.toString());
			//Create a transaction for 10 and add 10 to the balance
			//Use a transaction so mark commit as false
			Transaction transaction2 = new Transaction("1",1,10);
			account2.updateBalance(10);
			both.put("TRN_1",transaction2.toString(),false);
			both.put("ACC_1", account2.toString(),false);
			both.commit();
			both.closeBTree();
		} catch (BTreeException e) {
			e.printStackTrace();
			if (both != null) both.rollback();
		}
		
	} 

There is a benefit to taking the 'both' approach in that the commit does not have to span across two tables as it does in the 'separate tables' approach. A good compromise between the two different approaches is to keep data that belongs together (or is updated together) in the same table.

If I was using a Database I would have columns in my tables - what do I do with a BTree?

BTrees don't have the concepts of columns. A single record is held for each index. There are a number of ways to overcome this. One is to use a sub-index for each field. In the case of the accounts we could do something like this -

	Account account1 = new Account(1,"First Account",0);
	both.put("ACC_1_Name",account1.getName());
	both.put("ACC_1_Number",account1.getNumber()+"");
	both.put("ACC_1_Balance",account1.getBalance()+"");

This is quite long winded though and a better approach is to store all the data as a record using a field separator. In this case we've used '^' as its an easy to see character and it doesn't get used frequently in text. Remember though that you cannot allow any field to contain this character otherwise your data will be corrupted so you should choose carefully. If you look at the code for the Account class below you will see how this works in practice. The Transaction class that we implemented above works in a similar fashion.


public class Account {
	String name;
	int balance=0;
	int number =0;
	
	public Account(String aName,int aNum, int aBalance) {
		name = aName;
		number = aNum;
		balance = aBalance;
	}
	
	public void updateBalance(int anAmount) {
		balance += anAmount;
	}
	
	public void fromString(String aString) {
		String[] temp = aString.split("^");
		number = Integer.parseInt(temp[0]);
		name = temp[1];
		balance = Integer.parseInt(temp[2]);
	}
	
	public String toString() {
		return number+"^"+name+"^"+balance;
	}

	public String getName() {
		return name;
	}

	public int getBalance() {
		return balance;
	}

	public int getNumber() {
		return number;
	}
}

I want to access my data in lots of different ways how do I do this with a BTree?

A good example of this would be where you wanted to get all the transactions for a particular account. In a standard database you would set up a foreign key on the transaction table which linked to the account table. Under the covers this creates an index table that the database manages for you. In a BTree you have to maintain this yourself so lets look at the code that we need to do this -

	
	public static void main(String[] args) {
		BTreeInterface both = null;
		try {
			both = BTree.createNewTree("BOTH");
			//Create a new account with a balance of zero
			Account account2 = new Account("FirstAccount",1,0); 
			both.put("ACC_1", account2.toString());
			//Create a transaction for 10 and add 10 to the balance
			//Use a transaction so mark commit as false
			Transaction transaction3 = new Transaction("3",1,10);
			account2.updateBalance(10);
			both.put("TRN_3",transaction3.toString(),false);
			both.put("ACC_1", account2.toString(),false);
			// Update the Index
			both.put("ACC_TRN_IX_1_3","3",false);
			both.commit();
			both.closeBTree();
		} catch (BTreeException e) {
			e.printStackTrace();
			if (both != null) both.rollback();
		}
		
	} 

All we had to do here was add a line to create an index based on the account number and the transaction number that contains the transaction number. So if we want to find all the transactions for an account we just need to run the following code -

	
	String[] allAccount1 = both.getIndicesStartingWith("ACC_TRN_IX_1",100);
	for (int i=0; i<allAccount1.length; i++) {
		String trn = both.get(allAccount1[i]);
		Transaction aTransForAccount1 = Transaction.fromString(both.get(trn));
	}
While this approach isn't too onerous for a small number of indices if you feel that you need a lot of these indices you might be better to use a database.

I want to store data that is bigger than the maximum 64k page size how do I do this with Virtual Machinery's BTree?

There is more than one possibility here - the easiest one is to put the large data object in a file and just store the file path in the BTree. Sometimes you don't want to do this - so the other approach is to break the obejct into smaller pieces and reassemble it when you fetch it. This might sound inefficient but it in fact it's not generally noticeable compared to putting the object out to file since the file system generally does the same job as it reads file sectors in chunks. If you have a cached Btree then there is a possibility that your data will be in cache and the operation may actually be faster. So here's some code to break and reassemble a large binary object (in this case a Bitmap on the Android platform) -

	
public class BitmapLibrary {
	
	//For the moment we'll use a hashtable then we can convert to BTree
	public static BTreeInterface library = null;
	{
		try {
			BTree.createNewTree("LIBRARY");
		} catch (BTreeException e) {
			e.printStackTrace();
		}
	}
	public static final int MAX_LENGTH = 48000;
   
	
	public static void saveImage(Bitmap aBitmap, String index) {
		int ht = aBitmap.getHeight();
	    	int wid = aBitmap.getWidth();
    		String config = aBitmap.getConfig().name();
    		byte[] pixels = new byte[wid*ht];
    		aBitmap.getPixels(pixels, 0, wid, 0, 0, wid, ht);
		int numRecords = pixels.length/MAX_LENGTH+1;
		String baseRecord=numRecords+"^"+pixels.length+"^"+ht+"^"+wid+"^"+config;
		library.put(index,baseRecord);
		int start=0;
		int left = 0;
		for (int i=0;i

Click here to buy Virtual Machinerys BTree implementation online.

 
 
 

Contact Us

© 2017 Virtual Machinery   All Rights Reserved.
Android is a trademark of Google Inc. Use of this trademark is subject to Google Permissions .

Portions of this page are reproduced from work created and shared by Google and used according to terms described in the Creative Commons 2.5 Attribution License.

Some of the icons in this page are generously provided by MySiteMyWay