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 Thu, 31 Jan 2008 06:58:42 GMT
Thanks Ole.

Alex

On Jan 30, 2008 10:49 AM, Ole Ersoy <ole.ersoy@gmail.com> wrote:

> Hey Alex,
>
> You probably saw this (It says public domain at the top):
> http://www.link.cs.cmu.edu/link/ftp-site/splaying/SplayTree.java
>
> I also came across this (Has splay tree implementation in the Javadoc):
> http://www.cs.williams.edu/~bailey/JavaStructures/Welcome.html<http://www.cs.williams.edu/%7Ebailey/JavaStructures/Welcome.html>
> http://www.cs.williams.edu/~bailey/JavaStructures/doc/structure/index.html<http://www.cs.williams.edu/%7Ebailey/JavaStructures/doc/structure/index.html>
>
> Which looks like it's code to go along with the free book.  He says the
> code is free for instructors and students, but I'm betting he'd be cool with
> Apache as well.
>
> Cheers,
> - Ole
>
>
>
>
> Alex Karasulu wrote:
> > 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
> > <mailto: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