Re: [help] main memory db

"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message <news:k18zb.16$2A3.176_at_news.oracle.com>...

> "Christopher Browne" <cbbrowne_at_acm.org> wrote in message
> news:bqir8m$22r2d9$1_at_ID-125932.news.uni-berlin.de...
> > Well, there's the _possibility_ (I haven't seen good papers on it, so
> > I rank it only as "possible") that there would be substantially
> > different algorithms that you would use if you know you'll never be
> > hitting disk.
> >
> > <http://kdb.snu.ac.kr/~tsangbi/papers/TTree86.html>
>
> The optimal main memory index should meet 2 criteria:
> 1. Balance Constraint
> 2. Minumum number of binary decisions on the path from the root to the leaf.
> Here we must take into account _all_ bunary decisions, including those what
> happens when traversing a linear list of slots at each the B-Tree node .
>
> It is easy to see that B-Tree of the lowest degree (n=3?) meets these
> criteria. This goal is the opposite to traditional disk database
> implementation, where node degree is kept high to minimize disk access.
>
> Surprisingly, paper insists that keeping degree high is a good idea:
>
> <quote>
> Because a T node contains many elements, the T Tree has the good update and
> storage characteristics of the B Tree.
> </quote>
>
> Which casts a doubt that authors really understand what they are doing...

If the elements in a T-node are kept in order, use Vyssotsky's binary search. When designing the T-node layout, try to make it fit within the CPU level one data cache. This ought to be better than chasing binary tree node pointers all over slower RAM, which will cause the CPU to stall while RAM is copied to cache! While RAM is much faster than disk, level two cache is faster than RAM, and level one cache on the CPU is typically much faster than even the level two cache.

--
Joe Foster <mailto:jlfoster%40znet.com>  DC8s in Spaace: <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above        They're   coming  to
because  my cats have  apparently  learned to type.        take me away, ha ha!