Размеры страниц
В дополнение к настройке на основе правила пяти минут имеется оптимизация, основанная на показателях эффективности доступа и заключающаяся в выборе оптимального размера узлов B-дерева. При выборе оптимального размера страницы минимизируется время, затрачиваемое на выполнение операций ввода-вывода при поиске от корня к листьям дерева. Достигается компромисс между коротким временем доступа (т.е. потребностью в небольших страницах) и сильным сокращением пространства поиска (т.е. потребностью в крупных страницах). Если внутри узлов B-дерева используется двоичный поиск, то сокращение пространства поиска измеряется логарифмом числа записей в каждом узле. Этот показатель в одной из предыдущих статей автора [] был назван полезностью (utility) узла. Эта оптимизация, по существу, эквивалентна той, которая описывалась в исходном исследовании B-деревьев [].
Табл. 4. Полезность страниц для узлов B-дерева на диске
| Размер страницы | Число записей в странице | Полезность узла | Время доступа | Полезность/время |
| 4 Кб | 140 | 7 | 12.0 мс | 0.58 |
| 16 Кб | 560 | 9 | 12.1 мс | 0.75 |
| 64 Кб | 2240 | 11 | 12.2 мс | 0.90 |
| 128 Кб | 4480 | 12 | 12.4 мс | 0.97 |
| 256 Кб | 8960 | 13 | 12.9 мс | 1.01 |
| 512 Кб | 17920 | 14 | 13.7 мс | 1.02 |
| 1 Мб | 35840 | 15 | 15.4 мс | 0.97 |
В табл. 4 эта оптимизация иллюстрируется для записей из 20-ти байт (типичных при отбрасывании префикса и суффикса []) и узлов, заполненных примерно на 70%. Не удивительно, что оптимальный размер узла B-дерева на современных дисках с высокой пропускной способностью намного больше размера страницы, используемого в традиционных системах баз данных. При использовании этих дисков для всех страниц небольшого размера доминирует время доступа, так что передача большего числа байт и, следовательно, большая полезность даются почти бесплатно.
Размер узла B-дерева в 256 Кб очень близок к оптимальному. Как показывает табл. 3, для этого размера страницы интервал равнозатратности для основной памяти и диска составляет 88 секунд. Для флэш-диска стоимостью $400 и традицонного вращающегося жесткого диска этот интервал составляет 337 секунд, или чуть больше пяти минут.
Это первое из двух новых правил пяти минут, представленное в данной статье.
Табл. 5. Полезность страниц для узлов B-дерева на флэш-диске
| Размер страницы | Число записей в странице | Полезность узла | Время доступа | Полезность/время |
| 1 Кб | 35 | 5 | 0.11 мс | 43.4 |
| 2 Кб | 70 | 6 | 0.13 мс | 46.1 |
| 4 Кб | 140 | 7 | 0.16 мс | 43.6 |
| 8 Кб | 280 | 8 | 0.22 мс | 36.2 |
| 16 Кб | 560 | 9 | 0.34 мс | 26.3 |
| 64 Кб | 2240 | 11 | 1.07 мс | 10.3 |
В таблице 3 интервал равнозатратности для страниц размером в 4 килобайта составляет 351 секунду. Это второе новое правило пяти минут.
Из наличия двух разных оптимальных размеров страниц следует то, что любой размер страниц для B-деревьев, одинаковый при использовании как флэш-памяти, так и традиционных вращающихся жестких дисков, не является оптимальным. Для оптимизации размеров страниц для обоих видов носителей требуются изменения в управлении буферами, распределении памяти и, частично, в логике работы с B-деревьями.
К счастью, Патрик О’Нейл (Patrick O’Neil) из Массачусетского университета уже разработал схему распределения памяти для B-деревьев, при использовании которой соседние листовые страницы обычно размещаются в одном непрерывном экстенте страниц []. При потребности в новой странице по причине расщепления узла выделяется другая страница в том же экстенте. Когда экстент переполняется, половина его страниц перемещается в заново выделенный экстент. Другими словами, логика B-деревьев по «отщеплению половины при переполнении» теперь применяется не только к страницам, содержащим записи, но и к дисковым экстентам, содержащим страницы.
При использовании SB-деревьев О’Нейла (S означает sequential, в данном случае, непрерывный) экстенты размером в 256 килобайт могут служить единицами передачи данных между флэш-памятью и диском, а страницы размером в 4 килобайта – единицей передачи между основной и флэш-памятью.
Аналогичные понятия «самоподобных» (self-similar) B-деревьев предлагались для более высоких уровней иерархии памяти (например, в форме B-деревьев строк кэша для поддержки таблиц преобразования адресов внутри страниц большого размера) []. Если учесть, что в настоящее время имеется, по крайней мере, три уровня B-деревьев и три размера узлов (т.е. строки кэша, страницы флэш-памяти и страницы диска), очень перспективными могут оказаться исследования B-деревьев, при работе с которыми не учитываются конкретные характеристики кэша.
