尽管，我们使用以最小区域单位为叶子节点的满四叉树，能够很好的提升检索效率，但是在数据稀疏的时候，许多叶子节点中的数据可能是空的，这就很有可能造成大量的空间浪费。为了避免出现空间浪费，我们有一种改进方案是，使用动态节点分裂的 非满四叉树。
首先，我们可以给每个叶子节点规定一个容纳上限。比如说，我们可以将上限设置为 n。那么，一开始的四叉树只有一个根节点，这个根节点同时也是叶子节点，它表明了当前的全部空间范围。当有数据加入的时候，我们直接记录在这个节点中，查询时也只查询这个节点即可。因此，当插入的数据个数小于 n 时，我们不需要进行任何复杂的查找操作，只需要将根节点的所有数据读出，然后进行距离计算并排序即可。
随着加入的数据越来越多，如果一个叶子节点的容量超出了容纳上限，我们就将该节点进行分裂。首先，我们将该节点转为中间节点，然后，我们会为这个节点生成 1 至 4 个叶子节点（注意：不是一定要生成 4 个叶子节点），并将原来存在这个节点上的数据都转入到对应的叶子节点中。这样，我们就完成了分裂。
不过，有一种极端的情况是，这些数据都会转入到同一个下层叶子节点上。这时，我们就需要继续分裂这个叶子节点，直到每个叶子节点的容量在阈值下为止。
通过这种动态生成叶节点的方案，我们就能得到一棵非满四叉树。和满四叉树相比，它的叶子节点会更少，而且每个叶子节点表示的区域范围也可能是不一样的。这使得非满四叉树具有更好的空间利用率。非满四叉树的查询过程和满四叉树十分相似，也是根据当前的区域编码，找到对应的叶子节点，并根据该叶子节点上存储的数据数量，判断是否要递归扩大范围。这里我就不再详细说了。
