12

My first master's research topic was about spatial indexes. I learned about R-Trees and R+-tree, R*-trees and other various but very similar topics. This may not be published information, but what spatial index type does ESRI use? As a secondary question can this type be changed and how? There are some situations where a different type of index would boost performance.

In Oracle's case it can use the ST_Geometry spatial data type which can be indexed to either an R-tree or a quad tree or both: http://docs.oracle.com/html/A88805_01/sdo_intr.htm

Other databases use binary storage mechanisms which are non-spatial by default and do not seem to use the spatial indexing available. In SQL 2005 and lower spatial datatype didn't exist, but ESRI was still able to use SQL databases. According to this case study SQL 2012: http://www.microsoft.com/casestudies/Case_Study_Detail.aspx?CaseStudyID=710000000547 it uses the automated spatial performance type, but doesn't list what kind of R-Tree it is.

Bonus points for reading material answering this question.

Thanks.

Roland
  • 1,290
  • 9
  • 21
  • 4
    This depends on what database you are connecting to and how it is set up. – Mapperz Dec 19 '12 at 21:31
  • this might help: http://webhelp.esri.com/arcgisserver/9.3/java/index.htm#geodatabases/settin-1197445025.htm – Gago-Silva Dec 19 '12 at 21:58
  • http://resources.arcgis.com/en/help/main/10.1/index.html#//003n0000001q000000 may be worth looking at too – PolyGeo Dec 19 '12 at 23:15
  • 1
    Thanks to the second commenter I updated due to your link. Thanks @PolyGeo I followed the chain as best I could and ended up here: http://www.dpi.inpe.br/cursos/ser303/oracle_r_tree.pdf. It says it is an R-Tree and then reference a R*-tree in the bibliography –  Dec 19 '12 at 23:41
  • One of the most interesting spatial indexes for me is revealed here: https://www.youtube.com/watch?NR=1&v=0-zd_XyqQbM – mistapink Jun 04 '13 at 21:57

2 Answers2

8

There are a number of different spatial indexes that ArcSDE will use depending on what database and spatial datatype you are using.

  • Oracle SDO_Geometry -> Oracle Spatial R-Tree, I don't know if Quad tree is still supported after 9i.
  • Oracle ST_Geometry -> ESRI Multilevel Grid Index
  • Oracle Binary/LOB/WKB -> Uses the S table as a Multilevel Grid Index (not a DBMS index)
  • MS SQL Server Binary/WKB -> Uses the S table as a Multilevel Grid Index (not a DBMS index)
  • MS SQL Server Geometry/Geography -> B-Tree
  • PostgreSQL ST_Geometry -> PostgreSQL R-Tree
  • PostgreSQL PostGIS -> GiST
  • DB2 ST_Geoemtry -> Multilevel Grid Index
  • Informix ST_Geometry -> R-Tree
  • Netezza -> Does not use indexes
  • Terradata -> Tessellation (I don't know much about this)

In Oracle's case, Oracle Spatial uses an R-Tree domain index while Esri's type SDE.ST_Geometry uses a grid domain index. With SQL Server 2012, I believe the major change to spatial indexing is the addition of auto grid. This doesn't actually change the structure of the grid (still a B-Tree), but it does automatically choose a better grid size.

That is everything I can think of, but I am sure I have missed something.

travis
  • 1,910
  • 17
  • 21
0

Spatial indexes differ depending on the data source. Feature classes in the following geodatabase types use grid-based spatial indexes:

  • Personal geodatabases
  • File geodatabases
  • Geodatabases in DB2
  • Geodatabases in Oracle, if the feature class contains an Esri ST_Geometry or binary geometry storage field
  • Geodatabases in Microsoft SQL Server, if the feature class contains a binary geometry storage field
Vince
  • 20,017
  • 15
  • 45
  • 64
oneda
  • 1
  • 1
  • 1
    This doesn't add much more value over the existing answers, beyond mentioning some (but not all) data formats not mentioned elsewhere, and it leaves out shapefile, Oracle SDO_GEOMETRY, Informix and the NoSQL databases, and binary storage in SQL Server has long been de-supported. – Vince Sep 06 '22 at 03:26