What kind of spatial index does arcgis use?

Question

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.

Answer 1

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.