kd樹（k-dimensional樹的簡稱），是一種分割k維資料空間的資料結構，主要應用于多元空間關鍵資料的近鄰查找(Nearest Neighbor)和近似最近鄰查找(Approximate Nearest Neighbor)。
一、Kd-tree
其實KDTree就是二叉查找樹（Binary Search Tree，BST）的變種。二叉查找樹的性質如下：
1）若它的左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值；
2）若它的右子樹不為空，則右子樹上所有結點的值均大于它的根結點的值；
3）它的左、右子樹也分别為二叉排序樹；
例如：
如果我們要處理的對象集合是一個K維空間中的資料集，我們首先需要确定是：怎樣将一個K維資料劃分到左子樹或右子樹？
在構造1維BST樹類似，隻不過對于Kd樹，在目前節點的比較并不是通過對K維資料進行整體的比較，而是選擇某一個次元d，然後比較兩個K維資料在該次元 d上的大小關系，即每次選擇一個次元d來對K維資料進行劃分，相當于用一個垂直于該次元d的超平面将K維資料空間一分為二，平面一邊的所有K維資料 在d次元上的值小于平面另一邊的所有K維資料對應次元上的值。也就是說，我們每選擇一個次元進行如上的劃分，就會将K維資料空間劃分為兩個部分，如果我 們繼續分别對這兩個子K維空間進行如上的劃分，又會得到新的子空間，對新的子空間又繼續劃分，重複以上過程直到每個子空間都不能再劃分為止。以上就是構造 Kd-Tree的過程，上述過程中涉及到兩個重要的問題：
- 每次對子空間的劃分時，怎樣确定在哪個次元上進行劃分；
- 在某個次元上進行劃分時，怎樣確定建立的樹盡量地平衡，樹越平衡代表着分割得越平均，搜尋的時間也就是越少。
1、在哪個次元上進行劃分？
一種選取軸點的政策是median of the most spread dimension pivoting strategy，統計樣本在每個次元上的資料方差，挑選出對應方差最大值的那個次元。資料方差大說明沿該坐标軸方向上資料點分散的比較開。這個方向上，進行資料分割可以獲得最好的平衡。
2、怎樣確定建立的樹盡量地平衡？
給定一個數組，怎樣才能得到兩個子數組，這兩個數組包含的元素 個數差不多且其中一個子數組中的元素值都小于另一個子數組呢？方法很簡單，找到數組中的中值（即中位數，median），然後将數組中所有元素與中值進行 比較，就可以得到上述兩個子數組。同樣，在次元d上進行劃分時，劃分點（pivot）就選擇該次元d上所有資料的中值，這樣得到的兩個子集合資料個數就基本相同了。
二、Kd-Tree的建構
1）、在K維資料集合中選擇具有最大方差的次元k，然後在該次元上選擇中值m為pivot對該資料集合進行劃分，得到兩個子集合；同時建立一個樹結點node，用于存儲；
2）、對兩個子集合重複（1）步驟的過程，直至所有子集合都不能再劃分為止；
舉個例子：
假設有6個二維資料點{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，資料點位于二維空間内（如下圖中黑點所示）。kd樹算法就是要确定圖1中這些分割空間的分割線（多元空間即為分割平面，一般為超平面）。下面就要通過一步步展示kd樹是如何确定這些分割線的。
- 分别計算x，y方向上資料的方差，得知x方向上的方差最大；
- 根據x軸方向的值2,5,9,4,8,7排序選出中值為7，是以該node中的data = （7,2）。這樣，該節點的分割超平面就是通過（7,2）并垂直于x軸的直線x = 7；
- 确定左子空間和右子空間。分割超平面x = 7将整個空間分為兩部分，如下圖所示。x < = 7的部分為左子空間，包含3個節點{（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節點{（9,6），（8,1）}。 k-d樹的建構是一個遞歸的過程。然後對左子空間和右子空間内的資料重複根節點的過程就可以得到下一級子節點（5,4）和（9,6）（也就是左右子空間的'根'節點），同時将空間和資料集進一步細分。如此反複直到空間中隻包含一個資料點，如下圖所示：
Kd Tree算法詳解 Kd Tree算法詳解
三、Kd-Tree的最近鄰查找
-
（1）将查詢資料Q從根結點開始，按照Q與各個結點的比較結果向下通路Kd-Tree，直至達到葉子結點。
其中Q與結點的比較指的是将Q對應于結點中的k次元上的值與中值m進行比較，若Q(k) < m，則通路左子樹，否則通路右子樹。達到葉子結點時，計算Q與葉子結點上儲存的資料之間的距離，記錄下最小距離對應的資料點，記為目前最近鄰點nearest和最小距離dis。
-
（2）進行回溯操作，該操作是為了找到離Q更近的“最近鄰點”。即判斷未被通路過的分支裡是否還有離Q更近的點，它們之間的距離小于dis。
如果Q與其父結點下的未被通路過的分支之間的距離小于dis，則認為該分支中存在離P更近的資料，進入該結點，進行（1）步驟一樣的查找過程，如果找到更近的資料點，則更新為目前的最近鄰點nearest，并更新dis。
如果Q與其父結點下的未被通路過的分支之間的距離大于dis，則說明該分支内不存在與Q更近的點。
回溯的判斷過程是從下往上進行的，直到回溯到根結點時已經不存在與P更近的分支為止。
注：判斷未被通路過的樹分支中是否還有離Q更近的點，就是判斷"Q與未被通路的樹分支的距離|Q(k) - m|"是否小于"Q到目前的最近鄰點nearest的距離dis"。從幾何空間上來看，就是判斷以Q為中心，以dis為半徑超球面是否與未被通路的樹分支代表的超矩形相交。
下面舉兩個例子來示範一下最近鄰查找的過程。
假設我們的kd樹就是上面通過樣本集{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}建立的。
例1：查找點Q(2.1,3.1)
如下圖所示，紅色的點即為要查找的點。通過圖4二叉搜尋，順着搜尋路徑很快就能找到目前的最鄰近點（2,3）。
在上述搜尋過程中，産生的搜尋路徑節點有<（7,2），（5,4），（2,3）>。為了找到真正的最近鄰，還需要進行'回溯'操作，首先以（2,3）作為目前最近鄰點nearest，計算其到查詢點Q（2.1,3.1）的距離dis為0.1414，然後回溯到其父節點（5,4），并判斷在該父節點的其他子節點空間中是否有距離查詢點Q更近的資料點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如圖6所示。發現該圓并不和超平面y = 4交割，即這裡：|Q(k) - m|=|3.1 - 4|=0.9 > 0.1414，是以不用進入（5,4）節點右子空間中去搜尋。
再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，是以不用進入（7,2）右子空間進行查找。至此，搜尋路徑中的節點已經全部回溯完，結束整個搜尋，傳回最近鄰點（2,3），最近距離為0.1414。
例2：查找點Q(2,4.5)
如下圖所示，同樣經過圖4的二叉搜尋，可得目前的最鄰近點（4,7），産生的搜尋路徑節點有<（7,2），（5,4），（4,7）>。首先以（4,7）作為目前最近鄰點nearest，計算其到查詢點Q（2,4.5）的距離dis為3.202，然後回溯到其父節點（5,4），并判斷在該父節點的其他子節點空間中是否有距離查詢點Q更近的資料點。以（2,4.5）為圓心，以為3.202為半徑畫圓，如圖7所示。發現該圓和超平面y = 4交割，即這裡：|Q(k) - m|=|4.5 - 4|=0.5 < 3.202，是以進入（5,4）節點右子空間中去搜尋。是以，将(2,3)加入到搜尋路徑中，現在搜尋路徑節點有<(7,2), (2, 3)>。同時，注意：點Q(2,4.5)與父節點(5,4)的距離也要考慮，由于這兩點間的距離3.04 < 3.202，是以将(5,4)賦給nearest，并且dist=3.04。
接下來，回溯至（2,3）葉子節點，點Q（2,4.5）和（2,3）的距離為1.5，比距離（5,4）要近，是以最近鄰點nearest更新為(2,3)，最近距離dis更新為1.5。回溯至（7,2），如圖8所示，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，即這裡：|Q(k) - m|=|2 - 7|=5 > 1.5。至此，搜尋路徑回溯完。傳回最近鄰點（2,3），最近距離1.5。
四、總結
Kd樹在次元較小時（比如20、30），算法的查找效率很高，然而當資料次元增大（例如：K≥100），查找效率會随着次元的增加而迅速下降。假設資料集的維數為D，一般來說要求資料的規模N滿足N>>2的D次方，才能達到高效的搜尋。
為了能夠讓Kd樹滿足對高維資料的索引，Jeffrey S. Beis和David G. Lowe提出了一種改進算法——Kd-tree with BBF（Best Bin First），該算法能夠實作近似K近鄰的快速搜尋，在保證一定查找精度的前提下使得查找速度較快。