Choose Index below for a list of all words and phrases defined in this glossary.

Quadtree / Quad Tree

index | Index

Quadtree / Quad Tree - definitions

quadtree - [data structures] A method for encoding raster data that reduces storage requirements and improves access speeds by storing values only for homogeneous regions rather than for every pixel. The raster is recursively subdivided into quadrants until all regions are homogeneous or until some specified level has been reached.

[Category=Geospatial ]

Source: esri, 22 July 2012 10:22:52, External 

These advertisers support this free service

quad tree - A quad tree is a method of placing and locating files (called records or keys) in a database. The algorithm finds data by repeatedly dividing the number of ultimately accessible records in four parts until only one remains.

In a tree, records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. Branch points are called nodes. The order of a tree is the number of branches (called children) per node. In a quad tree, there are always four children per node, so the order is 4. The number of leaves in a quad tree is always a power of 4. The number of access operations required to reach the desired record is called the depth of the tree. The image below shows a quad tree of depth 3.


In a practical tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but more than half do. A leaf that does not contain a record is called a null. In the example shown here, the eighth, twelfth, and sixteenth leaves are nulls, indicated by open circles.

The quad tree is uniquely suited as an algorithm to locate pixels in a two-dimensional image. The reason for this is that, in two dimensions (the usual way in which graphics are depicted), square pixels can be divided into four square parts repeatedly. The depth of such a tree depends on the image resolution, the computer memory, and the complexity of the image.

Also see binary tree, B Tree / B-tree, splay tree, and tree structure.

Related glossary terms: record, flexfield, splay tree, in-memory database, virtual private database (VPD), Edgar F. "Ted" Codd, extent, field, object-oriented database management system (OODBMS / ODBMS), hash / hashing / hash algorithm

[Category=Data Management ]

Source:, 02 September 2013 09:43:04, External




Data Quality Glossary.  A free resource from GRC Data Intelligence. For comments, questions or feedback: