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 <[EMAIL PROTECTED]> 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
>
