Это первое из двух новых
Это первое из двух новых правил пяти минут, представленное в данной статье.
Табл. 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 |
В табл. 5 иллюстрируются аналогичные вычисления для B-деревьев во флэш-памяти. По причине отсутствия механического перемещения головок и вращения время передачи доминирует даже для страниц небольшого размера. Оптимальный размер страницы для B-деревьев во флэш-памяти составляет 2 килобайта, намного меньше, чем в случае использования традиционных дисковых устройств.
В таблице 3 интервал равнозатратности для страниц размером в 4 килобайта составляет 351 секунду. Это второе новое правило пяти минут.
Из наличия двух разных оптимальных размеров страниц следует то, что любой размер страниц для B-деревьев, одинаковый при использовании как флэш-памяти, так и традиционных вращающихся жестких дисков, не является оптимальным. Для оптимизации размеров страниц для обоих видов носителей требуются изменения в управлении буферами, распределении памяти и, частично, в логике работы с B-деревьями.
К счастью, Патрик О’Нейл (Patrick O’Neil) из Массачусетского университета уже разработал схему распределения памяти для B-деревьев, при использовании которой соседние листовые страницы обычно размещаются в одном непрерывном экстенте страниц []. При потребности в новой странице по причине расщепления узла выделяется другая страница в том же экстенте. Когда экстент переполняется, половина его страниц перемещается в заново выделенный экстент. Другими словами, логика B-деревьев по «отщеплению половины при переполнении» теперь применяется не только к страницам, содержащим записи, но и к дисковым экстентам, содержащим страницы.
При использовании SB-деревьев О’Нейла (S означает sequential, в данном случае, непрерывный) экстенты размером в 256 килобайт могут служить единицами передачи данных между флэш-памятью и диском, а страницы размером в 4 килобайта – единицей передачи между основной и флэш-памятью.
Аналогичные понятия «самоподобных» (self-similar) B-деревьев предлагались для более высоких уровней иерархии памяти (например, в форме B-деревьев строк кэша для поддержки таблиц преобразования адресов внутри страниц большого размера) []. Если учесть, что в настоящее время имеется, по крайней мере, три уровня B-деревьев и три размера узлов (т.е. строки кэша, страницы флэш-памяти и страницы диска), очень перспективными могут оказаться исследования B-деревьев, при работе с которыми не учитываются конкретные характеристики кэша.
Содержание Назад Вперед