A comparison on BTree, RTree
& Quad Tree Indexing technologies in the field of Spatial
The following table illustrates a
comparison on Indexing technologies BTree, RTree and Quad Tree in the field
of Spatial. Going through the content, the reader should be in a position to
understand that each of the indexing technologies have their own set of
strengths and weaknesses and have limitations on the areas they play around.
Clearly, BTree is ill suited in the field of Spatial, while it gels well, when
it is applied on Linear data sets. The reader can take his / her perspective as
to which of the two indexing technologies are better, i.e between RTree and
Quad Tree. I'll leave that decision to the reader based on their need and
requirement.
BTree

RTree

Quad
Tree


Definition

In
computer science, a Btree is a tree data structure that keeps data sorted
and allows searches, sequential access, insertions, and deletions in
logarithmic time.

Rtrees
are tree data structures used for spatial access methods, i.e., for indexing
multidimensional information such as geographical coordinates, rectangles or
polygons.

A
Quadtree is a tree data structure in which each internal node has exactly
four children.

Description

The
Btree is a generalization of a binary search tree in that a node can have
more than two children. The Btree is optimized for systems that read and
write large blocks of data. It is commonly used in databases and file
system’s.

Similar
to the Btree, the Rtree is also a balanced search tree (so all leaf nodes
are at the same height), organizes the data in pages, and is designed for
storage on disk (as used in databases)

Quadtrees
are most often used to partition a two dimensional space by recursively
subdividing it into four quadrants or regions. The regions may be square or
rectangular, or may have arbitrary shapes.

Support
Spatial Data

The
Btree access method, indexes numeric and character data only.
You
cannot use the Btree access method to index spatial data.

Designed
for indexing multidimensional information such as geographical coordinates,
rectangles or polygons

Quadtrees
work on two dimensional space / regions that may be square, rectangular or
any arbitrary shapes

Approximation

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

The approximation of
geometries cannot be fine tuned. (Spatial uses the minimum bounding
rectangles.)

The
approximation of geometries can be fine tuned by setting the tiling level and
number of tiles.

Complexity

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

Index creation and tuning are
easier.

Tuning is more complex, and
setting the appropriate tuning parameter values can affect performance
significantly.

Storage

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

Less storage is required

More storage is required.

Workload

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

If your application
workload includes nearest
neighbor
queries, Rtree indexes are
faster, and you can use the sdo_batch_size
keyword.

If your application
workload includes nearest
neighbor
queries, quadtree indexes are
slower, and you cannot use the sdo_batch_size
keyword.

Updates

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

Heavy update activity to
the spatial column may
decrease the Rtree index
performance until the index is rebuilt.

Heavy update activity
does not affect the
performance of a Quadtree
index.

Dimensions
supported

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

You can index up to four
dimensions.

You can index only two
dimensions. If LRS (Linear Referencing System) data is indexed using a
spatial Quadtree index, only the first two dimensions are indexed; the
measure dimension and its values are not indexed.

Recommended

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

An Rtree index is
recommended for indexing
geodetic data if
ST_WITHIN queries will be
used on it.

A quadtree index is not
recommended for Indexing geodetic data if ST_WITHIN queries will be used on
it.

WholeEarth
Model

BTree
is optimized for Linear data set and cannot handle spatial data and features.
Hence, not applicable.

An Rtree index is required
for a wholeEarth index.

A
quadtree index cannot be used for a wholeEarth index.

Reference
1: Wikipedia pages of BTree, RTree and Quad Tree
This comment has been removed by a blog administrator.
ReplyDelete