You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Kiran Ayyagari <ay...@gmail.com> on 2008/02/11 21:17:24 UTC
splay tree for duplicate key cursor implementation
hi Guys,
During a discussion with Alex it was understood that implementing a
linked
splay tree for duplicate key cursor may not result in any
performance gain.
When we perform lookups on the splay tree (kept in memory after
fetching the
serialized version ) its structure changes due to splaying.
This changed structure will be discarded without writing back to the
disk to
eliminate the write cost. This way it will not help us in any form
to get the amortized
time benefits.
So we are thinking of using some kind of btree for the actual
implementation.
Thoughts?
- Kiran Ayyagari
Re: splay tree for duplicate key cursor implementation
Posted by Alex Karasulu <ak...@apache.org>.
This is excellent news. Thanks for following up. I guess now we just keep
a close eye on their releases and start using the library for a new backend
implementation.
Thanks!!
Alex
On Thu, Feb 21, 2008 at 4:58 AM, Jörg Henne <j....@levigo.de> wrote:
> Alex,
>
>
> Alex Karasulu wrote:
>
> On Feb 12, 2008 4:06 AM, Ersin Er <er...@gmail.com> wrote:
>
> > On Feb 12, 2008 11:04 AM, Jörg Henne <j....@levigo.de> wrote:
> > > ok, btw, what I wanted to mention: there seems to be a very promising
> > > (albeit beta) implementation of B-Link trees at
> > > http://code.google.com/p/simpledbm/ with excellent documentation.
> > >
> > > Unfortunately, it has the wrong license...
> >
> > We can just ask for a license change ;-)
> >
>
> Yes yes can someone explore this option? Ersin, Jörg do you think you can
> approach them?
>
> good news: I did approach him and he is open to releasing his project
> under a license what would allow us to use it. In fact, he is working on
> making SimpleDBM an optional storage backend for Derby, see
> https://issues.apache.org/jira/browse/DERBY-3351 and
> https://issues.apache.org/jira/browse/DERBY-3405.<https://issues.apache.org/jira/browse/DERBY-3405>
>
> He even recommended we use Derby itself, but the discussion in the issues
> above indicates that this would not be a easy route to go: the tight
> coupling of Derby's storage layer would probable prevent us from using it as
> a backend engine just like it makes it hard for him to use SimpleDBM as a
> Derby backend.
>
> So, in conclusion, I think that SimpleDBM is an option we should
> definitely keep an eye on.
>
> Joerg Henne
>
Re: splay tree for duplicate key cursor implementation
Posted by Alex Karasulu <ak...@apache.org>.
On Feb 12, 2008 4:06 AM, Ersin Er <er...@gmail.com> wrote:
> On Feb 12, 2008 11:04 AM, Jörg Henne <j....@levigo.de> wrote:
> > ok, btw, what I wanted to mention: there seems to be a very promising
> > (albeit beta) implementation of B-Link trees at
> > http://code.google.com/p/simpledbm/ with excellent documentation.
> >
> > Unfortunately, it has the wrong license...
>
> We can just ask for a license change ;-)
>
Yes yes can someone explore this option? Ersin, Jörg do you think you can
approach them?
Thanks,
Alex
Re: splay tree for duplicate key cursor implementation
Posted by Ersin Er <er...@gmail.com>.
On Feb 12, 2008 11:04 AM, Jörg Henne <j....@levigo.de> wrote:
> Jörg Henne schrieb:
> > interesting indeed. Thanks for the pointer! The B-Link concurrency
> > management seems to focus on ARIES-style locking which I am not too
> > fond of (having had just last week a bad, bad nightmare of deadlocks
> > due to lock escalation in DB2) but for low-update applications like
> > directories that's probably a non-issue.
> ok, btw, what I wanted to mention: there seems to be a very promising
> (albeit beta) implementation of B-Link trees at
> http://code.google.com/p/simpledbm/ with excellent documentation.
>
> Unfortunately, it has the wrong license...
We can just ask for a license change ;-)
> Joerg Henne
>
>
--
Ersin Er
Re: splay tree for duplicate key cursor implementation
Posted by Jörg Henne <j....@levigo.de>.
Jörg Henne schrieb:
> interesting indeed. Thanks for the pointer! The B-Link concurrency
> management seems to focus on ARIES-style locking which I am not too
> fond of (having had just last week a bad, bad nightmare of deadlocks
> due to lock escalation in DB2) but for low-update applications like
> directories that's probably a non-issue.
ok, btw, what I wanted to mention: there seems to be a very promising
(albeit beta) implementation of B-Link trees at
http://code.google.com/p/simpledbm/ with excellent documentation.
Unfortunately, it has the wrong license...
Joerg Henne
Re: splay tree for duplicate key cursor implementation
Posted by Jörg Henne <j....@levigo.de>.
Howard Chu schrieb:
> Also look into B-link trees. They have very nice locking properties
> (that I wish the BerkeleyDB guys would implement for us. Sigh.)
very interesting indeed. Thanks for the pointer! The B-Link concurrency
management seems to focus on ARIES-style locking which I am not too fond
of (having had just last week a bad, bad nightmare of deadlocks due to
lock escalation in DB2) but for low-update applications like directories
that's probably a non-issue.
Joerg Henne
Re: splay tree for duplicate key cursor implementation
Posted by Howard Chu <hy...@symas.com>.
Jörg Henne wrote:
> Kiran Ayyagari schrieb:
>> So we are thinking of using some kind of btree for the actual
>> implementation.
> "common database wisdom" is to use a B+-Tree for this kind of
> application. A B+-Tree has all its keys in the bottom-most node-level.
> Furthermore, it usually has bottom-level links between adjacent nodes.
> This approach results in several advantages
> - the tree nodes map nicely to disk blocks
> - (read) accesses require an exactly known number of disk accesses
> - the top-few node-levels can be easily kept in a buffer-cache (this
> happens almost automatically if one uses an LRU-approach for retaining
> nodes in the cache)
> - since all keys/data is guaranteed to be present in the bottom-most
> node-level and adjacent nodes are linked, range retrievals become very
> efficient, because the retrieval doesn't have to percolate upwards in
> order to traverse the tree.
Also look into B-link trees. They have very nice locking properties (that I
wish the BerkeleyDB guys would implement for us. Sigh.)
--
-- Howard Chu
Chief Architect, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
Re: splay tree for duplicate key cursor implementation
Posted by Jörg Henne <j....@levigo.de>.
Kiran Ayyagari schrieb:
> So we are thinking of using some kind of btree for the actual
> implementation.
"common database wisdom" is to use a B+-Tree for this kind of
application. A B+-Tree has all its keys in the bottom-most node-level.
Furthermore, it usually has bottom-level links between adjacent nodes.
This approach results in several advantages
- the tree nodes map nicely to disk blocks
- (read) accesses require an exactly known number of disk accesses
- the top-few node-levels can be easily kept in a buffer-cache (this
happens almost automatically if one uses an LRU-approach for retaining
nodes in the cache)
- since all keys/data is guaranteed to be present in the bottom-most
node-level and adjacent nodes are linked, range retrievals become very
efficient, because the retrieval doesn't have to percolate upwards in
order to traverse the tree.
Joerg Henne
Re: splay tree for duplicate key cursor implementation
Posted by Alex Karasulu <ak...@apache.org>.
Thanks Kiran for posting our off line conversations here.
Alex
On Feb 11, 2008 3:17 PM, Kiran Ayyagari <ay...@gmail.com> wrote:
> hi Guys,
>
> During a discussion with Alex it was understood that implementing a
> linked
> splay tree for duplicate key cursor may not result in any
> performance gain.
>
> When we perform lookups on the splay tree (kept in memory after
> fetching the
> serialized version ) its structure changes due to splaying.
>
> This changed structure will be discarded without writing back to the
> disk to
> eliminate the write cost. This way it will not help us in any form
> to get the amortized
> time benefits.
>
> So we are thinking of using some kind of btree for the actual
> implementation.
>
> Thoughts?
>
> - Kiran Ayyagari
>
>