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
onlylittle 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
