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树与哈希表

回答

相关问题