來源：互聯網
四叉樹，是在二維圖片中定位像素的唯一適合的算法，可以用來在數據庫中放置和定位文件。
基本介紹
四叉樹是一種數據結構，是一種每個節點最多有四個子樹的數據結構。
四叉樹可以用來在數據庫中放置和定位文件（稱作記錄或鍵）。這一算法通過不停的把要查找的記錄分成4部分來進行匹配查找直到僅剩下一條記錄為止。
在樹中，記錄被存儲在葉子的位置上。這一名字的由來是因為記錄被存儲在端點上，它們上面再沒有節點了。分支被稱作節點。數的順序是每節點的分支（也稱孩子）數。在四叉樹中，每個節點通常有4個孩子，因此順序是4。四叉樹的葉子數也是4。為達到想要的記錄所進行的查找操作次數成為樹的深度。下圖給出了深度為3的四叉樹。
在實際的樹中，可能有成千、成萬或數十億條記錄。不是所有的葉子必須有一條記錄，但至少要有一半包含記錄。不包含記錄的葉子稱為空。在上面例子中，第8、第12、第16個葉子是空的，用空白圓來指示。
四叉樹是在二維圖片中定位像素的唯一適合的算法。因為二維空間（圖經常被描述的方式）中，平面像素可以重復的被分為四部分，樹的深度由圖片、計算機內存和圖形的復雜度決定。
參考資料 >