Re: how to build a database from scratch

From: paul c <toledobythesea_at_oohay.ac>
Date: Sun, 03 Dec 2006 02:22:48 GMT
Message-ID: <Yxqch.413169$R63.158626@pd7urf1no>

Murdoc wrote:
> Neo wrote:
>
>

>>>Most relational database systems are based upon Bayer trees.
>>
>>Is this true? If so why doesn't the relational data model mention trees?

>
>
> It doesn't need to. B-Trees are not a part of the relational data model, but are almost
> always used as the internal implementation with the RDMS itself. Index storage is the
> perfect example. If you have a multiple-component index, e.g. field_01, field_02, etc.
> then each field would be stored in a separate layer of the B-Tree.
>
> The top layer would contain a separate 'node' for each unique value for field_01 that
> exists. The second layer would contain, for every unique value of field_01, the
> corresponding unique values for field_01. That is, there could exist two entries in the
> second layer for the value "ABC", but they would be related to different values of
> field_01.
>

I suspect that scenarios that profit from the above are rare with most disk-based conventional products. It is more likely that an optimizer or a dba would choose a "single layer" (to use Murdoc's lingo) for a composite key and separate index(es) for the expected individual "field" accesses, both indexes being combined by a smart optimizer when that is useful. Otherwise, with a multi-layer index for a six attribute index, eg., a six attribute composite key, six indexes must be navigated and the possibility of using a sparse index is also lost.

Still, I think individual indexes for all attributes of any given table/relvar in a mostly memory-based dbms might compete well with the trans-relational idea without paying its up-front organization costs (even though one person more familiar with TRM has told me I was dreaming when I brought it up). This kind of scheme would pay a price if it were to avoid conventional row storage, which would be desireable for storage economy and would also need to be fairly clever about cache misses if it were to exploit modern cpu speeds.

p Received on Sat Dec 02 2006 - 20:22:48 CST