directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex Karasulu" <>
Subject Re: [ApacheDS] Going to need to implement a splay tree
Date Wed, 30 Jan 2008 08:09:20 GMT
Original paper:

Wondering if anyone has an existing Java implementation that is BSD licensed
in mind.


On Jan 30, 2008 2:49 AM, Alex Karasulu <> wrote:

> 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

View raw message