R-tree Secondary Index
An R-tree storage structure is a secondary index for multi-dimensional object management extension data types that can provide the requisite functions (nbr and hilbert).
The R-tree index is a secondary index only. The access method of the base table is B-tree, hash, heap, or ISAM. The R-tree index uses two functions to describe and sort its data. The R-tree index is built on the nbr (normalized bounding rectangle) function of the original object, not the object itself. The nbr function describes the location of each object. The hilbert function sorts the nbr values so that nbr records describing close locations are close to one another in the R-tree index table.
For more information on the nbr and hilbert functions and for more information on handling objects, see the Object Management Extension User Guide.
An R-tree index allows Ingres to answer range queries, such as: “find all records where its position overlaps this spot,” quickly. Without an R-tree index, the whole database must be read. Consider two tables: Table A is a table of houses, and Table B contains park information and location. The query, “select all houses where the house intersects a park” is an example of a spatial join. Without an R-tree index, the spatial join reads Table B entirely for each row in Table A.
When creating an R-tree index (for example, using the Create Indexes dialog or the CREATE INDEX statement) you must include range values, which specify the minimum and maximum values of the index column.
The following example illustrates an R-tree index:
select shape, hex(hilbert), tidp from xfio_shape_ix;
+-----------------------------------------------+------------+-------+
|shape |col2 |tidp |
+-----------------------------------------------+------------+-------+
|((6644550,2412235),(6651911,2425562)) |182343433792| 0|
|((5711593,7469490),(5720615,7473074)) |2CBBAFC085E6| 1541|
|((5755540,7431379),(5765798,7468084)) |2CBC38CC815C| 1543|
|((5764642,7468084),(5776333,7489652)) |2CCEABAE4E25| 1542|
|((5760044,7471142),(5775065,7492024)) |2CCEAC433EF1| 1544|
|((4392392,7367220),(4392773,7368251)) |2F0514CC452B| 3|
|((4393222,7381338),(4393696,7382470)) |2F05ECE43CA5| 1536|
|((6105365,8716914),(6119516,8719411)) |7BC8B02F74CE| 1539|
|((6104208,8719411),(6123227,8733088)) |7BC8B47DB378| 1538|
|((6082882,8707086),(6104747,8708099)) |7BCA043955D6| 1540|
|((8995748,12135179),(8999981,12144160)) |8F8235359771| 1537|
|((9289826,13632441),(9325335,13663808)) |9356B03B9AA0| 1|
|((9268185,13666317),(9286628,13724240)) |93591514F7A8| 4|
|((9396304,16145868),(9397279,16148181)) |95C328081C95| 2|
|((11623892,4873084),(11624345,4874079)) |DF6722ADDB47| 7|
|((11624186,4871079),(11624855,4871713)) |DF6727B0C6D0| 6|
|((11622165,4875404),(11624949,4877801)) |DF672D336FDD| 8|
|((11621206,4874079),(11624345,4876640)) |DF672D738440| 10|
|((11621807,4874417),(11624499,4877759)) |DF672D7B50C1| 9|
|((11610646,4875871),(11612145,4878603)) |DF67321EEFB6| 5|
+-----------------------------------------------+------------+-------+
(20 rows)
The shape column contains the nbr coordinates. The col2 column contains the hilbert number for the nbr. The tidp column corresponds to the tid value of the object in the base table.
Tids (see page
Tids) identify every row on every data page.