btree indexing 
Author Message
 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



Mon, 22 Sep 2003 19:12:32 GMT
 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



Mon, 22 Sep 2003 19:13:59 GMT
 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,
        You can read tons of info about btrees in the Informix Administrator's
Reference, Chapter 7.  Good description on structure, creation, and updating
procedures.

        AFAIK, in this case, the "using btree" is irrelevant as that is the
Informix default.  Your indexes are Informix-standard and are accessed as
discussed in the manuals.

        The "using" case for Create Index is provided for setting up
"secondary access methods" for the index.  Not entirely clear on what that
means, other than those methods are non-Informix-standard ways of ordering
or traversing the indexes.

        Someone please clarify what a "secondary access method" is.  Thanks.

Michael Hoffman



Mon, 22 Sep 2003 21:50:19 GMT
 btree indexing

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



Tue, 23 Sep 2003 01:27:57 GMT
 btree indexing

Quote:

> what does that mean "btree" ?

A btree is an index that is organized in several layers. You could
consider it this way:

Say that we have an index that grows enough to be too cumbersome to use.

Split it into usable portions and make an index over the portions.

When that grows out of hand we continue to split the index until we get an
index over idexes over indexes and so on.

Take a look in chapters 5 and 6 in Elmasri-Navathe: Fundamentals of
Database Systems, ISBN 0-201-54263-3 for an overview, or
http://www.public.asu.edu/~peterjn/btree/ for a nice presentation

/Serafim



Tue, 23 Sep 2003 02:34:08 GMT
 btree indexing

Put it simply: "secondary access method" means index.

csomi

Quote:
-----Original Message-----

Sent: Thursday, April 05, 2001 3:50 PM

Subject: Re: 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,
        You can read tons of info about btrees in the Informix
Administrator's
Reference, Chapter 7.  Good description on structure, creation, and updating
procedures.

        AFAIK, in this case, the "using btree" is irrelevant as that is the
Informix default.  Your indexes are Informix-standard and are accessed as
discussed in the manuals.

        The "using" case for Create Index is provided for setting up
"secondary access methods" for the index.  Not entirely clear on what that
means, other than those methods are non-Informix-standard ways of ordering
or traversing the indexes.

        Someone please clarify what a "secondary access method" is.  Thanks.

Michael Hoffman



Tue, 23 Sep 2003 05:40:49 GMT
 btree indexing
So, to summarise and slightly improve Csom and other peoples excellent
explanations:

With version 9.XX (not sure which XX) Informix started supporting
user-defined indexing methods. This requires new syntax to specify the
necessary intelligence and methods. The default is USING BTREE and for some
reason Informix decided to print that even where not necessary on all
schemas. Maybe because it looks impressive. Anyway, so those indexes are
plain standard and traditional.

This extra syntax means you have to clean up the schema file if you export a
database from a 9.XX engine and import it into a 7.XX engine. That's why I'm
slightly cynical and negative about the inclusion of this clause in the
exports. I wish it would go away.



Tue, 23 Sep 2003 07:44:02 GMT
 
 [ 7 post ] 

 Relevant Pages 

1. multi-column btree index for real values

2. Btree index extension question

3. Problem with btree index on 7.1.3

4. btree-indexing-engine

5. pctfree setting for BTREE indexes

6. Problem with btree index?

7. Corrupt Btree Index

8. Btree Index Depth

9. 6.4/04 btree index corruption after system crash

10. btree indexing

11. reverse order on secondary btree indexes

12. BTree indexes


 
Powered by phpBB® Forum Software