directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex Karasulu" <akaras...@apache.org>
Subject [ApacheDS] Going to need to implement a splay tree
Date Wed, 30 Jan 2008 07:49:41 GMT
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