四叉樹

四叉樹是一種數據結構，是一種每個節點最多有四個子樹的數據結構。

四叉樹可以用來在資料庫中放置和定位文件（稱作記錄或鍵）。這一演演算法通過不停的把要查找的記錄分成4部分來進行匹配查找直到僅剩下一條記錄為止。

在樹中，記錄被存儲在葉子的位置上。這一名字的由來是因為記錄被存儲在端點上，它們上面再沒有節點了。分支被稱作節點。數的順序是每節點的分支（也稱孩子）數。在四叉樹中，每個節點通常有4個孩子，因此順序是4。四叉樹的葉子數也是4。為達到想要的記錄所進行的查找操作次數成為樹的深度。下圖給出了深度為3的四叉樹。

在實際的樹中，可能有成千、成萬或數十億條記錄。不是所有的葉子必須有一條記錄，但至少要有一半包含記錄。不包含記錄的葉子稱為空。在上面例子中，第8、第12、第16個葉子是空的，用空白圓來指示。

四叉樹是在二維圖片中定位像素的唯一適合的演演算法。因為二維空間（圖經常被描述的方式）中，平面像素可以重複的被分為四部分，樹的深度由圖片、計算機內存和圖形的複雜度決定。