ディスクに展開するための戦略ディスク

Question

私は現在、データ解析プログラムに取り組んでいる核物理学の大学院生です。データは、数十億の多次元ポイントで構成されています。

とにかく、複数のディメンションを1つのディメンションにマップするために空白の塗りつぶし曲線を使用しています。データのページにインデックスを付けるためにB +ツリーを使用しています。各ページには一定の最大点数があります。

元のファイルから生データ（数百ギガ）を読み込み、前処理してインデックス化するときに、個々のポイントをページに挿入する必要があります。明らかに、あまりにも多くのページがメモリに格納され、ディスクにダンプされるだけです。だから私の質問は、これは次のとおりです。ページをディスクに書き込むための良い戦略は、ページが最大サイズに達して分割する必要があるときにデータの再シャッフルを最小限に抑えることです。

コメントに基づいて少し減らしてみましょう。

私は、注文されたレコードを含むファイルを持っています。これらのレコードはファイルに挿入されており、メモリ内でこれを単に実行してファイルに書き込むためには、これらのレコードが多すぎます。レコードを挿入するときに必要な再切り換えの量を最小限に抑えるためにどのような戦略をとるべきですか。

これが意味をなさないのであれば、私があなたに持っている可能性のある解決策に感謝します。

編集：
データは多次元スペースのポイントです。本質的に整数のリスト。これらの整数はそれぞれ2バイトですが、各整数には2バイトのメタデータも関連付けられています。したがって、1座標あたり4バイト、3〜20座標のどこかに座標があります。つまり、本質的にデータは、12〜100バイトのどこかの各チャンクで構成されています。 （明らかに、4次元が抽出されると、5次元の点とは異なるファイルに配置されます）。

私はこの記事で説明したものと同様の技術使用しています： http://www.ddj.com/184410998

編集2： を私はちょっとここにこの質問をして後悔するので、それが正式に撤回を検討。しかし、ここには棚用製品を使わないという理由があります。私のデータは、3次元から22次元の任意の範囲にある点です。それぞれの点を単なるリストと考えると、どのようにポイントを照会したいのか、これらの数字と同じリストにあるすべての数字が何であるか考えることができます。以下の低次元（及び通常より多くの、より少ないデータ点）といくつかの例は、 例： データ 237、661、511、 1047 1021 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またはマイクロボールと呼ばれる検出器システムに挿入するか、時にはgammasphereで生成された核種をフラグメント質量分析計に流し込み、これらの検出器システムはすべて単独で、またはgammasphereと組み合わせて使用​​できます。残念ながら、私たちはほとんどの場合、上記のような方法でこの追加データを選択できるようにしたいと考えています。だから座標は異なる意味を持つことができます。もしあなたが数式x + y = nに対して肯定的な解があるのと同じくらい多くの方法でn次元の出来事を作るようにすれば、さらに、各座標にはメタデータが関連付けられています。私が示した数字のそれぞれには、それらに関連する少なくとも2つの追加番号があります。第1に、イベントを取得した検出器の検出器番号、第2のもの、特定のガンマ線の回数を表す有効性値（実際に検出される検出器に入射するガンマ線の割合は、検出器およびエネルギーによって変化するため）。

棚卸しデータベースソリューションは、これらのすべてを実行し、同時に膨大な量のカスタマイズを行うことなく、うまく機能することを誠実に疑っています。私はそれに費やされた時間が私自身の、より一般的ではない解決策を書くことに費やされたと考えています。一般性を失うため、データバインディングコードの削除機能を実装する必要はありません。異なるタイプの座標にゲートするためのセカンダリインデックスを構築する必要はありません（各ポイントを1回だけ有効に数えます）

Answer 1

私は自分自身で答えを出しました。ページを分割する必要があるときにイベントがページに挿入されると、ファイルの最後に新しいページが作成されます。元のページのイベントの半分がそのページに移動します。これにより、ページはソートされないままになり、高速検索メカニズムにいくぶん敗れます。

しかし、私は大規模なイニシャルラッシュ（たぶん数日間持続する）でDBに書き込むので、書いたあと少し時間を費やしてページを通ってそれらがすべて構築された後に並べ替えることを正当化することができます。この部分は、ページを索引付けするために使用されるB +ツリーの性質のため、実際は非常に簡単です。私は、B +ツリーの一番左の葉ノードで始まり、最初のページを読んで最初に最終ファイルに入れてから、2番目のページを読んで2番目に置くなどします。

この方法で、挿入の最後にすべてのページがファイル内でソートされ、多次元の要求を1次元のインデックスにマップして効率的かつ迅速にディスクからデータを読み込む方法が可能になります。

Answer 2

したがって、最初の側面は、スレッドアプリケーションでこれを実行して、より早くそれを行うことです。データのまとまりを実行可能なセクションに分割します。これは私に考えさせてくれます...

私は最初にLuceneを使うことを提案するつもりでしたが、これは実際にはHadoopで処理すべきもののように思えます。この種の作業のために作られました（インフラストラクチャがあると仮定して）。

私は確かにこれをデータベースでは行いません。

データをインデックス付けしてドキュメントにデータポイントを埋め込むと、インフラストラクチャがなく、hadoopを実装する方法や時間がわからないときは、元の考えに戻り、Lucene 。あなたは実際にあなたのデータをそのように索引付けし、データポイントを「ドキュメント」（オブジェクト）構造で索引に直接格納することができます。

Answer 3

私は、商用と無料のデータベースが提供しなければならないものをまず見てください。それらは高速な範囲の検索（適切なインデックスが与えられている）を実行し、効率的にメモリを管理し、ページをディスクに読み書きするように設計されています。

バイナリSpace Partition（BSP）の種類の1つを見てください。