为应用程序提供四叉树GPS数据的最佳选择

Question

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

我们希望在不将所有数据加载到内存的情况下搜索数据，在快速的时间内，理想情况下不用重新发明轮子。

我们已经考虑在SQLite中使用R-Trees提供数据库，这听起来很理想，但显然这些在android提供的SQLite版本中不可用。为android发布我们自己的SQLite版本(包括R-Tree结构)听起来很痛苦——但我们很想听听其他人在这方面的经验。

我们可以创建一个文件系统模型，但是我们的数据可能非常大，感觉我们可能会因为这样错误地使用文件系统而遇到麻烦。

我们希望可能有一些其他的文件格式已经为此目的而设计，也许java/obj-c库已经存在。有谁能给我们指出来吗?

另一个明显的解决方案是创建我们自己的文件格式和搜索系统，但这可能会做很多工作。

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

Thanks in advance

Answer 1

忽略这个问题的离题方面，在Android上使用R-tree数据需要用NDK编译SQLite，并将其发布到任何你想要支持的架构。

然而，SQLite的R-tree模块是作为一个扩展来实现的，它使用'normal'表来存储R-tree数据。处理r树最复杂的部分是更新和重新平衡树;与此相比，搜索是微不足道的。如果您只想在静态数据上搜索，您可以手动实现它们。

源代码是这样说的:

R-Tree表的数据库格式

单个虚拟r-tree表的数据结构存储在三个表中本机SQLite表声明如下。在每种情况下，都是'%'字符在表中，名称被替换为用户提供的r树名称表。

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树根节点的节点，有%_parent表中的条目，将节点与其父节点关联起来。对于表中的每一行数据，在%_rowid中都有一个条目表，该表从条目rowid映射到它所在节点的id存储在。

r-tree的根节点总是存在的，即使r-tree表存在空的。根节点的节点数总是1。中的所有其他节点表的大小必须与根节点相同。每个节点的内容格式如下:

1. 如果节点是根节点(节点1)，则前2个字节的节点以大端整数的形式包含树的深度。对于非根节点，前2个字节不使用

2. 后2个字节包含当前表项的个数

3. 节点的剩余部分包含节点条目。每个条目由一个8字节的整数后跟一个偶数组成4字节坐标的。对于叶节点，整数是行号有记录。对于内部节点，它是a的节点号子页面。

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

算法是这样的:

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)