Re: A DBMS implementation Question

From: Larry Coon <>
Date: Fri, 28 Feb 2003 11:21:18 -0800
Message-ID: <>

owen wrote:

> Some small rational dbms use B tree for indexing.

I wouldn't limit it to "some small."

> I found a problem in
> the condition that the key for the table is a multiple key.

Actually, as I read through the rest of your post, your problem doesn't really pertain to composite keys or even keys in general. Nor are they specific to any implementation of indexing, such as B-tree variants.

> For example
> , there is a table which is denoted as emp(no, age, name), and (no +
> age) is the key for indexing.

I'd normally question whether (no, age) is even a candidate key, but I'll leave it alone for your example.

> In the B Tree, the values of "no" and "age"
> are transfered to String and merge together,

That'd be an implementation issue. And it might be a poor way to do it, since any lookup would incur a lot of overhead in string conversion.

> such as the key value of
> (1, 20, "abc") is "00010020",and the the B Tree of the table is
> established by the sequence of the key.
> Now , I have a problem , if I want to query all the people whose
> age are more than 20 , which is described as "select * from emp
> where age > 20", i can't use b tree for indexing,

No, for that query, then THAT PARTICULAR index is of little use.

> if i use , the
> number of records that i must scan may be very large, how to sovle
> the problem.
> The problem can be expressed as "how to deal with scaning the table
> using non-primary key or non-key field".

The problem is really, "what column(s) are good candidates for indexing?" The primary key is a given, since a PK must be unique and we need an efficient way of enforcing uniqueness. But nothing prevents you from adding more indexes. If you perform a lot of queries such as the one above, then the age column might be a good candidate for its own index (with a possible argument against being the amount of selectivity that index would provide -- if the table contained something like voter registration where the vast majority of rows had age > 20, then the index might be ignored in favor of a table scan in any event).

Larry Coon
University of California
and Received on Fri Feb 28 2003 - 20:21:18 CET

Original text of this message