空间数据（spatial information）和传统的结构型数据以及非结构型的数据都有点不一样。空间数据虽然是有一定的结构性，但是其和非结构型数据一样难以按照结构型数据分析方法去操作。而像地图的测绘、定位算法、轨迹生成、轨迹分析，都是基于空间数据的dao层，因此从空间数据开始入门。
基本概念
bounding box：最基本的确定空间位置的方式：对于k维空间，确定该object在每个维度上的投影。
Spatial Selection：search region to find all objects requested by a query。
Spatial Join：search region to find all adjacent objects whose approximations intersect
spatial index： 这是一种类似字典的作用。目的是为了降低遍历的范围。
The object approximation：相似度是一种聚类方法。
空间索引的基本策略
单点索引方式
最基本的思路就是，对空间区域进行划分子区域，然后对子区域进行划分，直到区域不可划分为止。整体上是构成了一种树形结构。构成二叉树或者是哈希链表。这个比较好从信息论的角度去理解，例如索引一个4*4的像素平面，理论上是4个bit就可以存储的，因此索引的次数应该为4而不是16。二叉索引可以有一定的灵活性。例如可以对空间进行不规则划分。这里的一个问题是，为什么不采用原始的哈希索引，不管列表多大都是O（1）。解释如下：
- 空间上的索引如果是简单的哈希索引，其实最后对于使用数据而言并没有太大的意义，毕竟是一个一维空间到多维空间的map，map后的结果虽然可以保证一一映射，但是丧失了空间相关性信息。
- 单点的索引只是一个非常基础的方式，正常的object都不可能是单点的模式，对于非单点的索引来讲，更加难以去操作一个map后的索引表。
索引方式的分类
- The Transformation Approach：将KN维上的一个数据点转化为N维上的K个数据点。例如4维数据可以由两个2维数据表征。但是一般而言都是表征维4个一维数据点，通过二叉树构建索引
-
The Non-Overlapping（非重叠） Native Space Indexing Approach ：
（1）Object Duplication: 对整个空间去划分为不想交的子空间，所有的子空间要存每一个相交的object的id。
（2）Object Clipping:对每个object进行分解，每个分解的部门仅存一个子空间的索引。
问题是对于object重叠时，object duplication会受限了重叠数量。object clipping受限于object包含的子空间的数目。好处是point和object都可以用point存储空间信息。 - The Overlapping Native Space Indexing Approach： 每个object都代表着一个子空间，对于重叠的object建立索引的相关关系。
典型空间数据结构
一个是kd-tree，一个是R-tree，这是两个非常经典的高维空间的数据结构。但是整体来讲，R-tree是更适合于空间数据的表征上。
R-tree的关键思想：其实就和我们填通信地址一样，快递公司如何去索引到你的家，仅仅读一下通信地址就可以了。首先限制你在中国，然后限制你在北京，然后限制你在海淀，最后限制你在北邮，再最后限制你在哪个宿舍。你会发现这是一个平衡树的结构，每个叶子节点存着两个属性，一个是自己节点所代表的最小矩形区域，这也就是R的来源（Rectangle）。另外一个属性是一个有长度限制的列表，列表中存着该矩形区域所包含的子节点的地址。因此空间中每一个object，都可以通过这样层级的索引进行表示，而在进行搜索时，也可以像解析一个通信地址一样，遍历的空间降到很低。
基于R-tree，就会有更多的问题产生，R-tree表示的是矩形，那么现实中想表示的是不规则的多边形，该如何做的问题，因此就会衍生其他的数据结构。