Оптимальная запись в BTree (Живительная сортировка-2)

lexa - 26/Ноя/2008 10:20

Интересным следствием из оптимальной записи в BTree является то, что кэш практически перестает быть нужен.

Действительно, нам локально-моментно нужно иметь в кэше по одной странице с каждого уровня дерева плюс место под пару страниц на сплит. Всего получается 4-6 страниц или меньше 50 килобайт для стандартных 8k-страниц.

Эксперименты подтверждают: уменьшение размера кэша с 100 мегабайт до 128k никак не ухудшают производительность. Даже нет смысла приводить результаты замеров, цифры просто такие же (плюс-минус разумный разброс в пару процентов).

Естественно, это относится и к чтению. Если вы собрались читать из BTree (а это не только Berkeley DB, но и большинство индексов в базах данных) много данных и ваше дерево не в памяти - отсортируйте ключи в том же порядке, в котором они в индексе/базе и вам за это воздастся.

Comments

maxcom (not verified) - 26/Ноя/2008 15:33

а зачем BTree, если сортировка по ключам в логике не используется? хеш-таблица лишена такого недостатка

lexa - 26/Ноя/2008 20:16

Если хэш в памяти - вопросов нет (надо смотреть на оверхеды и все такое, но принципиальных возражений нет)

Как только в память влезать перестаем - с хэшами начинается катастрофа, ибо любое обращение к этой конструкции с вероятностью (размер кэша/размер данных) преврашается в seek(rand()) и вместо сотен тысяч транзакций в секунду мы скатываемся в лучшем случае к первым сотням в секунду (от дисковой подсистемы зависит, на SSD будет быстрее, скажем 10^4 в секунду)

maxcom (not verified) - 27/Ноя/2008 14:30

наверное тут тоже поможет предварительная сортировка, только по значениям хеш-функции. Наверное получится оптимально, если хеш с открытой адресацией. Главное заранее предсказать количество элементов при помещении.

lexa - 27/Ноя/2008 14:41

Ну вот я токийский шкаф сейчас мучаю, пока не нравится :)

df_org (not verified) - 26/Ноя/2008 15:06

как же я отсортирую ключи, если они они поступают в своём собственном/случайном порядке?
Отдельный буфер для накопления и сортировки?

lexa - 26/Ноя/2008 15:29

Именно. Скока не жалко. Гораздо полезнее отвести буфер на это а не на свой кэш базы (в случае Berkeley DB всегда есть выбор).

Собственно, если посмотреть на предыдущий постинг и сделать поправку на то, что кэш вообще не нужен (нужно исчезающе мало), то получится что если выделить 300M на буфер сортировки а не на кэш, мы получаем ускорение в 130 раз (для данного конкретного примера с 18M записей).