Terry Heidelberg
2006-Nov-17 14:49 UTC
[Lustre-devel] algorithms for efficient extent lock comparisons
Yang Liu <liu24@llnl.gov> wrote:> I think I see the problem. Such an query would not return intervals that > are completely contained within [A,B] (i.e. all [C,D] where A<C<D<B). > > -yang >Yang Liu wrote:> Have you guys looked at relational interval trees? > http://www.dbs.informatik.uni-muenchen.de/Forschung/CAD/presentations/RI-Tree.pdf > > > -yang
Andreas Dilger
2006-Nov-18 05:10 UTC
[Lustre-devel] algorithms for efficient extent lock comparisons
On Nov 17, 2006 13:48 -0800, Terry Heidelberg wrote:> Yang Liu <liu24@llnl.gov> wrote: > >I think I see the problem. Such an query would not return intervals that > >are completely contained within [A,B] (i.e. all [C,D] where A<C<D<B). > > Yang Liu wrote: > >Have you guys looked at relational interval trees? > >http://www.dbs.informatik.uni-muenchen.de/Forschung/CAD/presentations/RI-Tree.pdfI stopped reading the paper after the title reported "Patent pending"... Zach pointed me at "interval trees" on Wikipedia which seem like the right thing. They are like interval skip lists, but with a clever twist to handle the case where intervals wholly overlap as Yang Liu suggests. It might make sense to keep some special values out of the tree, like [0,EOF] locks, since we know they will match every interval. Cheers, Andreas -- Andreas Dilger Principal Software Engineer Cluster File Systems, Inc.