5

我有一组(x,y)64 位整数的元组组成我的数据集。比如说，我有数万亿个这样的元组；将数据集保存在地球上任何机器的内存中是不可行的。但是，将它们存储在磁盘上是相当合理的。

我有一个磁盘存储（一个 B+-tree），它允许在一个维度中快速、并发地查询数据。但是，我的一些查询依赖于这两个维度。

查询示例：

  • 查找x大于或等于某个给定值的元组
  • 找到x尽可能小的 st 它y大于或等于某个给定值的元组
  • 找到x尽可能小的 st 它y小于或等于某个给定值的元组
  • 执行维护操作（插入一些元组，删除一些元组）

我发现最好的选择是 Z 阶曲线，但我似乎无法弄清楚如何在给定我的二维数据集的情况下进行查询。

不可接受的解决方案包括数据的顺序扫描，这可能太慢了。

4

4 回答 4

2

我认为，最适合您要求的数据结构是R-tree及其变体（R*-tree、R+-tree、Hilbert R-tree）。R-tree 类似于 B+-tree，但也允许多维查询。

其他相关的数据结构是优先搜索树。它适用于您的示例 1 .. 3 之类的查询，但如果您需要频繁更新或磁盘存储，则效率不高。有关详细信息，请参阅本文或本书：“数据结构和应用手册”（第 18.5 章）。

于 2012-09-21T08:17:46.983 回答
0

http://fallabs.com/tokyocabinet/

Tokyo Cabinet 是用于管理数据库的例程库。数据库是一个包含记录的简单数据文件，每个记录是一对键和一个值。每个键和值都是可变长度的串行字节。二进制数据和字符串都可以用作键和值。既没有数据表的概念，也没有数据类型的概念。记录以散列表、B+ 树或定长数组的形式组织。

Tokyo Cabinet 是用 C 语言编写的，并作为 C、Perl、Ruby、Java 和 Lua 的 API 提供。Tokyo Cabinet 在具有符合 C99 和 POSIX 的 API 的平台上可用。Tokyo Cabinet 是根据 GNU Lesser General Public License 授权的免费软件。

你可以轻松嵌入吗？

于 2013-09-16T04:16:57.073 回答
0

我目前正在设计一个数据结构，它本质上是一个用于多维数据的“堆叠”B+ 树（或d + 树，其中d是维数）。我相信它会完美地适合您的数据，并且是专门为您的用例设计的。

基本思想是这样的：

每个维度都是一个 B+ 树，并链接到下一个维度的 B+ 树。通常搜索第一个维度，一旦到达叶子，它就会包含一个指向下一个 B+ 树的根的指针，该树属于下一个维度。第二个 B+ 树中的所有内容都属于同一个x值。

最初的计划是只存储每个维度的唯一值及其计数。这采用了一种非常简单的压缩算法（如果您甚至可以这样称呼它），同时仍然允许表示整个数据集。这种“链接”维度方案可以允许稍后添加额外维度，因为它们只是添加到 B+ 树的堆栈中。

2 个维度的总插入/搜索/删除时间将与此类似：

log b(card(x)) + log b(card(y))

其中b是每个 B+ 树的基数，而card(x)将是x维度的基数。

我希望这是有道理的。我仍在致力于实现，但可以随意使用甚至增强这个想法。

于 2013-01-28T03:21:51.533 回答
0

你是说你不知道如何查询 z 阶曲线？维基百科页面描述了您如何进行范围搜索。

z 曲线将您的空间划分为嵌套的矩形，其中键中的每个附加位将空间分成两半。要搜索一个点：

Start with the largest rectangle that might contain your point.

    Recursively:

        Create a result set of rectangles    

    For each rectangle in your set        
        If the rectangle is a single point, you are done, it is what you are looking for.
        Otherwise, divide the rectangle in two (specify one additional bit of the z-curve)
            If both halves contain a point
                If one half is better 
                    Add that rectangle to your result set of rectangles
                Otherwise
                    Add both rectangles to your result set of rectangles
            Otherwise, only one half contains a point
                    Add that rectangle to your result set of rectangles

    Search your result set of rectangles

当然，最坏情况下的性能很差。您可以通过更改构建 z 顺序索引的方式来调整它。

于 2012-09-20T23:09:23.803 回答