1. 概述

KD樹是一種查詢索引結(jié)構(gòu)，廣泛應(yīng)用于數(shù)據(jù)庫索引中愕掏。從概念的角度講度秘，它是一種高緯數(shù)據(jù)的快速查詢結(jié)構(gòu)，本文首先介紹1維數(shù)據(jù)的索引查詢饵撑，然后介紹2維KD樹的創(chuàng)建和查詢剑梳，相關(guān)定理和推論也簡單列出，本文爭取用15分鐘的時(shí)間滑潘，讓大家快速理解KD樹垢乙。

2. 1維數(shù)據(jù)的查詢

假設(shè)在數(shù)據(jù)庫的表格T中存儲(chǔ)了學(xué)生的語文成績chinese、數(shù)學(xué)成績math语卤、英語成績english追逮，如果要查詢語文成績介于30～93分的學(xué)生，如何處理粹舵？假設(shè)學(xué)生數(shù)量為N钮孵，如果順序查詢，則其時(shí)間復(fù)雜度為O(N)眼滤，當(dāng)學(xué)生規(guī)模很大時(shí)巴席，其效率顯然很低，如果使用平衡二叉樹诅需，則其時(shí)間復(fù)雜度為O(logN)漾唉，能極大地提高查詢效率。平衡二叉樹示意圖為：

圖1：平衡二叉樹示意圖

對(duì)于1維數(shù)據(jù)的查詢堰塌，使用平衡二叉樹建立索引即可赵刑。如果現(xiàn)在將查詢條件變?yōu)椋赫Z文成績介于30～93，數(shù)學(xué)成績結(jié)余30～90蔫仙，又該如何處理呢料睛？

如果分別使用平衡二叉樹對(duì)語文成績和數(shù)學(xué)成績建立索引，則需要先在語文成績中查詢得到集合S₁摇邦，再在數(shù)學(xué)成績中查詢得到集合S₂恤煞，然后計(jì)算S₁和S₂的交集，若|S₁|=m,|S₂|=n施籍，則其時(shí)間復(fù)雜度為O(m*n)居扒，有沒有更好的辦法呢？

3. KD樹

針對(duì)多維數(shù)據(jù)索引丑慎，是否也存在類似的一維的索引方法呢喜喂？先看2維數(shù)據(jù)的集合示意圖：

圖2: 2維數(shù)據(jù)示意圖

如果先根據(jù)語文成績瓤摧，將所有人的成績分成兩半，其中一半的語文成績<=c₁玉吁，另一半的語文成績>c₁照弥，分別得到集合S₁,S₂;然后針對(duì)S₁，根據(jù)數(shù)學(xué)成績分為兩半进副，其中一半的數(shù)學(xué)成績<=m₁,另一半的數(shù)學(xué)成績>m₁这揣，分別得到S₃,S₄，針對(duì)S₂影斑，根據(jù)數(shù)學(xué)成績分為兩半给赞，其中一半的數(shù)學(xué)成績<=m₂,另一半的數(shù)學(xué)成績>m₂，分別得到S₅,S₆矫户；再根據(jù)語文成績分別對(duì)S₃,S₄片迅，S₅,S₆繼續(xù)執(zhí)行類似劃分得到更小的集合，然后再在更小的集合上根據(jù)數(shù)學(xué)成績繼續(xù),...

上面描述的就是構(gòu)建KD樹的基本思路皆辽，其構(gòu)建后的KD樹如下圖所示：

圖3: KD樹示意圖

如圖所示柑蛇，l1左邊都是語文成績低于45分，l1右邊都是語文成績高于45分的膳汪；l2下方都是語文成績低于45分且數(shù)學(xué)成績低于50分的唯蝶，l2上方都是語文成績低于45分且數(shù)學(xué)成績高于50分的，后面以此類推遗嗽。下面的圖示粘我，更清晰地表示了KD樹的結(jié)構(gòu)及其對(duì)應(yīng)的二叉樹：

圖4: KD樹及對(duì)應(yīng)的二叉樹

在了解了KD樹的基本原理后，剩下的工作就是如何構(gòu)建KD樹以及如何在KD樹上查詢了痹换。

3.1 KD樹構(gòu)建算法

相對(duì)而言征字，構(gòu)建KD樹是針對(duì)高維數(shù)據(jù)，需要針對(duì)每一維都進(jìn)行二分娇豫，針對(duì)二維數(shù)據(jù)的KD樹構(gòu)建算法如下圖5所示：

圖5:KD樹構(gòu)建算法

其中的P表示待構(gòu)建的元素集合匙姜，depth表示當(dāng)前是KD樹的第幾層，如果depth是偶數(shù)冯痢，通過縱向線對(duì)集合進(jìn)行劃分氮昧；如果depth是奇數(shù)，通過橫向線進(jìn)行劃分（3～5行）浦楣；第6袖肥、7行遞歸進(jìn)行KD樹中子樹的構(gòu)建。

圖5中的算法時(shí)間復(fù)雜度為：O(nlogn)振劳，感興趣的同學(xué)可以寫出遞推公式公式進(jìn)行推到椎组，算法導(dǎo)論中專門講了這個(gè)遞推公式。

3.2 KD樹查詢算法

在構(gòu)建了KD樹的基礎(chǔ)上历恐，如何進(jìn)行查詢其實(shí)是一個(gè)相對(duì)簡單的問題了寸癌，在這里需要注意的是专筷，在KD樹中每一層劃分所依據(jù)的是哪一維的數(shù)據(jù)，其它的根二叉樹其實(shí)沒有差別蒸苇。KD樹查詢算法如下圖所示：

圖6: 查詢算法

圖6中算法的v表示KD樹中當(dāng)前搜索的子樹磷蛹，R表示是一個(gè)高維數(shù)據(jù)的區(qū)域，區(qū)域的概念如圖7所示：

圖7: 區(qū)域示意圖

如果v是葉子結(jié)點(diǎn)且屬于區(qū)域R填渠，則直接返回（第1行）弦聂；如果v是非葉子結(jié)點(diǎn)鸟辅，則比較R與v的左子樹lc(v)是否有交集氛什，如果有且lc(v)完全被R覆蓋，則lc(v)是所查詢結(jié)果的一部分匪凉，如果不是完全覆蓋枪眉，則遞歸查詢lc(v)(3_{6行)；對(duì)右子樹也是類似的操作（7}10）再层。算法的時(shí)間復(fù)雜度為：O(sqrt(n) + k)贸铜，其中k是最后的結(jié)果中元素的個(gè)數(shù)，其遞推公式公式為：

圖8: KD樹查詢遞推公式

上述算法中的二維也可升級(jí)為3維聂受，其思維方式與從1維升級(jí)到2維一致蒿秦，相應(yīng)的構(gòu)建算法和查詢算法也與2維的一致，感興趣的童鞋可以分析相應(yīng)算法的時(shí)間復(fù)雜度蛋济。

4. 小結(jié)

本文以從1維數(shù)據(jù)索引跳變到2維數(shù)據(jù)索引的方式棍鳖，引出了KD樹，并介紹了KD樹的構(gòu)建與索引查詢算法碗旅。KD樹主要應(yīng)用在高維數(shù)據(jù)索引渡处，特別是空間數(shù)據(jù)庫的索引，x和y分別表示經(jīng)度和緯度祟辟，能較好的處理空間上的查詢效率問題医瘫，如果在x和y再加一個(gè)時(shí)間維度，也能較好地處理時(shí)空數(shù)據(jù)索引查詢旧困。