Re: [help] main memory db

From: Christopher Browne <>
Date: 2 Dec 2003 22:52:26 GMT
Message-ID: <bqj539$24ard4$>

The world rejoiced as "Mikito Harakiri" <> wrote:
> "Christopher Browne" <> wrote in message
> news:bqir8m$22r2d9$
>> 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.
>> <>
> 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.

"Linux is a very complete, sophisticated OS" - Paul Maritz of MICROS~1
Received on Tue Dec 02 2003 - 23:52:26 CET

Original text of this message