Классика баз данных - статьи
Это первое из двух новых
Это первое из двух новых правил пяти минут, представленное в данной статье.
Табл. 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-деревьев, при работе с которыми не учитываются конкретные характеристики кэша.
