On B+ Trees and Java

Before beginning this project, required reading is page 343 in your book, which begins section 10.5 "B-Trees". I now assume you've read that page;) The thing that makes B Trees of any variety so special is the internal node, which is sized to be about one page size (or disk block) of contiguous memory. This way if a page fault does occur when accessing a node you are guaranteed to be able to perform several searches in a row without causing any more faults. *note to self- how many are familiar with databases?:) * For those not familiar with virtual memory, it may be helpful to think in terms of a database. The index for a large database may easily exceed the physical memory of the machine running the database. For this reason a database manager can only keep a fraction of the index in memory at any given time. To fascilitate this, the manager works with a block size, say 4kbytes, where any 4k region of logical memory is either entirely in physical memory, or entirely swapped out to disk. If an index search needs to access a node that is not in memory, the manager must choose an existing block in physical memory to swap to disk, then copy the new block in its place. Then the search can proceed. This operation is extremely slow, so you would like to do it as little as possible. With a B+ Tree index, every time one of these faults occurs an entire node gets put into physical memory and all searches within that node can occur without fear of another fault. In a structure like a BST there are no such guarantee. There is no guarantee of memory locality even between a single node and its children, so every single comparison can conceivably cause another fault. In the worst case thrashing can occur, where, for instance, the tree gets so deep with nodes located in random portions of memory that by the time a leaf is reached the root of the tree has been pushed out of memory. In this worst case scenerio almost every comparison would require another fault, easily making simple accesses tens of thousands of times slower. Here are some numbers I pulled off the web, the relevant comparison is "hit time" versus "miss penalty":

      from: http://www.cp.eng.chula.ac.th/faculty/pjw/teaching/ca/vm.htm

      Typical range of parameters for virtual memory 
      block (page) size          512-8192 bytes 
      hit time                   1-10 clock cycles 
      miss penalty               100,000-600,000 clocks 
      (access time)              (100,000-500,000 clocks) 
      (transfer time)            (10,000-100,000 clocks) 
      miss rate                  0.00001% - 0.001% 
\begin{end}


      All of that said, can you see the problem with a java B+ Tree?  What's an internal
      node supposed to look like?

\begin{verbatim}
    class Node
      {
      Object key[];
      Node children[];
      int filled;
      Node(int size)
        {
        filled=0;
        key = new Object[size];
        children = new Node[size];
        }
      }

I hope it's obvious that the above implementation will not at all do what a B+ Tree node is supposed to do. Sure, you can build a structure that looks like a B+ Tree (and you will), but a node has absolutely no internal memory locality. The keys, in particular, come and go at essentially random times in the lifetime of the structure. There's no guarantee that two consectutive keys aren't physically located on opposite sides of the heap. So, what to do. An option is to have an array of characters/bytes/ints to contain the keys- but 1. this limits the B+ tree to using only key types that can be represented as chars/bytes/ints/etc, and 2., there are no functions in java the let you do comparisons on fields of base types. There's no character based string library, for instance. So you would have to either write a character based comparison library specific to a single key type, or instantiate a new key object for every single comparison. And that would just be obsenely slow. Those who miss C++ will know that the problem of a generic B+ tree can be very cleanly solved with templates. But oh well. The algorithms will all be the same, and if you ever want to use your own C/C++ B+ trees for any real applications it should not be a difficult rewrite. Anyway, I've come up with I think a fair compromise for java, based on the idea that objects allocated consecutively are likely to have good memory locality. You will still have an array of keys, but the key type must be 'assignable'. That is, the contents of one key must be able to be copied into another key without changing the memory in that key. Now you'll have:

    class Node
      {
      BKey key[];
      Node children[];
      int filled;
      Node(int size)
        {
        filled=0;
        key = new Object[size];
        children = new Node[size];
        for(int i=0;i<size;i++)
          key[i]=BKey.newKey(); //static method returning a full sized key 
        }
      }

    class BKey
      {
      static BKey newKey();
      void assign(BKey other);
      }

Notice the line key[i]=BKey.newKey(); This is necessary since the B+ Tree won't know what the object type actually is (another advantage of templates). The newKey function will have to build an entire BKey object whose memory will never change. Then, when the B+ tree is actually in use whenever a key is added to a node the assign function is used to overwrite the memory of an existing key array entry. With this trick we should at least be able to get some use of memory locality out of java. I've decidided that you will actually implement two completely endependant B+ tree classes. One will be based on just pointer reassignment for a node's keys. The other will use the trick above to try and preserve memory locality. My advice would be to write the code one way, and then before submitting do the few modifications needed to get the other way working. You could easily have a common base class for the two B+ trees- any functions that don't require reassigning internal node keys would not be affected. In this way we can see what the performance difference is when trying very large data sets. Should be fun eh. FYI I will have to have some code posted to specify your B+ tree and the key type. I'm not set on the actual implementation. We may have a class like 'Comparator' called 'Assigner' or something like that, along with a factory class for building empty keys. As I said, my advice is that you first implement the B+ without such considerations- just using naive pointer assignment inside your nodes, and then fix it all up when you're done;) And yes, your B+ tree *will* implement just as much of the sortedmap interface as your Skiplists had to. **note- if you've read this again you'll note this goal has been changed- see the newsgroup and the USE_HAPPY_FUN_BP() command.

Web Accessibility