B Tree Structure for Composite Index

saurabh39 · Posted: Sat Dec 05, 2009 1:42 pm

Hi All,

Recently I was reading a article on B Tree structure for a index. The article was dealing with a case where index is defined on one column. I want to know what will the B Tree structure look like, if we have say index on 4 cloumn and in which case the DB2 will have matching index scan or non matching.

Any pointers to article on composite index?

mtaylor · Posted: Sat Dec 05, 2009 7:20 pm

It's not hard to imagine that in each non leaf node, where there was a single value indicating the max value in the associated leaf/node, there are four values for each of the four columns and a comparison function that compares each of the four values on some lexographical ordering based on ascending/desending.

But google doesn't readily return any useful links and I've not taken a database implementation course so that's just speculation.

PeterHolland · Posted: Sat Dec 05, 2009 7:37 pm

Google on "composite index" and btree will give some information
to think about.

dick scherrer · Posted: Sat Dec 05, 2009 10:56 pm

Hello,

Possibly an oversimplification, but you might consider a composite index as an index_value rather than multiple columns values.

We (people rather than the machines) are aided by seeing the "pieces". The system doesn't need them really.

The values used in the btree are the index_value. I believe if you look at the article again substituting the index_value for the "one column" you will have what you are looking for.

And i may have misunderstood the question. . .

sushanth bobby · Posted: Mon Dec 07, 2009 2:08 pm

Saurabh,

You might want to take a look at this .

Sushanth

GuyC · Posted: Wed Dec 09, 2009 9:32 pm

As dick said : it's just a concatenation of 4 columns. an index on a char(16) will look exactly the same as one on 4 char(4) columns.

In DB2 LUW there is a concept of INCLUDE columns on unique indexes.
Suppose you have a unique index on 3 columns, but like to add a fourth to make your accesspath index-only.
On z/os you can not use that index without sacrificing your unique constraint on the first 3 columns. On LUW you can.

For these kind of indexes it is true that only the first 3 columns are on the non-leaf pages of the index, and on the leaf-pages all 4 cols are present. thus enforcing uniqueness and keeping smaller B-tree.