理解K-D树背后的思想_hipac 数据结构

在介绍nf-HiPAC的时候，我提到了使用多维匹配树的方法，详见：
HiPAC高性能规则匹配算法之查找过程：http://blog.csdn.net/dog250/article/details/41220085
利用这一思想，后面我优化了iptables的规则集，详见：
iptables高性能前端优化-无压力配置1w+条规则：http://blog.csdn.net/dog250/article/details/77618319
总之，思路是完全一致的。

  也许，有人会问，落实到代码中的话，应该如何组织数据结构呢？这是一个很实际的问题，算法是必须要用代码实现的。

  这个多维树匹配归根到底是一个查找问题。还是老办法，我从最简单的情况开始，即一维的情况。

  这非常简单，在一维的情况下，数据结构就是一棵二叉树。这里无需在重复二叉树的构建，查找等细节，但是必须要理解二叉树二分查找操作的本质：不断将结果继续二分。这么做的结果就是不断把空间切分成更小的两部分，取其一部分，直到该部分就是结果本身的那个点。

  现在推广到二维的情况，还是按照切分空间的思路，二维空间就是个平面，因此就要不断切分这个平面，但问题是要用削平果的方式呢，还是用切西瓜的方式呢？

• 削苹果的方式
  不断沿着不同的方向削，即不断转动苹果，保持在削苹果的过程中，苹果的形状不变。
• 切西瓜的方式
  每一刀都改变西瓜的外形，在每一个方向只切一刀。

在之前的文章里，我曾经倾向于切西瓜的方式，即在一个维度方向一次性查到结果，然后再在另一个维度方向继续，在每一个维度方向均是一次性查找到结果。这种方式，在操作描述上看似简单，但是在数据结构的组织上就会发现它会带来大量的数据冗余，因为在一个方向的每一个叶子节点上都要携带所有其它维度的所有信息。之所以会有数据冗余问题是因为我们对空间的切割方式是正交的，即一个维度不了解另一个维度的任何信息。可以描述为：

当我们在一个维度查找时，仅仅在这个维度查找，不会使用其它维度的任何信息。

除此之外，切西瓜方式在模糊匹配的时候根本就适用！，由于没有额外维度的信息做辅助，在“寻找最邻近点”这种问题的时候，可能会找到错误的结果，比如：

因此，我们需要在切割空间的时候，综合所有维度的信息来切割：

• 切分一维数轴的时候，用点；

• 切分二维平面的时候，用线；

• 切分三维空间的时候，用面；
  …

• 切分
  n
  

  n

  $n$维超空间时，用$n-1$维的超平面。

这样一来，我们不再在某一个维度上将一维数轴不断切割成更小的两个部分，而是不断统一使用
n−1

n

−

1

$n-1$维的超平面切割。即每次切割都是沿着一个轴切割即可，这样自然而然的降低了1个维度。

  我以二维的情况来说明：

可以看出，我是不断地把二维平面一次次地切割成更小的二维平面，而不是在
x

x

$x$轴或者$y$轴先一走到底然后再转入别的轴。

  现在的问题是，在每一次切割的时候，到底是沿着
x

x

$x$轴还是沿着$y$轴呢？这就涉及到了数据的分散性问题了，一般而言，要想让最后的树更平衡些，选择数值方差大的那个轴切割会比较理想，不然的话，树会倾斜。

嗯，没错，削平果方式就是K-D树的方式，它可以让你找到最邻近的点，或者它可以让你知道某某东西更倾向于哪个集体，它可以让你找到组织。

K-D树在寻找最近的
k

$k$个邻居时涉及到回溯，简单来说就是判定一个是否$a$比
b

<script type="math/tex" id="MathJax-Element-1120">b</script>更接近的问题，因此在回溯的过程中，需要不断用当前距离作为半径的圆形来圈定范围，一旦既有的点在这个范围中，那么就是它了！算法细节问题并不是本文的内容，因此这里不谈。

待续！