Search code examples
sql-serversql-server-2008sql-server-2012spatial-index

How does SQL Server maintain spatial index internally?

I know that indexes are implemented using B-Tree. I have read the Microsoft documentation on spatial indexes. It seems that they implement spatial data using B tree as well.

But why is a grid required or how does grid hierarchy work or how does SQL Server search using spatial data values? All that stuff is still not clear to me.

It would be really helpful if anyone please explain it.

Thanks :-)

Solution

  • As you’re probably aware, the standard index in SQL Server uses a B+ tree structure, which is a variation of the B-tree index. B-tree is nothing but a data structure that keeps data sorted to support search operations, sequential access, and data modifications such as inserts and deletes.

    A B-tree index contains at least two levels: the root and the leaf. The root is the top most node and can have child nodes. If there are no child nodes, then the tree is called a Null tree. If there are child nodes, they can be either leaf nodes or intermediate nodes. A leaf node is the bottom part of the tree. Intermediate levels can exist between the root and leaf levels. The difference between a B-tree index and a B+ tree index is that all records are stored only at the leaf level for B+ tree, whereas in a B-tree we can store both keys and data in the intermediate nodes.

    SQL Server spatial indexes are built on top of the B+ tree structure, which allows the indexes to use that structure and its access methods. The spatial indexes also use the fundamental principles of XML indexing. XML indexing was introduced in SQL Server 2005 and supports two basic types of indexes: primary and secondary. The primary XML index is a B+ tree that essentially contains one row for each node in the XML instance.

    So how does SQL Server implement the spatial index? As already mentioned, SQL Server starts with a B+ tree structure, which organizes data into a linear fashion. Because of this, the indexes must have a way to represent the two-dimensional spatial information as linear data. For this, SQL Server uses a process referred to as the hierarchical uniform decomposition of space. When the index is created, the database engine decomposes, or refactors, the space into a collection of axes aligned along a four-level grid hierarchy. Figure 1 provides an overview of what this process looks like.

    enter image description here

    Taken from https://www.red-gate.com/simple-talk/sql/t-sql-programming/sql-server-spatial-indexes/