7

BerkeleyDB を使用しているときにアクセス方法の選択を促進するものを理解しようとしています: B-Tree と HashTable。Hashtable は O(1) ルックアップを提供しますが、挿入は高価です (Linear/Extensible ハッシュを使用すると、挿入のために償却された O(1) が得られます)。しかし、B ツリーはログ N (ベース B) のルックアップと挿入時間を提供します。B-Tree は、範囲クエリをサポートし、並べ替えられた順序でアクセスすることもできます。

  1. これらの考慮事項とは別に、他に何を考慮する必要がありますか?
  2. 範囲クエリをサポートする必要がない場合、Hashtable アクセス メソッドを使用できますか?
4

4 に答える 4

6

データ セットが非常に大きくなっても、内部メタデータの大部分がキャッシュに収まる可能性があるため、B ツリーの方が優れています。ハッシュは、その性質 (データの均一なランダム分散) により、本質的にキャッシュに適していません。つまり、データ セットの合計サイズが作業メモリのサイズを超えると、ハッシュのパフォーマンスが崖から落ち、B ツリーのパフォーマンスは (実際には対数的に) 緩やかに低下します。

于 2012-08-23T01:24:27.987 に答える
2

多くのアプリケーションでは、データベースはランダムに、対話的に、または「トランザクション」でアクセスされます。これは、Web サーバーからデータを受信して​​いる場合に発生する可能性があります。ただし、多くの場合、「バッチ」操作として、大規模なデータベースを一度に作成する必要があります。これは、データ分析プロジェクトを行っている場合、または古いデータベースを新しい形式に移行している場合に発生する可能性があります。

データベースに一度にデータを入力する場合は、B ツリーまたはその他の並べ替えられたインデックスを使用すると、バッチ挿入をより効率的に実行できるため、推奨されます。これは、キーをデータベースに入れる前にソートすることによって実現されます。すべてのアクセスがキャッシュ ミスであるため、BerkeleyDB データベースに 1,000 万のエントリを入力するには、エントリが並べ替えられていない場合に 1 時間かかる場合があります。しかし、エントリがソートされると、同じ手順で 10 分しかかからないことがあります。連続するキーが近接しているということは、ほぼすべての挿入にさまざまなキャッシュを利用することになるということです。ソートは非常に高速に実行できるため、データを挿入する前にソートするだけで、操作全体を数倍高速化できます。ハッシュテーブルのインデックス作成では、どのキーが隣り合うかが事前にわからないため、

更新: 実際の例を提供することにしました。db-test次のスクリプト " "に基づいています。

#!/usr/bin/perl
use warnings;
use strict;
use BerkeleyDB;
my %hash;
unlink "test.db";
tie %hash, (shift), -Filename=>"test.db", -Flags=>DB_CREATE or die;
while(<>) { $hash{$_}=1; }
untie %hash;

1600 万エントリのウィキペディア ダンプ インデックス ファイルでテストできます。(私はこれを 800MHz 2 コアのラップトップで実行しており、メモリは 3G です)

$ >enw.tab bunzip2 <enwiki-20151102-pages-articles-multistream-index.txt.bz2
$ wc -l enw.tab
16050432 enw.tab
$ du -shL enw.tab
698M    enw.tab
$ time shuf enw.tab > test-shuf
  16.05s user 6.65s system 67% cpu 33.604 total
$ time sort enw.tab > test-sort
  70.99s user 10.77s system 114% cpu 1:11.47 total
$ time ./db-test BerkeleyDB::Btree < test-shuf
  682.75s user 368.58s system 42% cpu 40:57.92 total
$ du -sh test.db
1.3G    test.db
$ time ./db-test BerkeleyDB::Btree < test-sort
  378.10s user 10.55s system 91% cpu 7:03.34 total
$ du -sh test.db
923M    test.db
$ time ./db-test BerkeleyDB::Hash < test-shuf
  672.21s user 387.18s system 39% cpu 44:11.73 total
$ du -sh test.db
1.1G    test.db
$ time ./db-test BerkeleyDB::Hash < test-sort
  665.94s user 376.65s system 36% cpu 46:58.66 total
$ du -sh test.db
1.1G    test.db

Btree キーを事前に並べ替えると、挿入時間が 41 分から 7 分に短縮されることがわかります。並べ替えには 1 分しかかからないため、データベースの作成が 5 倍速くなり、正味の利益が大きくなります。ハッシュ形式では、入力がソートされているかどうかに関係なく、作成時間は等しく遅くなります。また、ソートされた挿入の場合、データベース ファイルのサイズが小さくなることにも注意してください。おそらく、これはツリーのバランスに関係しています。

スピードアップは何らかのキャッシングが原因であるに違いありませんが、どこにあるかはわかりません。ソートされた挿入を使用すると、カーネルのページ キャッシュでのキャッシュ ミスが少なくなる可能性があります。これは、CPU 使用率の数値と一致します。ページ キャッシュ ミスが発生した場合、ページがディスクから取得されるまでプロセスが待機する必要があるため、CPU 使用率は低くなります。

比較のために、2 つの小さなファイルでも同じテストを実行しました。

File       | WP index         | Wikt. words       | /usr/share/dict/words
Entries    | 16e6             | 4.7e6             | 1.2e5
Size       | 700M             | 65M               | 1.1M
shuf time  | 34s              | 4s                | 0.06s
sort time  | 1:10s            | 6s                | 0.12s
-------------------------------------------------------------------------
           | total  DB   CPU  |                   |
           | time  size  usage|                   |
-------------------------------------------------------------------------
Btree shuf | 41m,  1.3G, 42%  | 5:00s, 180M, 88%  | 6.4s, 3.9M, 86%
      sort | 7m,   920M, 91%  | 1:50s, 120M, 99%  | 2.9s, 2.6M, 97%
Hash  shuf | 44m,  1.1G, 39%  | 5:30s, 129M, 87%  | 6.2s, 2.4M, 98%
      sort | 47m,  1.1G, 36%  | 5:30s, 129M, 86%  | 6.2s, 2.4M, 94%
-------------------------------------------------------------------------
Speedup    | 5x               | 2.7x              | 2.2x

最大のデータセットでは、並べ替えられた挿入により 5 倍のスピードアップが得られます。最小でも 2 倍のスピードアップが得られますが、データがメモリに簡単に収まるため、CPU 使用率は常に高くなります。これは、ページ キャッシュに加えて別の効率の源から恩恵を受けていることを意味しているように思われます。また、5 倍の速度向上は、実際にはページ キャッシュと他の何か (おそらく、より優れたツリー バランス) によるものでしたか?

いずれにせよ、私は Btree 形式を好む傾向があります。Btree 形式の方が高速なバッチ操作が可能だからです。最終的なデータベースがランダムにアクセスされる場合でも、開発、テスト、および保守にはバッチ操作を使用します。これらをスピードアップする方法を見つけることができれば、生活は楽になります。

于 2015-11-16T01:52:26.863 に答える
2

データセットとキーに依存します 小さなデータセットでは、ベンチマークはほぼ同じになりますが、大きなデータセットでは、キーの種類/データの量によって異なる場合があります。通常、b ツリーのメタデータがキャッシュを超えて多くの io を実行するまでは、b ツリーの方が優れています。その場合は、ハッシュの方が優れています。また、あなたが指摘したように、b ツリーの挿入はより高価です。挿入が多く、読み取りが少ないことがわかった場合は、ハッシュが優れている可能性があります。挿入がほとんどなく、読み取りが多い場合、b ツリーは良くなる。

パフォーマンスが本当に気になる場合は、両方の方法を試して、独自のベンチマークを実行できます =]

于 2010-11-09T00:29:27.880 に答える
0

このアーキテクチャの記事で、Berkeley DB の 2 人の主な著者を引用すると、次のようになります。

Btree と Hash アクセス方法の主な違いは、Btree はキーの参照の局所性を提供しますが、Hash は提供しないことです。これは、Btree がほぼすべてのデータ セットに適したアクセス方法であることを意味します。ただし、ハッシュ アクセス方式は、Btree インデックス構造でさえもメモリに収まらないほど大きなデータ セットに適しています。その時点で、インデックス構造よりもデータにメモリを使用することをお勧めします。このトレードオフは、メイン メモリが現在よりも一般的に小さかった 1990 年には、より理にかなっています。

そのため、組み込みデバイスや特殊なユース ケースでは、ハッシュ テーブルが機能する可能性があります。BTree はBtrfsのような最新のファイルシステムで使用されており、データベースまたはファイルシステムを構築するためのアイデアのデータ構造です。

于 2015-01-30T21:09:25.897 に答える