Vad är en fyrhjul?
En fyrdubb är en trädliknande struktur baserad på kraften hos fyra och används för att organisera filer i en databas. Varje förälder eller startande nod har fyra underordnade noder, och varje barn har en viss mängd data. När datagränsen spill över sin gräns kommer fyra barn att göras från den noden. Det finns två huvudsakliga fyrtratstrukturer: regionen och punktträdet, var och en något annorlunda i design. Medan en fyrdug oftast används med databaser, kan den också användas för att hitta pixlar i tvådimensionella (2D) bilder, eftersom pixlarna i en 2D-bild alltid kan delas upp i fyra delar.
Alla trädliknande strukturer är gjorda med förälder eller gren, noder och barn eller bladnoder. Föräldern är utgångspunkten och innehåller breda kategoribaserade data, medan barnet har filer och dokument. I en fyrbana måste varje förälder ha fyra barn. Det måste finnas fyra barn, men inte alla barn måste innehålla data; de utan kallas nollnoder. Dessa nollkoder förblir ofta stillastående och väntar på data.
Varje barnnod i en fyrdel har en datagräns. Denna gräns definieras vanligtvis av den totala databasstorleken. När det finns så mycket information att det skjuter ut över gränsen, blir barnnoden en föräldernod genom att väsentligen föda - skapa fyra barnnoder som tar upp alla extra data. Det kommer vanligtvis att finnas en eller två nollnoder från den här skapelsen, men detta beror helt på hur mycket data som fanns i noden.
Det finns två huvudsakliga fyrträd: region och punkt. Regionkvadratrien används för att sönderdela en hel 2D-region i delar baserade på kraften från fyra - som fyra, åtta eller 16 delar - och används ofta för representationer. Denna struktur är bäst för bilder eller datafältdiagram. Punktversionen är som ett binärt träd och används bäst med beställda poäng. Denna variant är också ett riktigt träd, eftersom det finns en central punkt från vilken alla noder springer, till skillnad från den regionversion där noderna är spridda.
Den vanligaste användningen av fyrhjulet är att separera och organisera en databas, men det är inte dess enda användning. Algoritmer gjorda för att hitta en specifik pixel i en bild använder vanligtvis fyrträd, eftersom varje pixel i en bild kan delas upp i fyra lika delar. Detta gör fyrhjulingar unika för att söka efter pixlar.