libSpatialIndex空间索引详解

设计目标：

1. 一种具有扩展性的框架，能够提供具备健壮性的索引方法
2. 支持复杂查询，如范围查询、点位置查询、最近邻查询、k个最近邻查询以及参数化查询（有空间约束条件定义）都可以方便的部署和运行
3. 提供针对插入、删除和更新操作易用的接口
4. 各种定制功能。基本索引和存储特性,如页面大小,节点容量,最低扇出,分裂算法等能够方便定制
5. 索引的持久性。支持内部存储和外部存储数据结构，集群与非集群索引也能够方便持久化存储

特征：

1. 基于存储管理器的磁盘和内存两种存储方式
2. 支持R*-树索引
3. 支持MVR-树索引
4. 支持TPR-树索引
5. 提供先进的查询能力，使用策略设计模式和观察者设计模式
6. 提供任意图形的范围查询
7. 强大的参数化能力，包括自定义维度，容量参数，节点容量等的设置
8. 提供STR packing 和 批量导入数据

目前版本包含六个包：

1. The core spatialindex utilities
2. The storagemanager files
3. The spatialindex interfaces
4. The rtree index
5. The mvrtree index
6. The tprtree index

Spatial Index Utilities：

• 提供一个PropertySet类，该类为库中所有对象提供了统一的构造和初始化功能。一个PropertySet将字符串与Variant关联，每一个property与一个字符串相关。

PropertySet提供如下三个函数：

1. getProperty：返回与给定string相关联的Variant
2. setProperty：将给定Variant和给定string关联在一起
3. removeProperty：从PropertySet删除某一个property

• 定义了一定数量的异常类，都提供了一个what方法，可以返回关于异常的一些有用信息。
• 定义了一个IShape接口，所有图形类都继承自这个接口。
• 提供了Region类和Point类

Storage manager：

• 为索引的存储管理提供了统一的接口。定义了IStorageManager接口，为存储和获取entities提供了一系列函数。一个entity可以视为一个简单的字节数组，所以，一个entity可以是索引entity、数据entity或者其他任何用户想要存储的东西。IStorageManager接口是一般化的接口，并不仅仅为空间索引提供支持。
• 实现IStorageManager接口的类决定如何存储entities，库中提供了简单的基于内存存储的简单实现，例如用vector存储entities，每一个entity对应一个唯一的ID。而基于磁盘存储的实现，只要能够保证每一个entity能够对应唯一一个ID，可以将entities存储在可以随机访问的文件中，或者可以将它们存储在数据库管理系统中的关系表里。storage manager也实现了它自己的页、压缩和删除策略，而这些策略对调用者（索引或者使用者）是透明的。
• 三种方法：
  • storeByteArray方法输入参数是：一个字节数组，它的长度，entity ID。如果调用者使用一个新页作为输入ID，那么storage manager就会分配一个新的ID，存储这个entity并返回与这个entity相关联的ID。如果用户使用一个已存在的ID来作为输入ID，那么storage manager就会覆盖掉旧数据。如果调用者使用一个无效的ID作为输入的话，就会抛出一个异常。
  • loadByteArray方法输入参数是：一个entity ID。返回值：该ID对应的字节数组。如果输入无效ID，就会抛出异常。
  • deleteByteArray删除对应的entity。
• storage manager没有关于entity字节数组类型的信息，原因如下；

1. storage manager使用任意数量的页和每个索引唯一的ID来存储大量的空间索引。
2. 支持聚合和非聚合的索引。一个聚合索引存储着与entity关联的数据中的空间信息。而非聚合索引仅仅存储着entity自身的空间信息。任何数据都是单独存储的，而与数据相关联的索引entity都有唯一的ID与之对应。为了支持这两种索引，storage manager接口被设计的更加一般化，允许索引来决定如何存储数据。另外，聚合索引和非聚合索引应该分别实现。
3. 选择更加灵活。例如，一个用户可以选择使用聚合索引存储全部内容。也可以选择基于主存存储的非聚合索引，并且在数据库中存储实际的数据。也可以选择基于磁盘存储的非聚合索引，并且手动的以单独的二进制文件存储数据或者将数据交由同一个storage manager存储。

• 目前，库中提供了两种storage manager实现：

• MemoryStorageManager

在主存中实现。使用vector存储数据。MemoryStorageManager对象初始化不需要初始化任何property，当MemoryStorageManager对象离开作用域是，它存储的数据就会全部消失。

• DiskStorageManager

使用两个随机访问文件存储信息。一个扩展名为.idx，另一个为.dat。

初始化时可以支持的属性列表：

对于大小超过一个页能够存储的entities，需要使用多个页存储。这样会导致最后一个页有部分空间的浪费（可能没有存满）。

idx文件存储一些重要的辅助信息。如页大小，下一个可用页，空页列表和与每一个ID相关联的顺序页。

提供了flush方法，用于重写idx文件和同步两个文件的指针。

idx文件在初始化时被加载到内存中，仅仅在刷写storage manager后，或者在析构对象过程中，被写回磁盘。如果这期间发生不可预知错误导致idx文件丢失，则无法恢复。

SpatialIndex Interfaces：

• 空间索引是一种能够高效访问空间信息的索引数据结构。它可以表达简单的网格文件，同样可以表达复杂的树结构。空间索引能够检索IEntry类型的entries，这些entries可以是索引节点，叶子节点，数据等，主要取决于其结构特点。应该为所有类型的entry提供一个合适的接口，这个接口可以提供一些有用访问的方法。
• 一个空间索引应该能够实现ISpatialIndex接口。
• containmentQuery方法要求有一个查询shape和有效的IVisitor实例的引用作为输入参数。intersectionQuery方法与之类似。它们都接受一个IShape类型实例作为输入参数。当查询shape是一个简单的区域时，那就会执行一个典型的区域查询算法。用户也可以创建自己的shape，因此可以在不修改索引的情况下，自定义intersection和containment方法来执行任何种类的范围查询。在回归测试（regressiontest）目录下有一个不规则四边形的例子。切记，用户要负责正确的实现自己创建的shape和要使用到的索引类型之间的intersection和containment方法。例如，如果要使用一个R树索引，不规则四边形需要定义它自身和Regions之间的intersection和containment方法，因为所有的R树节点都是Region类型。因此，用户如果想要运行一些复杂的查询，需要对索引内部的表达有一定的了解。
• pointLocationQuery方法用于执行点位置查询。需要待查询的点和一个visitor对象作为输入参数。
• nearestNeighborQuery方法用于执行最近邻查询。第一个参数是最近邻的个数k，其余两个参数是查询shape和visitor对象。缺省的实现是使用IShape的getMinimumDistance函数，根据存储于树中的矩形节点和数据entries来计算查询的距离。可以通过实现INearestNeighborComparator接口来进行更加复杂的距离计算，并把其作为nearestNeighborQuery方法的最后一个参数传递进来。例如，当查询需要检查存储于树中的实际数据而不是存储在叶子节点中的近似矩形数据entry时，需要一个comparator。
• 为了能够定制查询，IVisitor接口提供了访问索引、叶子节点以及数据entry的回调函数。可以使用INode和IData接口（均继承自IEntry）获得节点和数据的信息。使用这个接口的例子包括可视化查询，计算叶子节点的数量，计算某一次查询中被访问的索引节点的数量，当一个空间区域被访问时抛出警告信息等。
• queryStrategy方法提供了设计更加复杂查询的能力。它使用了IQueryStrategy接口作为回调函数，直到没有entries请求为止，这个接口会一直被调用。它也可以用来实现定制查询算法。
• insertData方法用户插入一个数据entry。insertion函数会将shape转换为其所依赖的索引的内部表达。每一个插入对象都会有一个ID，用于更新，删除和返回该对象。调用者负责给索引提供一个ID（无论是否唯一）。同样的，一个字节数组与一个entry关联，这个字节数组与空间信息一起被存储在叶子节点中。以这种方式来支持聚合索引。字节数组也可以为空，这样的话节点就不会有额外的空间被使用。
• deleteData方法删除一个数据entry。参数是shape对象和ID。空间索引是根据空间特征而不是ID来聚合对象的，所以本质上讲，shape对象被用来定位和删除一个entry。
• IStatistics接口和getStatistics方法用于获取一些有用的统计信息。
• getIndexProperties方法返回一个PropertySet，其中保存了像维度这种索引的属性信息。
• NodeCommand用于定制节点操作。使用addWriteNodeCommand方法，addReadNodeCommand方法，addDeleteNodeCommand方法来定制命令对象，并将其加入到监听列表中，在相关的操作执行后，会执行这些命令。
• isIndexValid方法用于检查内部数据结构的完整性。主要用于调试。
• 当一个索引创建了一个唯一的索引ID后，要赋值给它，以便于在后面从永久存储的磁盘上重新加载进内存后再次使用。在PropsertySet实例中，索引ID应该作为一个索引标识属性被返回，用于构造索引实例。使用索引ID，可以让一个storage manager管理多种索引结构（multiple indices，可能我理解的不准确）。管理索引ID是用户负责的，将错误的ID关联到错误的storage manager或者错误的索引类型，会导致未定义的结果。

The RTree Package：

• R树索引是一种平衡的树结构，其中包括了索引节点，叶子节点和数据。每一个节点（索引节点和叶子节点）都有固定的entries容量，节点容量的选择是在索引创建是确定的。一个R树用最小包围盒（MBR）来抽象数据，并在叶节点中根据不同的试探方法来聚合这些包围盒（MBR）。查询是从根到叶子。索引过程是平衡的，不可能出现空节点。每一个节点都有一个最小数量entries的填充因子，填充因子一般为70%。
• R树的创建涉及到一下几个步骤：
  • 决定索引是存储在内存中还是磁盘中，并选择合适storage manager。
  • 选择索引节点和叶子节点的容量。
  • 选择填充因子（节点容量的1%~99%）。
  • 选择数据的维度。
  • 选择插入和更新的策略（选择R树的变体）。
• 如果R树被重新载入，构造过程中只需要提供索引ID。在这种情况下，一些可选项不能被修改，如索引节点和叶子节点的容量，填充因子，维度等。但是R树的变体选择是可以更改的，变体仅仅影响了在发生分裂是如何进行分裂，任何时候这个可选项都可以更改。
• 初始化PropertySet时，可以设置上面的几个可选项，属性列表如下：

Performance：

• 数据集大小和数据密集度都与容量和页大小没有关系。我们需要做的就是从磁盘快速读取数据并充分利用磁盘缓存和预取技术。
• 一般的，会选择页大小等于磁盘页大小。同样，节点容量也会设置足够大来存储整个页（如果有数据entries的话，也包括数据entries）。
• 在设置节点容量大小时，也要有一个权衡：节点容量越大，在插入、删除、定位节点entries的时间也会越长；另一方面，节点容量越大，树就变得越矮，减少了抵达叶子节点过程中随机IO的的次数。因此，在磁盘页太大的情况下，需要在单一页中存储多个节点来平衡I/O和CPU花费。
• 如果有足够大的缓存空间来存储主存中多数索引节点时，设置较大节点容量就没有什么意义了，因为树高不在是什么问题。当然，节点容量越小，为了范围查询而从磁盘中获取叶子节点的数量就越大（点查询和最近邻查询并没有太大影响）。所以，太小的容量设置也会对性能造成影响。
• 在一个页中存储多个节点也有另外的问题：磁盘碎片。可能由于数据entries没有合适的大小而导致没有填充满页。在这种情况下，是没有办法避免的，必然会导致一定的空间损失。
• 选择页大小相对简单，等于磁盘页大小即可。选择节点容量大小，并不容易。

References：

• [guttman84] “R-Trees: A Dynamic Index Structure for Spatial Searching”  Antonin Guttman, Proc. 1984 ACM-SIGMOD Conference on Management of Data (1985), 47-57.
• [gamma94] “Design Patterns: Elements of Reusable Object-Oriented Software”  Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, Addison Wesley. October 1994.