View source for B-tree and UB-tree

==UB-trees for Multidimensional Applications==
Classical B-trees were designed for one dimensional, linearly ordered key spaces. Here, B-trees are excellent for point queries and interval queries.  But many applications are multidimensional, e.g. geographic maps, (2-dim), GPS data (3-dim, because of altitude in addition to latitude and longitude), or Data Warehouse (DWH) queries like asking for 
*'' the sales in a geographic area for a certain product group in a certain month '' (4-dim). 
Range queries in such spaces correspond to multidimensional rectangles, and the multidimensional points in those rectangles must be retrieved. 

By a mathematical transformation, such multidimensional data spaces can be linearized and then represented in ordinary B-trees. The overall resulting data structure is called <strong>''UB-tree''</strong> for <strong>Universal B-tree</strong> (Markl et al. 2000),(Website for UB-trees). The transformations used are space filling curves, and the linear order of the multidimensional keys is the order of the points on that curve. 

Two examples of such curves are the ''Peano-curve'' or ''Z-curve'' and the ''Hilbert-curve''. The order defined by the Z-curve is called ''Z-order''. Points in multidimensional space are transformed to their one dimensional ''Z-coordinate ''and inserted into the B-tree using the Z-order. Therefore, the points in the node of a B-tree correspond to an interval on the Z-curve. An interval of the Z-curve covers a multidimensional subspace, a so-called ''Z-region''. Therefore, a B-tree node corresponds exactly to a Z-curve interval and also to a Z-region. Figure 4 shows the interval [4:20] of the Z-curve (numbering starts with 0 in the left upper corner) in a 2-dimensional 8x8 space and the region covered by it with its characteristic shape.

[[Image: Btree-RegionZ-Fig4-n.GIF|thumb|400px|left|F1|The interval [4:20] of the Z-curve and its corresponding region]]
Now, let us look at a multidimensional range query: To answer such a query, only those UB-tree nodes must be retrieved, whose Z-regions intersect the query box. There are basically two problems to solve, the mathematical algorithms 
# to compute the Z-coordinate of a multidimensional point and
# to determine those UB-tree nodes, whose Z-regions intersect the query box specified by the range query.

These two algorithms are complicated, but they have linear running time, i.e. they are very efficient. In addition, both tasks can be solved by preprocessing the data before accessing the B-tree index. Therefore, multidimensional indexing can be done efficiently and easily by using an existing B-tree implementation, e.g. in a RDBS: One simply adds a preprocessor which performs the above two tasks, runs completely in main memory, and does not cause any I/O overhead.  The combination of a standard B-tree with an appropriate preprocessor results in the UB-tree.

Figure 5 shows a coarse example of a very small database with a query box, which is intersected by only 5 regions. 

A further consequence is: The set of nodes which must be retrieved is proportional to the set of datapoints in the query box, i.e. to the size of the answer for a query, and therefore it is essentially independent of the size of the overall database. This is illustrated intuitively by Figure 6: the region pattern results from a database with 50.000 points. The red regions are the only ones which must be retrieved from the database, since they intersect the querybox. For details see (Web Site for UB-trees). 
[[Image: Btree-RegionZ-Fig6-50.GIF|thumb|300px|left|F1|Range query in a very small database]]
[[Image: Btree- Range-Fig7-50.GIF|thumb|300px|right|F1|Range query in a moderate database]]























===All Relational <strong>Databases are Multidimensional</strong>===
So far we only discussed multidimensional point data. An important observation is that all relational databases are multidimensional. To explain this view, consider an entity/relationship model with two entities, e.g. ''Authors'' and ''Books''. Since some authors wrote several books and some books have several authors, there is an n:m relationship ''wrote'' between Authors and Books. The standard representation of such a model in a relational database is as follows: 
# Use a table, also called ''Authors'', for the entity Authors, with primary key A
# Use a table, also called ''Books'', for the entity Books, with primary key B
# Use a table, also called ''wrote'', for the n:m relationship ''wrote'', with foreign keys A of Authors and B of Books. 
Thus ''wrote'' has the composite key (A, B) as its primary key, and its tuples can  obviously be considered as points in a 2-dimensional dataspace. Whenever relational queries must join the two tables ''Authors'' and ''Books'' via the table ''wrote'', typically 2-dimensional range queries on the relation ''wrote'' result.
===Extended <strong>Multidimensional Objects</strong>===
[[Image: Btree-Intervals-Fig8.GIF|thumb|400px|left|F1|Intervals and their mapping to 2-dimensiolal dual space]]

To index extended multidimensional objects of arbitrary shape, a simple transformation does the trick: surround the object by a tight multidimensional rectangle R, the bounding box. In case of a d-dimensional space, transform the bounding box into a point in 2d-dimensional space, also called the ''dual space'',  and store this point in an UB-tree.  Figure 7 shows the transformation of several intervals with coordinates [x, y]. Each interval in one-dimensional space is transformed into points (x, y) in 2-dimensional space. Since x<y, these points are all located in the subspace below the diagonal. Range queries for containment, exclusion or intersection with objects in d-space are transformed into range queries in 2d-space analogously. Details are found on (Web Site for UB-trees).