当我对遇到的问题找一个解决方案的时候,我遇到了BKD树这个难题。从来没有听过吗?这种情况可能不只是你自己。从google上搜索”bkd tree”,通常会把你引导到original research paper和Lucene中用来解决一些空间搜索的patch 网页,然后就没有其他的了。实际上,在写这篇文章的时候,google的第2篇文章推过来的是wikipedia上与这个比较相似名称的 K-D-B Tree。BKD树太冷门了,google都以为你是想找其他的。
BKD树作为一个这么伟大的发明,google这样对待它,这是相当不幸的。
BKD树是用来搜索多维数据的一种树。多维数据可以是物理空间中的一些点,也可以是一个很大调色板上的一些点。BKD树相当善于做其他数的工作。相比和BKD同类型的树,BKD树通常比K-D-B树以及更简单的 R-Trees更快,更节省空间。
本篇文章不是一个对BKD树简单的罗列或者详细描述的wikipedia。我尝试用大白话来讲解BKD树是怎么运作的,有哪些特性。