空間索引技術的核心是：根據搜尋條件，比如一個矩形，迅速找到與該矩形相交的所有空間對象集合。當資料量巨大，矩形框相對于全圖很小時，這個集合相對于全圖資料集大為縮小，在這個縮小的集合上再處理各種複雜的搜尋，效率就會大大提高。
(1)、四叉樹索引
四叉樹索引的基本思想是将地理空間遞歸劃分為不同層次的樹結構。它将已知範圍的空間等分成四個相等的子空間，如此遞歸下去，直至樹的層次達到一定深度或者滿足某種要求後停止分割。四叉樹的結構比較簡單，并且當空間資料對象分布比較均勻時，具有比較高的空間資料插入和查詢效率，是以四叉樹是GIS中常用的空間索引之一。
四叉樹對于區域查詢，效率比較高。但如果空間對象分布不均勻，随着地理空間對象的不斷插入，四叉樹的層次會不斷地加深，将形成一棵嚴重不平衡的四叉樹，那麼每次查詢的深度将大大的增多，進而導緻查詢效率的急劇下降。
(1)四分區域辨別
分别定義了一個平面區域的四個子區域索引号，右上為第一象限0，左上為第二象限1，左下為第三象限2，右下為第四象限3。
typedef enum
{
UR = 0,// UR第一象限
UL = 1, // UL為第二象限
LL = 2, // LL為第三象限
LR = 3 // LR為第四象限
}QuadrantEnum;
(2)空間對象資料結構
空間對象資料結構是對地理空間對象的近似，在空間索引中，相當一部分都是采用MBR作為近似。
/*空間對象MBR資訊*/
typedef struct SHPMBRInfo
{
int nID; //空間對象ID号
MapRect Box; //空間對象MBR範圍坐标
}SHPMBRInfo;
nID是空間對象的辨別号，Box是空間對象的最小外包矩形（MBR）。
(3)四叉樹節點資料結構
四叉樹節點是四叉樹結構的主要組成部分，主要用于存儲空間對象的辨別号和MBR，也是四叉樹算法操作的主要部分。
/*四叉樹節點類型結構*/
typedef struct QuadNode
{
MapRect Box; //節點所代表的矩形區域
int nShpCount; //節點所包含的所有空間對象個數
SHPMBRInfo* pShapeObj; //空間對象指針數組
int nChildCount; //子節點個數
QuadNode *children[4]; //指向節點的四個孩子
}QuadNode;
Box
是代表四叉樹對應區域的最小外包矩形，上一層的節點的最小外包矩形包含下一層最小外包矩形區域；
nShpCount
代表本節點包含的空間對象的個數；
pShapeObj
代表指向空間對象存儲位址的首位址，同一個節點的空間對象在記憶體中連續存儲；
nChildCount
代表節點擁有的子節點的數目；
children
是指向孩子節點指針的數組。
JST 四叉樹實作原理
com.vividsolutions.jts.index.quadtree.Quadtree
A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of spatial objects need to be indexed they can be represented by their envelopes
quadtree structure is used to provide a primary filter for range rectangle queries. The query() method returns a list of all objects which may intersect the query rectangle. Note that it may return objects which do not in fact intersect.
四叉樹的空間索引結構的二維矩形的高效查詢。如果其他類型的空間對象需要被索引他們可以通過自己的最小外包矩形來表示
四叉樹結構是用來提供一個初級過濾器為矩形範圍查詢。在query（）方法傳回一個可以相交的查詢區域内的所有對象的清單。請注意，它可能會傳回其實不相交的對象。
eg:
public class QuadTreeDemo {
private Quadtree quadTree = new Quadtree();
public void buildQuadTree(){
Envelope enve = new Envelope(0, 1, 0, 1);
Envelope enve1 = new Envelope(0, 1, 0, -1);
Envelope enve2 = new Envelope(0, -2, 0, 2);
Envelope enve3 = new Envelope(0, -3, 0, -3);
quadTree.insert(enve, "first");
quadTree.insert(enve1, "second");
quadTree.insert(enve2, "third");
quadTree.insert(enve3, "fourth");
}
public void query(Envelope enve){
List<String> StrList = quadTree.query(enve);
for(String str:StrList) {
System.out.println(str);
}
}
public static void main(String[] args) {
QuadTreeDemo qd = new QuadTreeDemo();
qd.buildQuadTree();
Envelope enve = new Envelope(0.1, 0.5, 0.1, 0.5);
qd.query(enve);
System.out.println("------分割線--------");
Envelope enve1 = new Envelope(0.5, 0.5, 0.5, -0.5);
qd.query(enve1);
}
} 輸出結果：
first
------分割線--------
second
first
(2)、K-d樹索引
k-d樹（k-dimensional樹的簡稱），是一種分割k維資料空間的資料結構。主要應用于多元空間關鍵資料的搜尋（如：範圍搜尋和最近鄰搜尋）。
k-d樹是一個二叉樹，每個節點表示一個空間範圍。表1給出的是k-d樹每個節點中主要包含的資料結構。
| 域名 | 資料類型 | 描述 |
| Node-data | 資料矢量 | 資料集中某個資料點，是n維矢量（這裡也就是k維） |
| Range | 空間矢量 | 該節點所代表的空間範圍 |
| split | 整數 | 垂直于分割超平面的方向軸序号 |
| Left | k-d樹 | 由位于該節點分割超平面左子空間内所有資料點所構成的k-d樹 |
| Right | k-d樹 | 由位于該節點分割超平面右子空間内所有資料點所構成的k-d樹 |
| parent | k-d樹 | 父節點 |
表1 k-d樹中每個節點的資料類型
以上述舉的執行個體來看，過程如下：
由于此例簡單，資料次元隻有2維，是以可以簡單地給x，y兩個方向軸編号為0,1，也即split={0,1}。
（1）确定split域的首先該取的值。分别計算x，y方向上資料的方差得知x方向上的方差最大，是以split域值首先取0，也就是x軸方向；
（2）确定Node-data的域值。根據x軸方向的值2,5,9,4,8,7排序選出中值為7，是以Node-data = （7,2）。這樣，該節點的分割超平面就是通過（7,2）并垂直于split = 0（x軸）的直線x = 7；
（3）确定左子空間和右子空間。分割超平面x = 7将整個空間分為兩部分，如圖2所示。x < = 7的部分為左子空間，包含3個節點{（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節點{（9,6），（8,1）}。
如算法所述，k-d樹的建構是一個遞歸的過程。然後對左子空間和右子空間内的資料重複根節點的過程就可以得到下一級子節點（5,4）和（9,6）（也就是左右子空間的'根'節點），同時将空間和資料集進一步細分。如此反複直到空間中隻包含一個資料點，如圖1所示。最後生成的k-d樹如圖3所示。
JST KD樹實作原理
com.vividsolutions.jts.index.kdtree.KdTree
An implementation of a 2 - D KD- Tree. KD -trees provide fast range searching on point data.
This implementation supports detecting and snapping points which are closer than a given
tolerance value. If the same point (up to tolerance) is inserted more than once a new node is
not created but the count of the existing node is incremented.
一個實作了二維的KD-tree。 KD-樹提供快速搜尋範圍點上的資料。
public class KDTreeDemo {
private KdTree kdTree = new KdTree();
public void builKDTree(){
Coordinate p1 = new Coordinate(0,0);
Coordinate p2 = new Coordinate(1,1);
Coordinate p3 = new Coordinate(2,2);
Coordinate p4 = new Coordinate(3,3);
Coordinate p5 = new Coordinate(4,4);
Coordinate p6 = new Coordinate(5,5);
kdTree.insert(p1, "first");
kdTree.insert(p2, "second");
kdTree.insert(p3, "third");
kdTree.insert(p4, "fourth");
kdTree.insert(p5, "Fifth");
kdTree.insert(p6, "Sixth");
}
public void query(Envelope enve){
List<KdNode> StrList = kdTree.query(enve);
for(KdNode node:StrList) {
System.out.println(node.getData());
}
}
public static void main(String[] args) {
KDTreeDemo kd = new KDTreeDemo();
kd.builKDTree();
Envelope enve = new Envelope(-1,2,-1,2);
kd.query(enve);
System.out.println("------分割線--------");
Envelope enve1 = new Envelope(2, 4, 2, 4);
kd.query(enve1);
}
} 輸出結果：
first
second
third
------分割線--------
third
fourth
Fifth
(3)、R-Tree 索引
R樹是一棵平衡樹。樹上有兩類結點：葉子結點和非葉子結點。每一個結點由若幹個索引項構成。對于葉子結點，索引項形如(Index，Obj_ID)。其中，Index表示包圍空間資料對象的最小外接矩形MBR，Obj_ID辨別一個空間資料對象。對于一個非葉子結點，它的索引項形如(Index，Child_Pointer)。 Child_Pointer 指向該結點的子結點。Index仍指一個矩形區域，該矩形區域包圍了子結點上所有索引項MBR的最小矩形區域。
搜尋算法：
記R樹的根節點記為T。搜尋算法要求輸入一個搜尋矩形S，輸出所有與S相交的索引記錄。
步驟S1：搜尋子樹——如果T不是一個葉節點，則檢查其中的每一個條目E，如果EI與S相交，則對Ep所指向的那個子樹根節點調用Search算法。這裡注意，Search算法接收的輸入為一個根節點，是以在描述算法的時候，原文稱對子樹根節點調用Search算法，而不是對子樹調用Search算法。
步驟S2：搜尋葉節點——如果T是一個葉節點，則檢查其中的每個條目E，如果EI與S相交，則E就是需要傳回的檢索結果之一。
JTS R-Tree 樹實作原理
分兩種樹：STRtree和SIRtree
com.vividsolutions.jts.index.strtree.STRtree
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatial data.The STR packed R-tree is simple to implement and maximizes space utilization;
查詢指R樹采用排序 - 壓縮 - 遞歸（STR）算法建立的。為二維空間data.The STR壓縮的R-樹是實作簡單并且最大化空間使用率
eg：
public class STRtreeDemo {
private STRtree strTree = new STRtree();
private GeometryFactory gf = new GeometryFactory();
public LineString createLineByWKT(String lineStr)throws ParseException{
WKTReader reader = new WKTReader(gf);
LineString line = (LineString) reader.read(lineStr);
return line;
}
public void buildStrTree() throws ParseException{
strTree.insert(createLineByWKT("LineString(1 1, 2 2,3 0,6 10)").getEnvelopeInternal(), "first");
strTree.insert(createLineByWKT("LineString(0 0, 2 0)").getEnvelopeInternal(), "second");
strTree.insert(createLineByWKT("LineString(-1 1, 2 0)").getEnvelopeInternal(), "third");
strTree.insert(createLineByWKT("LineString(-1 -1, -2 -2)").getEnvelopeInternal(), "fourth");
}
public void query(Envelope enve){
List<String> StrList = strTree.query(enve);
for(String str:StrList) {
System.out.println(str);
}
}
public static void main(String[] args) throws ParseException {
STRtreeDemo qd = new STRtreeDemo();
qd.buildStrTree();
Envelope enve = new Envelope(1, 1.5, 1, 1.5);
qd.query(enve);
System.out.println("------分割線--------");
Envelope enve1 = new Envelope(0.5, 0.5, 0.5, -0.5);
qd.query(enve1);
}
} 輸出結果：
third
first
------分割線--------
second
third
com.vividsolutions.jts.index.strtree.SIRtree
One-dimensional version of an STR-packed R-tree. SIR stands for
"Sort-Interval-Recursive".
一維版本的STR-壓縮的R-樹