我试图理解在使用BerkeleyDB时应该选择哪种访问方法:B-Tree还是HashTable。
哈希表提供O(1)的查找,但插入操作很昂贵(使用线性/可扩展哈希我们可以得到摊销O(1)的插入)。但B树提供log N(基数为B)的查找和插入时间。 B-Tree还可以支持范围查询并允许按排序顺序访问。
- 除了这些考虑因素之外,还应该考虑什么?
- 如果我不需要支持范围查询,我可以只使用哈希表访问方法吗?
我试图理解在使用BerkeleyDB时应该选择哪种访问方法:B-Tree还是HashTable。
哈希表提供O(1)的查找,但插入操作很昂贵(使用线性/可扩展哈希我们可以得到摊销O(1)的插入)。但B树提供log N(基数为B)的查找和插入时间。 B-Tree还可以支持范围查询并允许按排序顺序访问。
当你的数据集变得非常大时,B树仍然更好,因为大部分内部元数据仍然可以适应缓存。哈希表由于其本质(数据的均匀随机分布)在缓存上不友好。也就是说,一旦数据集的总大小超过工作内存大小,哈希性能会急剧下降,而B树性能则会平稳地退化(实际上是对数级别的)。
#!/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;
$ >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
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格式,因为它允许更快的批量操作。即使最终数据库以随机方式访问,我也会在开发、测试和维护过程中使用批处理操作。如果能找到加速这些操作的方法,那么生活就更轻松了。
引用 Berkeley DB 的两位主要作者在 this 架构的写作中所说:
Btree 和 Hash 访问方法的主要区别在于 Btree 提供了键的引用局部性,而 Hash 则没有。这意味着 Btree 是几乎所有数据集的正确访问方法;然而,当数据集太大以至于甚至无法将 Btree 索引结构放入内存时,Hash 访问方法是合适的。此时,最好使用内存来存储数据而不是索引结构。这种权衡在 1990 年时更有意义,因为当时主存通常比今天小得多。
因此,在嵌入式设备和专业用例中,哈希表可能会起作用。BTree 在现代文件系统(如 Btrfs)中被使用,并且它几乎是构建数据库或文件系统的理想数据结构。