Berkeleydb - B樹與哈希表

我想了解在使用BerkeleyDB：B-Tree與HashTable時應該如何選擇訪問方法。 Hashtable提供了O（1）查找，但是插入操作很昂貴（使用線性/可擴展散列，我們得到了分段O（1）來插入）。但是B樹提供了log N（base B）查找和插入時間。 B-Tree還可以支持範圍查詢並允許按排序順序訪問。Berkeleydb - B樹與哈希表

除了這些考慮，還應考慮哪些因素？
如果我不需要支持範圍查詢，我可以使用Hashtable訪問方法嗎？

來源

2010-11-09 rakeshr

這取決於您的數據集和鍵在小數據集上，您的基準測試將接近相同，但是對於較大的數據集，它可以根據鍵的類型/您擁有多少數據而有所不同。通常B樹是更好的，直到btree元數據超過你的緩存，它最終會做很多的IO，在這種情況下，散列更好。同樣如你所指出的，如果你發現你會做大量的插入操作和很少的讀取操作，那麼b-tree插入會更加昂貴，如果你發現你做了很少的插入操作，但是大量的讀取操作，b-tree可能會更好會更好。

如果你真的關心性能，你可以嘗試這兩種方法和運行自己的基準=]

來源

2010-11-09 00:29:27 superfro

當你的數據集變得非常大，B樹仍然是更好，因爲大部分的內部元數據可能仍適合緩存。哈希本質上（統一的隨機數據分佈）本質上是緩存不友好的。也就是說，一旦數據集的總大小超過工作內存大小，散列性能就會下降，而B樹性能會優雅地降低（對數地，實際上）。

來源

2012-08-23 01:24:27 hyc

引述的Berkeley DB的兩個主要作者在建築this寫了起來：

B樹和Hash訪問方法之間的主要區別是， B樹提供的鑰匙局部性，而散列不不。這個意味着Btree是幾乎所有數據集的正確訪問方法。然而，哈希訪問方法適用於大數據集，因此甚至連Btree索引結構都不適合內存。在這一點上，最好使用內存數據而不是索引結構。這種權衡在1990年更有意義，當時主要的內存通常比今天小得多。

因此，也許在嵌入式設備和專用用例中，哈希表可能有效。 BTree用於現代文件系統，如Btrfs，它幾乎是構建數據庫或文件系統的想法數據結構。

來源

2015-01-30 21:09:25 simbo1905

對於許多應用程序，數據庫是隨機訪問，交互式地訪問或「交易」。如果您有來自網絡服務器的數據，則可能會發生這種情況。但是，您通常必須一次填充大型數據庫，作爲「批處理」操作。如果您正在執行數據分析項目，或者將舊數據庫遷移爲新格式，則可能會發生這種情況。

當您一次填充數據庫時，B-Tree或其他排序索引是更可取的，因爲它允許批量插入到的效率更高。這是通過將鍵放入數據庫之前完成的。當條目未排序時，填充BerkeleyDB數據庫1000萬個條目可能需要一個小時，因爲每個訪問都是緩存未命中。但是當條目被排序時，同一個過程可能只需要十分鐘。連續鍵的接近意味着您幾乎可以在所有插入中使用各種緩存。快速排序可以快速完成，所以整個操作可以通過在插入數據之前對數據進行排序來加速多次，僅爲。使用散列表索引，，因爲您事先並不知道哪些密鑰會在其他每個旁邊結束，所以此優化是不可能的。

更新：我決定提供一個實際的例子。它是基於下面的腳本「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

可以看到，預分類的B樹鍵滴插入時間從41分鐘下降到7分鐘。排序只需要1分鐘，所以有一個巨大的淨收益 - 數據庫創建速度提高了5倍。使用哈希格式，無論輸入是否排序，創建時間同樣很慢。另請注意，對於排序的插入，數據庫文件大小較小;據推測這與樹木平衡有關。

加速必須是由於某種緩存，但我不知道在哪裏。使用排序插入的內核的頁緩存很可能會減少緩存未命中次數。這與 CPU使用率編號一致 - 當頁面緩存未命中時，則在從磁盤檢索頁面時，進程必須等待，因此CPU使用率爲降低。

我用兩個較小的文件進行了相同的測試，以便進行比較。

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倍加速。儘管數據最小，我們仍然可以獲得2x加速 - 即使數據很容易放入內存中，CPU使用率始終很高。這似乎是暗示除了頁面緩存外，我們還從另一個效率來源中獲益，並且5倍加速實際上是由於等於頁面緩存等等 - 可能是更好的樹平衡？

無論如何，我傾向於選擇Btree格式，因爲它允許更快速地批量操作。即使隨機訪問最終數據庫，我也會使用批處理操作進行開發，測試和維護。如果我能找到加快速度的方法，生活會更容易。

來源

2015-11-16 01:52:26 Metamorphic

Berkeleydb - B樹與哈希表

回答

相關問題