前言

基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)如二叉樹衍生的的平衡二叉搜索樹通過左旋右旋調(diào)整樹的平衡維護數(shù)據(jù)，靠著二分算法能滿足一維度數(shù)據(jù)的logN時間復(fù)雜度的近似搜索。對于大規(guī)模多維度數(shù)據(jù)近似搜索，Lucene采用一種BKD結(jié)構(gòu)，該結(jié)構(gòu)能很好的空間利用率和性能。

本片博客主要學(xué)習(xí)常見的多維數(shù)據(jù)搜索數(shù)據(jù)結(jié)構(gòu)、KD-Tree的構(gòu)建、搜索過程以針對高維度數(shù)據(jù)容災(zāi)的優(yōu)化的BBF算法，以及BKD結(jié)構(gòu)原理。

感受 算法之美 結(jié)構(gòu)之道 吧～

目錄

• 多維數(shù)據(jù)空間搜索結(jié)構(gòu)
  • KD-Tree
    • BSP樹和四叉樹的關(guān)系
    • KD-Tree和BSP的關(guān)系
    • KD-Tree的原理
    • KD-Tree搜索算法優(yōu)化之BBF算法
  • KD-B-Tree
• BKD-Tree

一、多維數(shù)據(jù)空間搜索結(jié)構(gòu)

BKD-Tree是基于KD-B-Tree改進而來，而KD-B-Tree又是KD-Tree和B+Tree的結(jié)合體，KD-Tree又是我們最熟悉的二叉查找樹BST(Binary Search Tree)在多維數(shù)據(jù)的自然擴展，它是BSP(Binary Space Partitioning)的一種。B+Tree又是對B-Tree的擴展。以下對這幾種樹的特點簡要描述。

1、KD-Tree

kd是K-Dimensional的所寫，k值表示維度，KD-Tree表示能處理K維數(shù)據(jù)的樹結(jié)構(gòu)，當(dāng)K為1的時候，就轉(zhuǎn)化為了BST結(jié)構(gòu)

維基百科：在計算機科學(xué)里，k-d樹（k-維樹的縮寫）是在k維歐幾里德空間組織點的數(shù)據(jù)結(jié)構(gòu)。k-d樹可以使用在多種應(yīng)用場合，如多維鍵值搜索（例：范圍搜尋及最鄰近搜索）。k-d樹是空間二分算法（binary space partitioning）的一種特殊情況。

首先看BSP，Binary space partitioning(BSP)是一種使用超平面遞歸劃分空間到凸集的一種方法。使用該方法劃分空間可以得到表示空間中對象的一個樹形數(shù)據(jù)結(jié)構(gòu)。這個樹形數(shù)據(jù)結(jié)構(gòu)被我們叫做BSP樹。

可以分為軸對齊、多邊形對齊BSP，這兩種方式就是選擇超平面的方式不一樣，已軸對齊BSP通過構(gòu)建過程簡單理解，就是選擇一個超平面，這個超平面是跟選取的軸垂直的一個平面，通過超平面將空間分為兩個子空間，然后遞歸劃分子空間。
空間劃分思想可以轉(zhuǎn)化為坐標點劃分，一般可以應(yīng)用在游戲中如物體定位等，比如二維空間的四叉樹和三維空間的八叉樹都是參考BSP劃分算法。

1.1、BSP樹和四叉樹的關(guān)系

BSP算法和四叉樹的關(guān)系

• BSP樹：BSP樹使用平面進行遞歸的二分劃分，將空間劃分為兩個子空間。每個節(jié)點要么是葉子節(jié)點（包含實際對象），要么是內(nèi)部節(jié)點（包含一個分割平面）。分割平面通常由空間中的一條直線表示。
• 四叉樹：四叉樹將空間劃分為四個象限，每個象限都是父節(jié)點的子節(jié)點。每個節(jié)點要么是葉子節(jié)點（包含實際對象），要么是內(nèi)部節(jié)點（包含四個子節(jié)點）。

四叉樹又分為點四叉樹和邊四叉樹，以邊四叉樹為例，具體的實現(xiàn)源碼參考：空間搜索優(yōu)化算法之——四叉樹 - 掘金

1.2、KD-Tree和BSP樹的關(guān)系

KD-Tree是一種特殊的BSP樹，它的特點有：

• 每一層都是一種劃分維度，而BSP劃分的維度為軸劃分、邊劃分，是同一維度的劃分。
• 每個節(jié)點代表垂直于當(dāng)前維度的超平面，將空間劃分為兩部分
• k維空間，按樹的每一層循環(huán)選取，當(dāng)前節(jié)點為i維，下一層節(jié)點為(i+1)%k維

KD 樹（KD-tree）和 BSP 樹（Binary Space Partitioning tree）都是用于空間劃分的數(shù)據(jù)結(jié)構(gòu)，但它們有一些關(guān)鍵的區(qū)別，這也是為什么 KD 樹被認為是 BSP 樹的一種特殊情況的原因之一。

1. 維度劃分方式不同：
   • KD 樹：KD 樹是針對 k 維空間的樹形數(shù)據(jù)結(jié)構(gòu)，它在每個節(jié)點上通過輪流選擇一個維度來劃分空間，例如在二維空間中，它可能在 x 軸上進行一次劃分，在 y 軸上進行下一次劃分，以此類推。因此，KD 樹在每一層都會選擇一個維度進行劃分。
   • BSP 樹：BSP 樹是一種二叉樹，每個節(jié)點都代表一個超平面（hyperplane），用于將空間劃分為兩個子空間。BSP 樹的劃分方式不一定是輪流選擇維度，而是根據(jù)一些準則（如最佳平面）選擇劃分的超平面。
2. 節(jié)點類型不同：
   • KD 樹：KD 樹的節(jié)點可以是葉節(jié)點，也可以是非葉節(jié)點。非葉節(jié)點表示一個劃分超平面，葉節(jié)點表示一個數(shù)據(jù)點。
   • BSP 樹：BSP 樹的每個節(jié)點都是一個劃分超平面，它沒有葉節(jié)點來表示數(shù)據(jù)點。
3. 適用場景不同：
   • KD 樹：KD 樹主要用于 k 維空間中的最近鄰搜索等問題，由于它在每個節(jié)點上都選擇一個維度進行劃分，因此在高維空間中可能會出現(xiàn)維度災(zāi)難（curse of dimensionality）的問題。
   • BSP 樹：BSP 樹更通用，可以用于任何維度的空間劃分，常用于圖形學(xué)中的空間分區(qū)和碰撞檢測等問題。

因此，雖然 KD 樹和 BSP 樹都是空間劃分的數(shù)據(jù)結(jié)構(gòu)，但由于它們的設(shè)計和應(yīng)用場景有所不同，KD 樹被認為是 BSP 樹的一種特殊情況。

下面是一個2維度的KD-tree，類似BST，只不過BST是一維的

先KD-Tree適宜處理多維數(shù)據(jù)，查詢效率較高。不難知道一個靜態(tài)多維數(shù)據(jù)集合建成KD-Tree后查詢時間復(fù)雜度是O（lgN)。所有節(jié)點都存儲了數(shù)據(jù)本身，導(dǎo)致索引數(shù)據(jù)的內(nèi)存利用不夠緊湊，相應(yīng)地數(shù)據(jù)磁盤存儲的空間利用不夠充分。
此外KD-Tree不適宜處理海量數(shù)據(jù)的動態(tài)更新。原因和B樹不適宜處理多維數(shù)據(jù)的動態(tài)更新的分析差不多，因為KD-Tree的分層劃分是依維度依次輪替進行的，動態(tài)更新后調(diào)整某個中間節(jié)點時，變更的當(dāng)前維度也同樣需要調(diào)整其全部子孫節(jié)點中的當(dāng)前維度值，導(dǎo)致對樹節(jié)點的訪問和操作增多，操作耗時增大。可見，KD-Tree更適宜處理的是靜態(tài)場景的多維海量數(shù)據(jù)的查詢操作。

1.3、KD-Tree和KNN算法的聯(lián)系

KNN算法的實現(xiàn)就可以采KD-Tree：https://blog.csdn.net/v_july_v/article/details/8203674，這篇博客寫的很詳細，KNN算法簡單理解就是給定一個測試元素，根據(jù)最靠近的K個元素判斷測試元素的分類，當(dāng)K=1的時候，就轉(zhuǎn)化成了最緊鄰算法，KD-Tree結(jié)構(gòu)是支持最緊鄰搜索的。

1.4、KD-Tree的原理

學(xué)習(xí)KD-Tree是如何構(gòu)建、查詢、刪除元素的，使用Java實現(xiàn)一個簡單二維的KD-Tree結(jié)構(gòu)，實現(xiàn)尋找最近的n個點。

package org.example.kdtree;

import java.util.ArrayList;
import java.util.List;


/**
 * @author sichaolong
 * @createdate 2024/3/14 14:19
 */

class KDNode {
    int[] point;
    KDNode left;
    KDNode right;

    public KDNode(int[] point) {
        this.point = point;
        this.left = null;
        this.right = null;
    }
}

public class SimpleKDTreeDemo {
    private KDNode root;

    public SimpleKDTreeDemo() {
        this.root = null;
    }

    public void insert(int[] point) {
        this.root = insertNode(this.root, point, 0);
    }

    private KDNode insertNode(KDNode node, int[] point, int depth) {
        if (node == null) {
            return new KDNode(point);
        }

        int k = point.length;

        // 選定切割軸
        int axis = depth % k;

        if (point[axis] < node.point[axis]) {
            node.left = insertNode(node.left, point, depth + 1);
        } else {
            node.right = insertNode(node.right, point, depth + 1);
        }

        return node;
    }

    public List<int[]> search(int[] target, int n) {
        List<int[]> result = new ArrayList<>();
        searchNode(this.root, target, 0, n, result);
        return result;
    }

    private void searchNode(KDNode node, int[] target, int depth, int k, List<int[]> result) {
        if (node == null) {
            return;
        }

        // 確定當(dāng)前層的切割維度
        int axis = depth % k;

        if (target[axis] < node.point[axis]) {
            searchNode(node.left, target, depth + 1, k, result);
        } else {
            searchNode(node.right, target, depth + 1, k, result);
        }

        // 還沒找夠n個，就直接添加
        if (result.size() < k) {
            result.add(node.point);
        } else {
            // 上一個最近的點
            int[] farthestPoint = result.get(result.size() - 1);
            // 如果當(dāng)前點距離更近，就替換
            if (distance(target, node.point) < distance(target, farthestPoint)) {
                result.remove(result.size() - 1);
                result.add(node.point);
            }
        }

        // 如果切割軸距離更近，就添加
        int[] farthestPoint = result.get(result.size() - 1);
        // 切割軸距離
        double splitDistance = Math.abs(target[axis] - node.point[axis]);
        // 切割軸距離更近
        if (splitDistance < distance(target, farthestPoint)) {
            if (target[axis] < node.point[axis]) {
                searchNode(node.right, target, depth + 1, k, result);
            } else {
                searchNode(node.left, target, depth + 1, k, result);
            }
        }
    }

    // 歐式距離
    private double distance(int[] point1, int[] point2) {
        int k = point1.length;
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += Math.pow(point1[i] - point2[i], 2);
        }
        return Math.sqrt(sum);
    }

    public static void main(String[] args) {
        SimpleKDTreeDemo kdTree = new SimpleKDTreeDemo();
        int[][] points = {{2, 3}, {5, 4}, {9, 6}, {4, 7}, {8, 1}, {7, 2}};
        for (int[] point : points) {
            kdTree.insert(point);
        }

        int[] target = {6, 3};
        int n = 2;

        // 找出最近的n個點
        List<int[]> result = kdTree.search(target, n);
        System.out.println("The " + n + " nearest neighbors to the target point " + java.util.Arrays.toString(target) + " are:");
        for (int[] point : result) {
            System.out.println(java.util.Arrays.toString(point));
        }
    }
}

構(gòu)建

樹的構(gòu)建就是依靠遞歸，對于KD-Tree的構(gòu)建步驟

1. 根據(jù)元素各個維度的方差，確定split域作為劃分左、右子樹的邊界
2. 確定當(dāng)前層的根結(jié)點，一般是取中間值
3. 劃分左右子樹

舉例KD-Tree的構(gòu)建過程， 6個二維數(shù)據(jù)點{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}構(gòu)建kd樹的具體步驟為：

1. 計算x維度的方差為1.24，y維度的方差為0.83，選定split域為x維度，方差的計算公式
2. 確定當(dāng)前層的根結(jié)點為（7，2），經(jīng)過該點垂直于split域的平面為 分割超平面
3. 左子樹為（2，3）、（5，4）、（4，7），右子樹為（9，6）、（8，1）

然后遞歸的交替使用x、y維度繼續(xù)構(gòu)建左、右子樹，最終的結(jié)果，奇數(shù)層split域為x，偶數(shù)層為y。

使用x、y坐標軸表示KD-Tree

ps：上面的代碼并沒第一步，首次插入的節(jié)點被定為根節(jié)點

搜索

查詢最緊鄰的點，二維KD-Tree不像BST那樣，因為按照維度分層，找到的葉子節(jié)點不一定是最緊鄰的點，需要回溯，回溯到上一層父節(jié)點，查找父節(jié)點的其他子空間（分割平面劃分的另外一個空間）是否可能有更近的點，依據(jù)就是以當(dāng)前點為圓心，最近的距離為半徑畫圓，判斷是否可能有其他點在圓內(nèi)（判斷的依據(jù)就是圓是否觸達分割平面，是否包含其他點），距離度量同樣使用歐式距離。

搜索過程，如果點是隨機分布的，那么搜索的時間復(fù)雜度為O(lgN)，巧妙的地方就是回溯直接取棧元素就行

1. 從根節(jié)點遞歸的向下搜索，各維度交替向左、右子樹搜索。
2. 找到葉子節(jié)點，計算距離，記錄為臨時最近距離以及臨時最近節(jié)點target point，因為葉子節(jié)點不一定是最緊鄰的點。
3. 回溯
   1. 回溯的父節(jié)點到搜索節(jié)點距離是否小于 臨時最近距離，如果小于，更新臨時target point。
   2. 臨時最近節(jié)點target point為圓點，臨時最近距離為r畫圓，圓是否和其他維度域分割平面相交，如果相交，需要搜索其他維度區(qū)域（假如當(dāng)前進入的是root的左子樹，本來不應(yīng)該搜索右子樹的，但是圓和其他維度空間相交就又可能其他空間有更近的點，需要搜索計算距離和臨時最近點比較）
4. 回溯到根節(jié)點，找到最鄰近節(jié)點。

舉例，搜索（2.2，3.2）最緊鄰的點

1. 首先從根結(jié)點（7，2）出發(fā)搜索，首先按照x維度為split域，進入左子樹（5，4）
2. 接著按照y維度為split域名，進入左子樹（2，3），找到了葉子節(jié)點（2，3），計算歐式距離為0.1414，計算父節(jié)點（5，4）距離為2.91 > 0.1414，因此目前target點（2，3）最近距離為0.1414。
3. 回溯判斷
   1. 回溯到（5，4）按照（2.1，3.1）以0.1414為半徑畫圓，發(fā)現(xiàn)和y = 4這條分割域平面無交點，繼續(xù)回溯，
   2. 回溯到（7，2）按照（2.1，3.1）以0.1414為半徑畫圓，發(fā)現(xiàn)和x = 7這條分割域平面無交點，至此回溯結(jié)束。
4. 找到最鄰近的點為（2，3），最近距離為0.1414

舉例，搜索（2，4.5）最緊鄰的點

1. 首先從根結(jié)點（7，2）出發(fā)搜索，首先按照x維度為split域，進入左子樹（5，4）
2. 接著按照y維度為split域名，進入右子樹（4，7），找到了葉子節(jié)點（4，7），計算歐式距離為3.202，計算父節(jié)點（5，4）距離為3.04 < 3.202，因此目前target點（5，4）最近距離為3.04。
3. 回溯判斷
   1. 回溯到（5，4）按照（2，4.5）以3.04為半徑畫圓，發(fā)現(xiàn)與y = 4這條分割域平面有交交點，所以需要搜索（5，4）的左空間（2，3），計算（2，3）距離（2，4.5）為1.5 < 3.04，因此目前target點（2，3）最近距離為1.5。
   2. 回溯到（7，2）按照（2，4.5）以半徑1.5畫圓，發(fā)現(xiàn)不和x = 7 這條分割域平面有交交點，至此回溯結(jié)束。
4. 找到最鄰近的點（2，3），最近距離為1.5。

上面兩個demo證明葉子節(jié)點不一定是最緊鄰的target節(jié)點，需要以當(dāng)前葉子節(jié)點（temp target節(jié)點） 和 搜素節(jié)點 的歐式距離為r畫圓，看圓是否和某個split域平面相交，如果相交，還需要去相交域接著找是否存在更緊鄰的點，下面就是遞歸，直到圓和域切割面不在相交，最緊鄰的target才找到。

一般來說，葉子節(jié)點只需要找?guī)讉€即可

但是當(dāng)點分布的比較糟糕，就需要遞歸查找很多域，因此當(dāng)維數(shù)比較多的時候，KD-Tree樹的性能會迅速下降，一般數(shù)據(jù)規(guī)模 N >> K平方 才能發(fā)揮比較不錯的性能，比如100個2維度的點，其中 100 遠遠大于 2*2；實驗結(jié)果表明當(dāng)特征空間的維數(shù)超過20 的時候容易線形災(zāi)難。

1.5、KD-Tree搜索算法優(yōu)化之BBF算法

BBF（Best-Bin-First）查詢算法，它是由發(fā)明sift算法的David Lowe在1997的一篇文章中針對高維數(shù)據(jù)提出的一種近似算法，此算法能確保優(yōu)先檢索包含最近鄰點可能性較高的空間，此外，BBF機制還設(shè)置了一個運行超時限定。采用了BBF查詢機制后，kd樹便可以有效的擴展到高維數(shù)據(jù)集上。

上述的KD-Tree搜索過程得知，搜索回溯是有查詢路徑?jīng)Q定的，查詢的路徑并沒有考慮到數(shù)據(jù)本身的一些性質(zhì)，減少回溯到其他區(qū)域空間的次數(shù)，就能一定程度降低搜索計算次數(shù)，一個改進的思路就是對數(shù)據(jù)做一些處理，便于搜素的路徑可控，如按各自分割超平面（也稱bin）與查詢點的距離排序，也就是說，回溯檢查總是從優(yōu)先級最高（Best Bin）的樹結(jié)點開始。

對于BBF算法，就是把回溯的棧換成了有序的優(yōu)先隊列，然后按照優(yōu)先隊列里面的子樹進行遞歸。

• 首先是為每一層的節(jié)點排個優(yōu)先級，也就是各個節(jié)點到當(dāng)前層計算維度軸的距離，記為abs(q[i]-v)，i為當(dāng)前所選維度，v為到維度軸的距離。
• 搜索節(jié)點的時候，使用優(yōu)先隊列記錄那些同層未被選擇的兄弟節(jié)點，或者表兄弟節(jié)點。只有搜索到葉子節(jié)點才會回溯，才從優(yōu)先隊列取節(jié)點，回溯的時候直接從優(yōu)先隊列找，此時找到的基本上是理論最近點。然后遞歸更新找到的最緊鄰的點，直到優(yōu)先隊列為空。
• 找到最緊鄰的點。

舉例，還是以上面搜索（2，4.5）最緊鄰的點

1. 首先將根節(jié)點放入優(yōu)先隊列。
2. 首先從根結(jié)點（7，2）出發(fā)搜索，首先按照x維度為split域，進入左子樹（5，4），此時把右子樹根節(jié)點（9，6）放入優(yōu)先隊列，此時隊列頂元素為（7，2）
3. 接著按照y維度為split域名，進入右子樹（4，7），將左子樹根節(jié)點（2，3）放入優(yōu)先隊列，此時隊列元素有{（2，3）、（7，2），（5，4）}，優(yōu)先隊列隊頂元素為（5，4）。找到了葉子節(jié)點（4，7），計算歐式距離為3.202，計算父節(jié)點（5，4）距離為3.04 < 3.202，因此目前target點（5，4）最近距離為3.04。
4. 回溯判斷：提取優(yōu)先隊列隊頂元素（2,3），重復(fù)步驟2，直到優(yōu)先隊列為空。
5. 找到最鄰近的點（2，3），最近距離為1.5。

ps：針對KD-Tree結(jié)構(gòu)存在的問題，還有很多優(yōu)化的數(shù)據(jù)結(jié)構(gòu)如球樹、R樹、VP樹、MVP樹。

球樹簡單理解就是不在像KD-Tree使用split域?qū)⒄麄€空間分割成一個個矩形，而是分成了一個個圓形，這樣可以很好的處理KD-Tree不能很好的處理位于舉矩形空間角落的點。

VP樹又叫至高樹，而在vpt中，首先從節(jié)點中選擇一個數(shù)據(jù)點（可隨機選）作為制高點（vp），然后算出其它點到vp的距離大小，最后根據(jù)該距離大小將數(shù)據(jù)點均分為二，遞歸建樹。

R樹：https://zh.wikipedia.org/wiki/R%E6%A0%91

2、KD-B-Tree

KD-B-Tree（K-Dimension-Balanced-Tree）顧名思義，結(jié)合了KD-Tree和B+Tree。它主要解決了KD-Tree的二叉樹形式樹高較高，對磁盤IO不夠友好的缺點，引入了B+樹的多叉樹形式，不僅降低了樹高，而且全部數(shù)據(jù)都存儲在葉子節(jié)點，增加了磁盤空間存儲利用率。一個KD-B-Tree結(jié)構(gòu)的示意圖如下。它同樣不適宜多維數(shù)據(jù)的動態(tài)更新場景，原因同KD-Tree一樣。

二、BKD-Tree

BKD-Tree(或BK-D-Tree,全稱是Block-K-Dimension-Tree )
在本文中，我們提出了一種新的索引結(jié)構(gòu)，稱為Bkd-tree，用于索引大型多維點數(shù)據(jù)集。 Bkdtree 是一種基于 kd-tree 的 I/O 高效動態(tài)數(shù)據(jù)結(jié)構(gòu)。我們提出了一項廣泛的實驗研究的結(jié)果，表明與之前將 kd-tree 的外部版本動態(tài)化的嘗試不同，Bkd-tree 保持了其高空間利用率和出色的性能。查詢和更新性能與對其執(zhí)行的更新數(shù)量無關(guān)。

// TODO文章來源地址http://www.zghlxwxcb.cn/news/detail-840020.html

參考

• kd-tree-維基百科
• 論文 Bkd-Tree: A Dynamic Scalable kd-Tree
• K-D樹、K-D-B樹、B-K-D樹
• 空間索引技術(shù)在58搜索中的落地實踐 – BKD技術(shù)原理深入剖析_ITPUB博客
• 從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法

到了這里，關(guān)于ElasticSearch學(xué)習(xí)篇10_Lucene數(shù)據(jù)存儲之BKD動態(tài)磁盤樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！