Thanks Ole. Alex
On Jan 30, 2008 10:49 AM, Ole Ersoy <[EMAIL PROTECTED]> 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 <[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 > > > > >
