UB-Tree

Hi,

The inventor of the B-Tree algorythm, R. Bayer, published
in the past years ('96-'01) several scientific papers where
he describes the new UB-Tree algorythm. It is based on
ordinary B-Tree implementation but allows >multidimensional<
indexing.

Apart from the need to update only one index instead of
several for each table insert/delete the UB-Tree indexing
allows to perform extremly performant lookups for queries
that contain constraints for several columns (dimensions)
and sort criterias, like:

SELECT * FROM EMPLOYEES WHERE ID>10 AND ID<100 AND INCOME>5000 SORTED BY NAME

Such a query could profit from an UB-Tree index on the columns
(dimensions) ID, INCOME and NAME - all at once, using only
one UB-Tree!

So the UB-Tree allows you:
- to make range queries on all dimensions at once, and
- read the result in sorted order (with only little overhead), where
- each dimension can be read in sorted or reverse order

I guess such an indexing method would please any SQL database.
Has anybody of you ever stumbled across the UB-Tree related
algorythms?

If not, you can download several PDF documents describing
the UB-Tree related algorythms from this URL (in english
language!):

http://mistral.in.tum.de

I found no free implementation of the UB-Tree. The team
of R. Bayer only released closed source and sell it.

kind regards,
Robert Schrem