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

Fri, 8 Mar 2002 16:48:15 +0100
Robert Schrem <robert.schrem@WiredMinds.de>
UB-Tree
On Fri, 2002-03-08 at 20:48, Robert Schrem wrote:
> 
> 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

The last one tere seems to be the original explanation of the idea.
 
> I found no free implementation of the UB-Tree. The team
> of R. Bayer only released closed source and sell it.

This technique seems to be a good candidate for implementing using GiST
or perhaps just defined using the <. operator mentioned there. 

Mappign from ordinary query with several = , < and between may be a
little tricky though.

They may also have patents on it, so we should move carefully here.

-------------
Hannu



09 Mar 2002 00:37:32 +0500
Hannu Krosing <hannu@krosing.net>
Re: UB-Tree