Wat is een quadtree?

Een quadtree is een boomachtige structuur op basis van de kracht van vier en wordt gebruikt om bestanden in een database te organiseren.Elke ouder, of starten, knooppunt heeft vier onderliggende knooppunten en elk kind bevat een bepaalde hoeveelheid gegevens.Wanneer de gegevensbeperking over zijn grens limiet, worden vier kinderen gemaakt van dat knooppunt.Er zijn twee hoofds -quadtree -structuren: de regio en de puntboom, elk iets anders van ontwerp.Hoewel een quadtree meestal wordt gebruikt met databases, kan deze ook worden gebruikt om pixels te vinden in tweedimensionale (2D) afbeeldingen, omdat de pixels in een 2D-afbeelding altijd in vier delen kunnen worden gescheiden.

Alle boomachtige structuren zijnGemaakt met ouder, of tak, knooppunten en kind, of blad, knooppunten.De ouder is het startpunt en bevat brede categoriegebaseerde gegevens, terwijl het kind bestanden en documenten bevat.In een quadtree moet elke ouder vier kinderen hebben.Hoewel er vier kinderen moeten zijn, hoeven niet alle kinderen gegevens te bevatten;Degenen zonder staan bekend als nulknooppunten.Deze nulknooppunten blijven vaak stagneren en wachten op gegevens.

Elk onderliggende knooppunt in een quadtree heeft een gegevenslimiet.Deze limiet wordt meestal bepaald door de algemene databasegrootte.Wanneer er zoveel informatie is dat het voorbij de limiet duwt, wordt het onderliggende knooppunt een ouderknooppunt door in wezen geboorte te geven mdash;Vier kinderknooppunten maken die alle extra gegevens in beslag nemen.Er zullen meestal een of twee nulknooppunten zijn van deze creatie, maar dit hangt volledig af van hoeveel gegevens er in het knooppunt waren.

Er zijn twee hoofdvaartuigen: regio en punt.De regio quadtree wordt gebruikt om een volledig 2D -gebied te ontleden in delen op basis van het vermogen van vier mdash;zoals vier, acht of 16 delen mdash;en vaak gebruikt voor representaties.Deze structuur is het beste voor afbeeldingen of gegevensveldgrafieken.De puntversie is als een binaire boom en kan het beste worden gebruikt met geordende punten.Deze variant is ook een echte boom, omdat er een centraal punt is waaruit alle knooppunten vellen, in tegenstelling tot de regionversie waarin de knooppunten zijn verspreid.

Het meest voorkomende gebruik van de quadtree is het scheiden en organiseren van een database, maarDit is niet het enige gebruik.Algoritmen gemaakt om een specifieke pixel te vinden in een afbeelding gebruiken gewoonlijk quadtrees, omdat elke pixel in een afbeelding kan worden gescheiden in vier gelijke delen.Dit maakt quadtrees uniek geschikt voor het zoeken naar pixels.