logo标签列表

伯克利数据库 - B树与哈希表的比较

hashtableberkeley-dbb-tree
8

我试图理解在使用BerkeleyDB时应该选择哪种访问方法：B-Tree还是HashTable。

哈希表提供O(1)的查找，但插入操作很昂贵（使用线性/可扩展哈希我们可以得到摊销O(1)的插入）。但B树提供log N（基数为B）的查找和插入时间。 B-Tree还可以支持范围查询并允许按排序顺序访问。

  1. 除了这些考虑因素之外，还应该考虑什么？
  2. 如果我不需要支持范围查询，我可以只使用哈希表访问方法吗？
4个回答
6

当你的数据集变得非常大时，B树仍然更好，因为大部分内部元数据仍然可以适应缓存。哈希表由于其本质（数据的均匀随机分布）在缓存上不友好。也就是说，一旦数据集的总大小超过工作内存大小，哈希性能会急剧下降，而B树性能则会平稳地退化（实际上是对数级别的）。

3
这取决于您的数据集和键。在小型数据集上，您的基准测试结果将接近相同，但是在大型数据集上，它可能会因所用键类型/数据量而异。通常情况下，B树更好，直到B树元数据超过缓存并进行大量IO操作，此时哈希表更好。另外，正如您指出的，B树插入操作更昂贵，如果您发现自己需要频繁插入但读取较少，则哈希表可能更好；如果您发现自己很少插入但需要频繁读取，则B树可能更好。
如果您真的关心性能，可以尝试使用两种方法并运行自己的基准测试 =]
2
对于许多应用程序，数据库是随机访问的，可以进行交互式操作或使用“事务”。如果您从Web服务器中获取数据，则可能会发生这种情况。然而，您经常需要一次性填充大型数据库，作为“批量”操作。如果您正在进行数据分析项目或将旧数据库迁移到新格式，则可能会发生这种情况。
当您一次性填充数据库时，最好使用B-Tree或其他排序索引，因为它可以使批量插入更加高效。这是通过在将键放入数据库之前对其进行排序来实现的。如果输入项未排序，则填充包含1000万个条目的BerkeleyDB数据库可能需要一个小时，因为每个访问都是缓存未命中。但是，当输入项排序后，相同的过程可能只需要十分钟。连续键的接近意味着您几乎将为所有插入使用各种缓存。排序可以非常快速地完成，因此仅通过在插入数据之前对其进行排序，整个操作就可以加快几倍。使用哈希表索引，由于您无法预先知道哪些键将相邻，因此无法进行此优化。
更新：我决定提供一个实际示例。它基于以下脚本“ 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双核笔记本电脑上运行此程序，内存为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倍。即使数据集很小且容易适应内存，CPU使用率始终很高，我们仍然可以获得2倍的速度提升。这似乎意味着我们除了页面缓存之外还从其他效率来源受益，而5倍速度提升实际上是由于页面缓存和其他因素（也许是更好的树平衡）共同作用的。

无论如何，我倾向于使用Btree格式，因为它允许更快的批量操作。即使最终数据库以随机方式访问，我也会在开发、测试和维护过程中使用批处理操作。如果能找到加速这些操作的方法，那么生活就更轻松了。

0

引用 Berkeley DB 的两位主要作者在 this 架构的写作中所说：

Btree 和 Hash 访问方法的主要区别在于 Btree 提供了键的引用局部性，而 Hash 则没有。这意味着 Btree 是几乎所有数据集的正确访问方法；然而，当数据集太大以至于甚至无法将 Btree 索引结构放入内存时，Hash 访问方法是合适的。此时，最好使用内存来存储数据而不是索引结构。这种权衡在 1990 年时更有意义，因为当时主存通常比今天小得多。

因此，在嵌入式设备和专业用例中，哈希表可能会起作用。BTree 在现代文件系统（如 Btrfs）中被使用，并且它几乎是构建数据库或文件系统的理想数据结构。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接