Berkeleydb - B-Tree与Hash表

Question

在使用BerkeleyDB :B树和HashTable时，我试图理解是什么驱动了访问方法的选择。Hashtable提供了O(1)查找，但是插入很昂贵(使用线性/可扩展散列，我们得到了用于insert的摊销O(1) )。但是B树提供了log N(基本B)查找和插入时间。B树还可以支持范围查询，并允许按排序顺序访问.

1. 除了这些考虑外，还应考虑哪些因素？
2. 如果我不需要支持范围查询，我可以只使用Hashtable访问方法吗？

Answer 1

当数据集变得非常大时，B树仍然更好，因为大多数内部元数据可能仍然适合缓存。哈希，本质上(数据的均匀随机分布)本质上是缓存-不友好。也就是说，一旦数据集的总大小超过工作内存大小，哈希性能就会下降，而B树性能则会优雅地下降(实际上是对数的)。

Answer 2

这取决于您的数据集和小数据集上的键，您的基准测试将接近相同，但是在较大的数据集上，它可能会根据键的类型/数据的大小而有所不同。通常b树更好，直到btree元数据超过缓存并最终执行大量io，在这种情况下哈希更好。另外，正如您所指出的，b树插入更昂贵，如果您发现您将执行大量插入而很少读取，则哈希操作可能会更好，如果您发现您只执行少量插入，但是大量读取，b-树可能会更好。

如果您真的关心性能，可以尝试这两种方法并运行您自己的基准测试=]

Answer 3

对于许多应用程序，数据库是随机访问、交互访问或使用“事务”访问的。如果有来自web服务器的数据，则可能会发生这种情况。但是，您通常必须同时填充一个大型数据库，作为“批处理”操作。如果您正在执行数据分析项目，或者将旧数据库迁移到新的格式，则可能会发生这种情况。

当您同时填充数据库时，B树或其他排序索引更好，因为它允许更有效地执行批处理插入。这是通过在将键放入数据库之前对它们进行排序来实现的。使用1,000万个条目填充BerkeleyDB数据库可能需要一个小时才能完成条目的排序，因为每次访问都是缓存丢失。但是，当对条目进行排序时，相同的过程可能只需要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万条目的维基百科转储索引文件来测试它。(我在一台800 this 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使用率较低。

为了比较，我也对两个较小的文件运行了相同的测试。

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的使用率总是很高。这似乎意味着，除了页面缓存之外，我们还从另一个效率来源中受益，而5x加速比实际上是由页面缓存和其他什么东西共同造成的--也许是更好的树平衡？

无论如何，我倾向于使用Btree格式，因为它允许更快的批处理操作。即使最终数据库是随机访问的，我也会使用批处理操作进行开发、测试和维护。如果我能找到加快速度的方法，生活就会更容易。