android - 向应用程序提供 Quadtree GPS 数据的最佳选择？

Question

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

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

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

我们可以创建一个文件系统模型，但我们的数据可能非常大，并且感觉我们可能会以这种方式误用文件系统而遇到麻烦。

我们希望可能已经为此目的设计了一些其他文件格式，并且可能存在用于搜索此目的的 java/obj-c 库。任何人都可以向我们指出这样的事情吗？

另一个显而易见的解决方案是创建我们自己的文件格式和搜索系统，但这可能需要大量工作。

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

提前致谢

Answer 1

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

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

source code有这样的话:

Database Format of R-Tree Tables

The data structure for a single virtual r-tree table is stored in three native SQLite tables declared as follows. In each case, the '%' character in the table name is replaced with the user-supplied name of the r-tree table.

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)

The data for each node of the r-tree structure is stored in the %_node table. For each node that is not the root node of the r-tree, there is an entry in the %_parent table associating the node with its parent. And for each row of data in the table, there is an entry in the %_rowid table that maps from the entries rowid to the id of the node that it is stored on.

The root node of an r-tree always exists, even if the r-tree table is empty. The nodeno of the root node is always 1. All other nodes in the table must be the same size as the root node. The content of each node is formatted as follows:

1. If the node is the root node (node 1), then the first 2 bytes of the node contain the tree depth as a big-endian integer. For non-root nodes, the first 2 bytes are left unused.

2. The next 2 bytes contain the number of entries currently stored in the node.

3. The remainder of the node contains the node entries. Each entry consists of a single 8-byte integer followed by an even number of 4-byte coordinates. For leaf nodes the integer is the rowid of a record. For internal nodes it is the node number of a child page.

对于搜索，您不需要 _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)