Re: [help] main memory db
Date: 2 Dec 2003 22:52:26 GMT
The world rejoiced as "Mikito Harakiri" <mikharakiri_at_iahu.com> wrote:
> "Christopher Browne" <cbbrowne_at_acm.org> wrote in message
>> 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:
> Because a T node contains many elements, the T Tree has the good update and
> storage characteristics of the B Tree.
> 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~1Received on Tue Dec 02 2003 - 23:52:26 CET