Для многих приложений доступ к базе данных осуществляется случайным образом, в интерактивном режиме или с помощью «транзакций».Это может произойти, если у вас есть данные, поступающие с веб-сервера.Однако вам часто приходится заполнять большую базу данных одновременно, как «пакетную» операцию.Это может произойти, если вы выполняете проект анализа данных или переносите старую базу данных в новый формат.
При одновременном заполнении базы данных предпочтительным является B-дерево или другой отсортированный индекс, поскольку онпозволяет выполнять пакетные вставки гораздо эффективнее.Это достигается путем сортировки ключей перед помещением их в базу данных.Заполнение базы данных 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;
Мы можем протестировать его с помощью файла индекса дампа Википедии из 16 миллионов записей.(Я использую это на 800-МГц 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 время создания одинаково медленно, независимо от того, отсортированы входные данные или нет.Также обратите внимание, что размер файла базы данных меньше для отсортированных вставок;по-видимому, это связано с балансировкой деревьев.
Ускорение должно быть из-за какого-то кеширования, но я не уверен, где.Вероятно, у нас меньше пропусков кэша в кэше страниц ядра с отсортированными вставками.Это согласуется с показателями использования ЦП - при пропадании кэша страницы процесс должен ждать, пока страница извлекается с диска, поэтому загрузка ЦП ниже.
Я провел те же тестыдля сравнения также с двумя меньшими файлами.
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 раза - даже если данные легко помещаются в память, так что загрузка процессора всегда высока.Похоже, это подразумевает, что мы извлекаем выгоду из другого источника эффективности в дополнение к кешу страниц, и что 5-кратное ускорение фактически было обусловлено равными частями кеша страниц и чем-то еще - возможно, лучшая балансировка дерева?В любом случае я предпочитаю формат Btree, потому что он позволяет выполнять более быстрые пакетные операции.Даже если конечная база данных доступна случайным образом, я использую пакетные операции для разработки, тестирования и обслуживания.Жизнь станет проще, если я найду способ ускорить их.