directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ole Ersoy <ole.er...@gmail.com>
Subject Re: [ApacheDS] Going to need to implement a splay tree
Date Wed, 30 Jan 2008 15:49:27 GMT
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/~bailey/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