0

我是一名核物理学研究生,目前正在从事数据分析程序。数据由数十亿个多维点组成。

无论如何,我正在使用空间填充曲线将多个维度映射到一个维度,并且我正在使用 B+ 树来索引数据页面。每个页面将有一些恒定的最大点数。

当我从原始文件中读取原始数据(数百个演出)并对其进行预处理和索引时,我需要将各个点插入到页面中。显然,页面太多,无法简单地将它们存储在内存中,然后将它们转储到磁盘。所以我的问题是:将页面写入磁盘的好策略是什么,以便当页面达到最大大小并需要拆分时,数据的重新洗牌最少。

根据评论让我减少一点。

我有一个包含有序记录的文件。这些记录被插入到文件中,这些记录太多,无法简单地在内存中执行此操作,然后写入文件。我应该使用什么策略来最小化插入记录时所需的重新洗牌量。

如果这有任何意义,我将不胜感激您可能拥有的任何解决方案。

编辑:
数据是多维空间中的点。本质上是整数列表。这些整数中的每一个都是 2 个字节,但每个整数还有一个额外的 2 个字节与之关联的元数据。所以每个坐标 4 个字节和 3 到 20 个坐标之间的任何位置。所以基本上数据由数十亿个块组成,每个块在 12 到 100 个字节之间。(很明显,4 维的点与 5 维的点在被提取后将位于不同的文件中)。

我正在使用类似于本文中讨论的技术: http ://www.ddj.com/184410998

编辑 2:我有点后悔在这里问这个问题,所以认为它已被正式取消;但这是我不使用现成产品的原因。我的数据是从 3 到 22 维不等的点。如果您将每个点视为简单的列表,您可以将我想如何查询这些点作为与这些数字出现在相同列表中的所有数字。以下是一些低维的示例(并且数据点比正常少得多)示例:数据 237、661、511、1021 1047、661、237 511、237、1021 511、661、1047、1021

Queries:
511
1021
237, 661
1021, 1047
511, 237, 1047

Responses:
237, 661, 1021, 237, 1021, 661, 1047, 1021
237, 661, 511, 511, 237, 511, 661, 1047
511, 1021, 1047
511, 661
_

所以这对于大多数数据库程序来说是一个困难的小问题,尽管我知道一些可以很好地处理这个问题的存在。

但问题变得更加复杂。并非所有坐标都相同。很多时候,我们只是单独使用 gammasphere 运行,因此每个坐标代表一个 gamma 射线能量。但有时我们将中子探测器插入伽马球或称为微球的探测器系统,或者有时将伽马球中产生的核素导入碎片质量分析仪,所有这些和更多的探测器系统都可以单独使用或与伽马球任意组合使用。不幸的是,我们几乎总是希望能够以类似于上述方式的方式在这些附加数据上进行选择。所以现在坐标可以有不同的含义,如果除了伽马球之外只有微球,那么你就可以用与方程 x + y = n 的正解一样多的方式构成一个 n 维事件。此外,每个坐标都有与之关联的元数据。所以我展示的每个数字都至少有两个额外的数字与之相关,第一个是探测器编号,用于检测事件的探测器,第二个是效率值,用于描述特定伽马射线的次数计数(因为实际检测到进入探测器的伽马射线的百分比,随探测器和能量而变化)。

我真诚地怀疑,任何现成的数据库解决方案都可以在没有大量定制的情况下同时完成所有这些事情并表现良好。我相信花在这上面的时间最好花在编写我自己的解决方案上,更不用说通用的解决方案了。由于失去了一般性,我不需要为任何数据库代码实现删除功能,我不需要建立二级索引来控制不同类型的坐标(只有一组,每个点只计算一次),等等

4

3 回答 3

1

我相信你应该首先看看商业和免费数据库必须提供什么。它们旨在执行快速范围搜索(给定正确的索引)并有效地管理内存和读/写页面到磁盘。

如果做不到这一点,请查看二进制空间分区( BSP ) 树的一种变体。

于 2009-07-28T00:38:43.433 回答
0

因此,第一个方面是在线程应用程序中执行此操作以更快地完成它。将您的数据块分解为可行的部分。这让我想到...

我最初打算建议您使用 Lucene ......但考虑到这听起来确实像是您应该使用Hadoop处理的东西。它是为这种工作而设计的(假设你有它的基础设施)。

我肯定不会在数据库中这样做。

当您谈到索引数据和使用数据点填充文档时......并且您没有基础结构、知道如何或时间来实施 hadoop,您应该回到我最初的想法并使用 Lucene。您实际上可以以这种方式索引您的数据,并将您的数据点直接存储到索引中(我认为按数字范围),并使用您认为最好的“文档”(对象)结构。

于 2009-07-28T00:29:22.387 回答
0

我自己想出了一个答案。当页面需要拆分时,事件被插入到页面中,在文件末尾创建了一个新页面。原始页面的一半事件被移动到该页面。这使得页面未排序,这在某种程度上破坏了快速检索机制。

但是,由于我只在一个大的初始匆忙中写入数据库(可能持续几天),我可以证明在写入后花费一些额外的时间来浏览页面并在它们全部构建后对它们进行排序。这部分实际上很容易,因为用于索引页面的 B+ 树的性质。我只是从 B+tree 的最左边的叶节点开始,读取第一页并将其放在最终文件中,然后读取第二页并将其放在第二位,依此类推。

以这种方式,在插入结束时,所有页面都将在其文件中进行排序,从而允许我用来将多维请求映射到单维索引的方法在从磁盘读取数据时高效快速地工作。

于 2009-09-11T01:53:38.633 回答