Re: [help] main memory db

The world rejoiced as "Mikito Harakiri" <mikharakiri_at_iahu.com> wrote:
> "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.

A conflicting consideration is that you may want to try to make maximum use of memory, and therefore pack a larger number of elements into each "page/block/basic-quantity-of-allocatable-memory."

After all, efficient use of memory is important if that's the vital resource.

> 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...

There you go...

It's not evident to me what the vital _theoretical_ difference between T-trees and B-trees is. With the intentional caveat that I'm quite happy to gloss over the differences between B-trees and B*-trees and B+-trees; they have marginally different characteristics, but not to such a dramatic extent that this masks the sweeping similarities.

-- 
"cbbrowne","_at_","acm.org"
http://www.ntlug.org/~cbbrowne/
"Linux is a very complete, sophisticated OS" - Paul Maritz of MICROS~1