R-tree Index

Principle

R-tree is a disk-based index structure, which is a natural extension of B-tree (one-dimensional) in high-dimensional space. It is easy to integrate with existing database systems and can support various types of Spatial Query processing operations. It has been widely used in practice and is one of the most popular Spatial Index methods.

The R-tree Spatial Index method is to design a virtual rectangular target and include some targets with similar spatial positions in the rectangle, as shown in the left figure below. These rectangles are used as the Spatial Index, which contains the pointers of the included spatial objects. For example, Contains spatial objectsD in a, E, F, Contains spatial objectsH in B, I, J, K, Contains spatial objectsL in C, M. An example of R-tree Index is shown in the figure below.

Figure: R-tree Index Diagram

In spatial retrieval, we first determine which rectangles fall into the retrieval window, and then further determine which objects are the contents to be retrieved. This can improve the retrieval speed.

Characteristic

  • The spatial retrieval efficiency of R-tree Index is very high, and the retrieval accuracy is also very high.
  • The index data and geographic data of R-Tree Index are not stored together, and the update of R-Tree Index involves the balance and split of the R-tree, which is more complex, the update speed is slower, the query efficiency after large-scale editing is reduced, and Rebuild Spa tial Index is needed. Works well for read-only data or data that is not frequently edited by Spatial Data.
  • R-tree Index supports File Database and Database-type Datasource. See Table 1 on this page for specific types.

Applicable conditions

R-tree Index is more suitable for static data, such as data used as base map and data not frequently edited (except editing of attribute data). It is recommended to establish R-tree Index.

Hint:
The engine types

supporting the establishment of R-tree Index include: UDB, SQLPlus, PostgreSQL, OraclePlus, OracleSpatial, KingBase, MySQL, BeyonDB, and Altibase.