Re: B-Tree's and internal DBMS implementations

John,

  I can only say what Microsoft SQL Server does:

If the table has a clustered index, that index is in effect the table, a B-tree with
the entire row at the leaf level, which is linked as a doubly-linked list. The
interior nodes form the clustered index key roadmap.

Whether or not there is a clustered index, the non-clustered indexes are stored as
B-trees as well, with the index keys in the interior nodes. If there is a clustered index,
the leaves of the non-clustered indexes contain the clustered index key.  If there is not,
the leaves contain a reference to the logical disk page and position of a row.

If the clustered index is not unique, a uniquifier is added, but it is not accessible
by the user, and if there are multiple rows in the table for a given non-clustered
index key, there is a leaf node in the non-clustered index for each matching row.

LIKE on a indexed column can use the index if it is of the form LIKE 'prefix%' ,
but LIKE '%substring%' cannot. Of course the query optimizer refers to statistics
about the distribution of values in the table to determine how to execute the query,
and a linear search might take place when a large enough number of rows is expected to meet the query search condition.

I assume you mean "3 trees, one for each of the indexes," not "3 trees for each
index." With that correction, that's correct for SQL Server, in any case.

Steve Kass
Drew University

John wrote:

>Hi all.
>
>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? I assume a relation that
>has 3 indexes would have 3 corresponding B-trees for each of the indexes?
>
>How does the B-Tree deal with the LIKE clause, does that then cause a linear
>search through the tree?
>
>Thanks, Jon
>
>
>
>
Received on Tue Dec 31 2002 - 04:51:18 CET