7

我试图了解在使用 BerkeleyDB 时应该驱动访问方法的选择：B-Tree 与 HashTable。Hashtable 提供 O(1) 查找，但插入很昂贵（使用线性/可扩展散列，我们为插入分摊了 O(1)）。但是 B-Trees 提供 log N (base B) 查找和插入时间。B-Tree 还可以支持范围查询并允许按排序顺序访问。

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

4 回答 4

6

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

于 2012-08-23T01:24:27.987 回答
2

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

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

于 2010-11-09T00:29:27.880 回答
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 万个条目的 Wikipedia 转储索引文件对其进行测试。（我在 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 倍。使用 Hash 格式，无论输入是否排序，创建时间都同样慢。另请注意，排序插入的数据库文件大小较小；大概这与树平衡有关。

加速一定是由于某种缓存，但我不确定在哪里。很可能我们在带有排序插入的内核页面缓存中的缓存未命中率较低。这将与 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 使用率总是很高。这似乎意味着除了页面缓存之外，我们还从另一个效率来源中受益，并且 5 倍的加速实际上是由于页面缓存和其他东西 - 也许更好的树平衡？

无论如何，我更喜欢 Btree 格式，因为它允许更快的批处理操作。即使最终数据库是随机访问的，我还是使用批处理操作进行开发、测试和维护。如果我能找到一种方法来加快这些速度，生活会更轻松。

于 2015-11-16T01:52:26.863 回答
0

在这篇架构文章中引用 Berkeley DB 的两位主要作者：

Btree 和 Hash 访问方法之间的主要区别在于 Btree 提供了键的引用位置，而 Hash 没有。这意味着 Btree 是几乎所有数据集的正确访问方法；但是，哈希访问方法适用于数据集如此之大，以至于 Btree 索引结构都无法放入内存。在这一点上，最好将内存用于数据而不是索引结构。这种权衡在 1990 年更有意义，当时主存储器通常比今天小得多。

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

于 2015-01-30T21:09:25.897 回答