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