quad tree：四叉树

四叉树（quad tree）是在数据库中放置和定位文件（称作记录或键）的方法。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。
　　
　　在树中，记录被存储在叶子的位置上。这一名字的由来是因为记录被存储在端点上，它们上面再没有节点了。分支被称作节点。数的顺序是每节点的分支（也称孩子）数。在四叉树中，每个节点通常有4个孩子，因此顺序是4。四叉树的叶子数也是4。为达到想要的记录所进行的查找操作次数成为树的深度。下图给出了深度为3的四叉树。

　　
　　在实际的树中，可能有成千、成万或数十亿条记录。不是所有的叶子必须有一条记录，但只少要有一半包含记录。不包含记录的叶子成为空。在上面例子中，第8、第12、第16个叶子是空的，用空白圆来指示。
　　
　　四叉树（quad tree）是在二维图片中定位像素的唯一适合的算法。因为二维空间（图经常被描述的方式）中，平面像素可以重复的被分为四部分，树的深度由图片、计算机内存和图形的复杂度决定。