directory-dev mailing list archives

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

    http://www.cs.cmu.edu/%7Esleator/papers/self-adjusting.pdf

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

Thanks,
Alex

On Jan 30, 2008 2:49 AM, Alex Karasulu <akarasulu@apache.org> 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
>

Mime
View raw message