Un quadtree este o structură asemănătoare unui arbore bazată pe puterea a patru și folosită pentru a organiza fișiere într-o bază de date. Fiecare nod părinte sau de pornire are patru noduri copil și fiecare copil deține o anumită cantitate de date. Când limita de date depășește limita sa, patru copii vor fi formați din acel nod. Există două structuri principale cu patru arbori: regiunea și arborele punct, fiecare ușor diferit ca design. În timp ce un quadtree este cel mai des folosit cu bazele de date, poate fi folosit și pentru a găsi pixeli în imagini bidimensionale (2D), deoarece pixelii dintr-o imagine 2D pot fi întotdeauna separați în patru părți.
Toate structurile de tip arbore sunt realizate cu noduri părinte, sau ramură, și noduri copil, sau frunză. Părintele este punctul de plecare și conține date ample bazate pe categorii, în timp ce copilul deține fișiere și documente. Într-un quadtree, fiecare părinte trebuie să aibă patru copii. Deși trebuie să existe patru copii, nu toți copiii trebuie să conțină date; cele fără sunt cunoscute ca noduri nule. Aceste noduri nule rămân adesea stagnante și așteaptă date.
Fiecare nod copil dintr-un quadtree are o limită de date. Această limită este de obicei definită de dimensiunea totală a bazei de date. Când există atât de multă informație încât depășește limita, nodul copil devine un nod părinte, în esență, dând naștere – creând patru noduri copil care preia toate datele suplimentare. De obicei, vor exista unul sau două noduri nule din această creație, dar acest lucru depinde în întregime de câte date au fost în nod.
Există doi arbori cu patru patru principale: regiune și punct. Regiunea quadtree este folosită pentru a descompune o întreagă regiune 2D în părți bazate pe puterea a patru – cum ar fi patru, opt sau 16 părți – și este adesea folosit pentru reprezentări. Această structură este cea mai bună pentru imagini sau grafice cu câmpuri de date. Versiunea de puncte este ca un arbore binar și este cel mai bine utilizată cu puncte ordonate. Această variantă este, de asemenea, un arbore adevărat, deoarece există un punct central din care izvorăsc toate nodurile, spre deosebire de versiunea regiune în care sunt împrăștiate nodurile.
Cea mai obișnuită utilizare a quadtree este separarea și organizarea unei baze de date, dar aceasta nu este singura sa utilizare. Algoritmii realizati pentru a gasi un anumit pixel intr-o imagine folosesc de obicei quadtrees, deoarece fiecare pixel dintr-o imagine poate fi separat in patru parti egale. Acest lucru face ca quadtrees să fie unic potrivit pentru căutarea pixelilor.