Re: [help] main memory db

"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... Received on Tue Dec 02 2003 - 22:58:05 CET