Re: B-Tree's and internal DBMS implementations

From: Jan Mikkelsen <janm_at_godzilla.zeta.org.au>
Date: Tue, 31 Dec 2002 09:45:58 GMT
Message-ID: <qHdQ9.489$3q3.19656@nasal.pacific.net.au>

John <JonJones(NOSPAM)@hotmail.com> wrote:
>I'am somewhat curious about the B-tree algorithms and how RDBMS us them
>successfully. My question is, what is stored at the leaf level? is it memory
>addresses for the set that matches a point query?

The leaf contains the data that goes with the key. Typically, that will be a pointer to the matching record, although it could be some or all of the record.

>I assume a relation that
>has 3 indexes would have 3 corresponding B-trees for each of the indexes?

A table with three indexes typically has three b-trees in total.

>How does the B-Tree deal with the LIKE clause, does that then cause a linear
>search through the tree?

It depends on whether the prefix is given in the LIKE clause. If the prefix isn't given then the b-tree isn't much use.

If you are interested in more detail, the best book to start with is:

"Transaction Processing: Concepts and Techniques" by Gray & Reuter, and then follow the references. The book "File Structures" is also useful.

Regards,

Jan Mikkelsen
janm_at_transactionware.com Received on Tue Dec 31 2002 - 03:45:58 CST