Background:

ApacheDS used JDBM a B+Tree implementation in it's default partition implementation. JDBM does not allow duplicate keys (same key with many values) and so we abstract this using the Table interface.  Tables support duplicate keys.  So to allow this JdbmTable which implements this interface uses a TreeSet or something called a BTreeRedirect to manage the values of duplicate keys.  When some threshold of values is reached like say 50 for the same key, the JDBM table switches from using a TreeSet to using a BTreeRedirect. A BTreeRedirect is a pointer to another BTree in the same db file. The BTree pointed to contains the values of the duplicate key as it's keys.

Problem:

I was looking into the new Cursor interface and came to the realization that we can no longer use TreeSets efficiently or properly for that matter.  To build a Cursor on this we would have to be able to traverse up and down as the user of the Cursor desired and there's simply no way to do this. 

Proposal:

Implement an in memory linked splay tree with splay Cursor using the links for traversal.  Splay trees are idea for recurring lookups which would be the case for us.  Furthermore splay trees are great for caches.  Splay trees reposition the most frequently accessed nodes close to the root of the tree making access times faster.  They perform poorly though when inserting in an ordered fashion. I think this is acceptable for our use of this data structure for a TreeSet (which uses a red-black tree) and ideal for use in devising a better entry cache higher up in the server.

Thoughts?

Alex