提供Quadtree GPS数据到应用程序的最佳select？

我们有> 25 MB的静态四叉树数据，我们希望作为跨平台应用程序的一部分提供，然后可以通过应用程序代码进行search，以获取接近用户当前GPS位置的位置的详细信息。

我们希望在不加载所有数据的情况下快速search数据，理想情况下不需要重新发明轮子。

我们已经看过在SQLite中使用R-Trees提供数据库，这听起来像是理想的，但显然这些在Android提供的SQLite版本中不可用。 运行我们自己的Android版SQLite（包括R-Tree结构）听起来有很多痛苦，但我们希望了解其他人的经验。

我们可以创build一个文件系统模型，但是我们的数据可能非常大，而且我们觉得我们可能会以这种方式误用文件系统。

我们希望可能有一些其他文件格式已经为此目的而devise，可能还有java / obj-c库来search这个文件。 任何人都可以指出我们这样的事情吗？

另一个明显的解决scheme是创build我们自己的文件格式和search系统，但这可能是很多工作。

该应用程序实际上是一个cordova / phonegap应用程序，将可用于iOS和Android，但它不是一个问题编写一个本地插件为每个平台来处理这个。

提前致谢

Answer 1

忽略这个问题的离题问题，在Android上使用R-tree数据需要用NDK编译SQLite，然后发送给你想要支持的任何体系结构。

但是，SQLite的R-tree模块是作为使用“普通”表来存储R-tree数据的扩展来实现的。 处理R树最复杂的部分是更新和重新平衡树; 相比之下，search是微不足道的。 如果你只想在静态数据上search，你可以手动实现。

源代码有这样的说法：

R-Tree表的数据库格式

单个虚拟r-tree表的数据结构存储在三个本地SQLite表中，如下所示。 在每种情况下，表名中的'％'字符被用户提供的r-tree表名replace。

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB) CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER) CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER) 

r-tree结构的每个节点的数据存储在％_node表中。 对于不是r-tree的根节点的每个节点，在％_parent表中有一个将节点与其父节点关联的条目。 对于表中的每行数据，％_rowid表中存在一个条目，该条目将rowid条目映射到存储节点的id。

即使r-tree表为空，r-tree的根节点也始终存在。 根节点的nodeno始终为1.表中的所有其他节点必须与根节点的大小相同。 每个节点的内容格式如下：

1. 如果节点是根节点（节点1），则节点的前2个字节包含树深度作为大端整数。 对于非根节点，前2个字节未被使用。

2. 接下来的2个字节包含当前存储在节点中的条目的数量。

3. 节点的其余部分包含节点条目。 每个条目由一个8字节的整数组成，接着是偶数个4字节的坐标。 对于叶节点，整数是logging的rowid。 对于内部节点，它是一个子页面的节点号。

对于search，您不需要_parent或_rowid表。

algorithm看起来像这样：

 def search(nodeno = 1, root = True, tree_depth = -1, depth = 0): execute("SELECT data FROM X_node WHERE nodeno = ?", [nodeno]) if root: tree_depth = first_two_bytes for entry in data: if entry.rectangle matches: if depth == tree_depth: result += entry.id else: search(entry.nodeno, False, tree_depth, depth + 1)