Hi,

btree is not an Informix specific technology. The btree

implementation is of Informix but the technology itself

is widely used. In fact btree is the de facto standard

for storing index values - in many cases btree (or index)

based search is much more efficient then sequential scan.

...

Here's a very brief intro into the Informix implementation:

Let's assume you have a table (mytable) with an indexed

column (mycolumn) of INT data type. Then the btree

index would look like this:

You have an entry page (call it pageE) which holds

pointers, something like this:

pointer1 points to page1 which holds pointers for values less then zero

pointer2 points to page2 which holds pointers for values in the range of

0-99

pointer3 points to page3 which holds pointers for values in the range of

100-150

pointer4 points to page4 which holds pointers for values in the range of

151-300

pointer5 points to page5 which holds pointers for values greater then 300

Then for example page2 holds pointers like this:

pointer21 points to page21 which holds pointers for values in the range of

0-10

pointer22 points to page22 which holds pointers for values in the range of

11-50

pointer23 points to page23 which holds pointers for values in the range of

51-55

pointer24 points to page24 which holds pointers for values in the range of

56-100

Finally page 23 holds pointer like this

pointer231 points to row which holds column value of 51

pointer233 points to row which holds column value of 53

pointer234 points to row which holds column value of 54

pointer234 points to row which holds column value of 55

Let's assume you execute an SQL statment like this:

SELECT * FROM mytable WHERE mycolumn=53

Then, first the engine looks through pageE and finds pointer2

which points to page2 for values in the range of 0-101.

Then it goes to page2 where it finds pointer23 which

points to page23 for values in the range of 51-55.

Then it goes to page23 and finds pointer233 which finally

points to the table row itself.

Roughly that's the way how Informix implements btree.

One of the nicest features of the Informix implementation

(IDS 9 and above) is that one can extend the indexing

mechanism for extended data types. Eg. you can index not just

primitive or built in data types but by coding the necessarry

support routines you can use indexes for user defined data

types also.

Hope that helps...

cheers,

Csomi

Quote:

-----Original Message-----

Sent: Thursday, April 05, 2001 1:14 PM

Subject: btree indexing

Hello,

I'm very new with informix, so I need to find out where I can read

somthing about "btrees".

I found a script we are using here where is written:

create unique index "bibl".b_idsz on "bibl".bisy (id,sz) using btree ;

create index "bibl".ix100_1 on "bibl".bisy (gg) using btree ;

what does that mean "btree" ?

Elke

----------------------------------------------------------------------

Elke Salecker

WZB Wissenschaftszentrum Berlin phone: +49/30/25491-574

Bibliothek fax: +49/30/25491-533

Reichpietschufer 50

D-10785 Berlin