Un quadtree è una struttura ad albero basata sulla potenza di quattro e utilizzata per organizzare i file in un database. Ogni nodo padre o di partenza ha quattro nodi figlio e ogni figlio contiene una certa quantità di dati. Quando il limite di dati si estende oltre il suo confine, verranno creati quattro figli da quel nodo. Ci sono due strutture quadtree principali: la regione e l’albero dei punti, ognuna leggermente diversa nel design. Sebbene un quadtree venga utilizzato più spesso con i database, può anche essere utilizzato per trovare pixel in immagini bidimensionali (2D), poiché i pixel in un’immagine 2D possono sempre essere separati in quattro parti.
Tutte le strutture ad albero sono realizzate con nodi padre, o ramo, e nodi figlio, o foglia. Il genitore è il punto di partenza e contiene ampi dati basati su categorie, mentre il figlio contiene file e documenti. In un quadtree, ogni genitore deve avere quattro figli. Sebbene ci debbano essere quattro figli, non tutti i figli devono contenere dati; quelli senza sono noti come nodi nulli. Questi nodi nulli spesso rimangono stagnanti e attendono i dati.
Ogni nodo figlio in un quadtree ha un limite di dati. Questo limite è generalmente definito dalla dimensione complessiva del database. Quando ci sono così tante informazioni che spinge oltre il limite, il nodo figlio diventa un nodo genitore essenzialmente dando vita, creando quattro nodi figlio che occupano tutti i dati extra. Di solito ci saranno uno o due nodi null da questa creazione, ma questo dipende interamente dalla quantità di dati presenti nel nodo.
Ci sono due quadtree principali: regione e punto. Il quadtree della regione viene utilizzato per scomporre un’intera regione 2D in parti in base alla potenza di quattro, ad esempio quattro, otto o 16 parti, e spesso viene utilizzato per le rappresentazioni. Questa struttura è la migliore per immagini o grafici di campi dati. La versione a punti è come un albero binario ed è meglio utilizzata con punti ordinati. Anche questa variante è un vero albero, perché c’è un punto centrale da cui scaturiscono tutti i nodi, a differenza della versione regione in cui i nodi sono sparsi.
L’uso più comune del quadtree è quello di separare e organizzare un database, ma questo non è il suo unico utilizzo. Gli algoritmi creati per trovare un pixel specifico in un’immagine usano comunemente quadtree, perché ogni pixel in un’immagine può essere separato in quattro parti uguali. Questo rende i quadtree particolarmente adatti alla ricerca di pixel.