Indexes

Posted by Thomas Mercer-Hursh on 13-May-2015 16:19

I am trying to explain to someone outside of the OpenEdge world how the indices work.   He seems to have some ideas about b-trees which don't match my understanding of indexes.   Is there a document or presentation which talks about how they work?  

I am particularly interested, at the moment, anyway, in describing how many nodes one is likely to have to examine in order to find a particular record with a unique key out of a table with a trillion records.

All Replies

Posted by George Potemkin on 13-May-2015 16:46

> Is there a document or presentation which talks about how they work?

Space: The Final Frontier | Engine Crew Monograph No. 2 => Index Blocks

www.fast4gl.com/.../space.html

> how many nodes one is likely to have to examine in order to find a particular record with a unique key out of a table with a trillion records.

6-7 levels if db uses 8K blocksize

Posted by James Palmer on 13-May-2015 17:01

The man has spoken! I was about to suggest this is one for [mention:ae2ea2f6412743fc8be36c522f414ef0:e9ed411860ed4f2ba0265705b8793d05]

Posted by Thomas Mercer-Hursh on 13-May-2015 17:04

OK, I will look up that document.  Seemed likely there was something somewhere.

I have seen the previous remarks about 6 levels.  Does that mean that one can find any record by looking at 6 nodes?

Posted by Thomas Mercer-Hursh on 13-May-2015 17:06

Is that document still current?  I see it is from 1997.

Posted by George Potemkin on 14-May-2015 00:04

The current index structure format was introduced in Progress V7 in 1993.

Examples of ixanalys for the tables with 16 and 8 billions records:

community.progress.com/.../14487.aspx

Posted by gus on 03-Jun-2015 15:58

the document is old, but the ideas in it are still valid. the major changes since then are:

* type ii storage areas. tables in them can be read without using any indices. block headers are different.

* longer recids/rowids (64 vs 32 bits)

* bigger maximum key size. used to be roughly 189 bytes. now is roughly 3,000 bytes.

* operation fo the "index delete chain" and reservations for deleted unique index entries is different.

anyhow a find of a unique index entry will require readin down from the index root block through all the intermediate levels down to the leaf level. from there we ontain the rowid of the desired row and go read that. so one read per level plus one for the row itself plus one per additional row fragment.

This thread is closed