3

プレフィックス範囲のリストであるデータセットがあり、プレフィックスはすべて同じサイズではありません。以下にいくつかの例を示します。

low: 54661601   high: 54661679   "bin": a
low: 526219100  high: 526219199  "bin": b
low: 4305870404 high: 4305870404 "bin": c

対応するプレフィックスを持つ特定の値に対応する「ビン」を調べたい。たとえば、値5466160179125211は「bin」a に対応します。オーバーラップの場合 (ほとんどありません)、最長のプレフィックスまたはすべてのプレフィックスを返すことができます。

最適なアルゴリズムは明らかに、ビン オブジェクトを挿入できるある種のツリーであり、ツリーの連続する各レベルは、ますます多くのプレフィックスを表します。

問題は、これを (1 つのクエリで) データベースにどのように実装するかです。データセットを変更/追加することは許可されています。これに最適なデータとクエリの設計は何でしょうか? mongo または MySQL を使用した回答が最適です。

4

4 に答える 4

4

プレフィックス範囲のオーバーラップ数について穏やかな仮定を立てる場合、MongoDB または MySQL のいずれかを使用して、最適な方法で実行することができます。以下の私の回答では、MongoDB で説明しますが、この回答を MySQL に移植するのは簡単なはずです。

まず、問題を少し言い換えてみましょう。「プレフィックス範囲」の一致について話すとき、実際に話しているのは、辞書式の順序で正しい範囲を見つけることだと思います (直感的には、これは文字列の自然なアルファベット順です)。たとえば、プレフィックスが 54661601 から 54661679 に一致する数値のセットは、文字列として記述した場合、辞書編集的に「54661601」以上であるが、辞書編集的に「54661680」未満である数値のセットとまったく同じです。したがって、最初に行うべきことは、すべての上限に 1 を追加して、この方法でクエリを表現できるようにすることです。mongo では、ドキュメントは次のようになります。

{low: "54661601", high: "54661680", bin: "a"}
{low: "526219100",  high: "526219200",  bin: "b"}
{low: "4305870404", high: "4305870405", bin: "c"}

ここで問題は次のようになります: [ low , high )の形式の 1 次元区間のセットが与えられた場合、与えられた点を含む区間をどのようにすばやく見つけることができるでしょうか? これを行う最も簡単な方法は、ローフィールドまたはハイフィールドのインデックスを使用することです。ハイフィールドを使いましょう。mongo シェルの場合:

db.coll.ensureIndex({high : 1})

ここでは、間隔がまったく重ならないと仮定しましょう。この場合、特定のクエリ ポイント "x" について、"x" を含む唯一の可能な間隔は、"x" より大きい最小の高値を持つものです。したがって、そのドキュメントを照会して、その低い値も「x」より小さいかどうかを確認できます。たとえば、一致する間隔があれば、これを出力します。

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(1).forEach(
       function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
  )

ここで、間隔がまったく重ならないと仮定する代わりに、すべての間隔がk 個未満の隣接する間隔と重なっていると仮定するとします ( kのどの値があなたにとってこれを真にするかはわかりませんが、それが小さいことを願っています)。 ）。その場合、上記の「制限」で1 をkに置き換えるだけです。

 db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(k).forEach(
       function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
  )

このアルゴリズムの実行時間は? インデックスは B ツリーを使用して保存されるため、データ セットにn 個の間隔がある場合、最初に一致するドキュメントを高い値で検索するのに O(log n ) の時間がかかり、次のkを反復するのにO( k ) の時間がかかります。ドキュメント、合計 O(log n + k ) 時間。kが定数である場合、または実際には O(log n )未満の場合、これは漸近的に最適です (これは計算の標準モデルにあります。外部メモリ転送の数などはカウントしていません)。

これが破綻する唯一のケースは、kが大きい場合です。たとえば、ある大きな間隔に他の間隔がほぼすべて含まれている場合です。この場合、実行時間は O( n ) です。データがこのように構造化されている場合は、おそらく別の方法を使用することをお勧めします。1 つのアプローチは、mongo の "2d" インデックスを使用することです。x座標とy座標を符号化した低い値と高い値を使用します。次に、クエリは、 x - y平面の特定の領域内のポイントのクエリに対応します。これは実際にはうまくいくかもしれませんが、2d インデックスの現在の実装では、最悪のケースは依然として O(n) です。

kのすべての値に対してO(log n ) のパフォーマンスを達成する多くの理論的結果があります。これらは、優先検索ツリー、セグメント ツリー、間隔ツリーなどの名前で呼ばれます。ただし、これらは独自に実装する必要がある特殊な目的のデータ構造です。私の知る限り、現在それらを実装している一般的なデータベースはありません。

于 2012-06-16T20:09:26.347 に答える
0

「最適」は、人によって意味が異なります。低い値と高い値をvarcharとして保存するようなことができるようです。その後、あなたがしなければならないのは

select bin from datatable where '5466160179125211' between low and high

または、値をテーブルに整数として保持する何らかの理由がある場合は、クエリでキャストを実行できます。

これが大規模なデータセットでひどいパフォーマンスをもたらすかどうかはわかりません。そして、あなたが何をしたいのかを理解していただければ幸いです。

于 2012-06-15T17:04:40.643 に答える
0

MySQL では、値を bin にマップするために呼び出すストアド プロシージャを使用する必要がある場合があります。この手順では、各行のバケットのリストを照会し、算術演算または文字列演算を実行して、一致するバケットを見つけます。固定長のプレフィックスを使用して、固定数のレイヤーに配置することで、この設計を改善できます。ツリーに固定の深さを割り当てることができ、各レイヤーにはテーブルがあります。これらのアプローチでは、ツリーのようなパフォーマンスは得られません。

より高度なことをしたい場合は、別のプラットフォームを使用する必要があると思います。

Sql Server には Hierarchy データ型があります: http://technet.microsoft.com/en-us/library/bb677173.aspx

PostgreSQL には cidr データ型があります。私はそれが持っているクエリサポートのレベルに精通していませんが、理論的には、データベース内にルーティングテーブルを構築し、それを使用してバケットを割り当てることができます: http://www.postgresql.org/docs/7.4/static/ datatype-net-types.html#DATATYPE-CIDR

于 2012-06-15T16:22:37.667 に答える
0

ペイトン！:)

すべてを整数として保持する必要があり、単一のクエリで動作させたい場合は、次のように動作するはずです。

select bin from datatable where 5466160179125211 between 
      low*pow(10, floor(log10(5466160179125211))-floor(log10(low))) 
   and ((high+1)*pow(10, floor(log10(5466160179125211))-floor(log10(high)))-1);

この場合、番号 5466160100000000 (低いプレフィックスと検索する番号と同じ桁数を持つ最小の番号) と 546616799999999 (高いプレフィックスと番号と同じ桁数を持つ最大の番号) の間で検索します。見つけるには）。これは、高いプレフィックスの桁数が低いプレフィックスよりも多い場合でも機能するはずです。前のソリューションの varchar コードが誤った結果をもたらす可能性がある場合、数値がプレフィックスの長さよりも短い場合にも機能するはずです (私はそう思います)。

実験して、(このソリューションのように) クエリに大量のインライン演算を使用した場合のパフォーマンスと、varchar を使用した場合のパフォーマンスを比較する必要があります。

編集: インデックスのない大きなテーブルでも、どちらの方法でもパフォーマンスは非常に優れているようです。varchar を使用できる場合は、low 列と high 列にインデックスを付けることで、パフォーマンスをさらに向上できる可能性があります。いずれかのプレフィックスに最初のゼロがある場合は、間違いなく varchars を使用する必要があることに注意してください。varchars を使用するときに、数値がプレフィックスよりも短い場合に対応するための修正を次に示します。

select * from datatable2 where '5466' between low and high
    and length('5466') >= length(high);
于 2012-06-15T19:40:54.390 に答える