Обработка запросов
Подход самоподобности применяется как к структурам данных, таким как B-деревья, так и к алгоритмам. Например, в алгоритмах сортировки уже используются алгоритмы, подобные традиционным алгоритмам внешней сортировки с многоканальным (multiple way) слиянием, для слияния частичных результатов сортировки не только на диске, но и в основной памяти, где размеры начальных частей массива выбираются таким образом, чтобы размеры частичных результатов сортировки ограничивались размером кэша центрального процессора [,].
Такую же технику можно применить три, а не два раза: сначала частичные результаты сортировки, хранящиеся в основной памяти и ограниченные размером кэша, сливаются, образуя частичные результаты, хранящиеся в флэш-памяти и ограниченные размером основной памяти; потом, при выполнении очень крупных операций сортировки, частичные результаты сортировки, хранящиеся в флэш-памяти и ограниченные размером основной памяти, сливаются, образуя частичные результаты на диске; и, наконец, частичные результаты сортировки, хранящиеся на диске, сливаются для получения окончательного результата сортировки. Такие приемы, как упреждающее чтение, прогнозирование, отложенная запись и выбор оптимального размера страниц, заслуживают того, чтобы взглянуть на них по-новому при наличии многоуровневой иерархии памяти, включающей кэш, основную память, флэш-память и традиционные дисковые устройства. Затем на основе этих размеров страниц можно произвести вычисления величин интервалов равнозатратности и получить, тем самым, руководство для оценки оптимального объема ресурсов на каждом уровне памяти.
Можно предположить, что некоторая разновидность описанного алгоритма сортировки будет не только быстрой, но и эффективной в смысле энергопотребления. Хотя эффективность энергопотребления всегда была критичной для устройств с питанием от батарей, только в последнее время начали исследоваться проблемы обработки запросов с эффективным энергопотреблением []. Например, и для флэш-памяти, и для дисков размеры страниц, оптимальные с точки зрения энергопотребления, могут значительно отличаться от размеров страниц, оптимальных с точки зрения производительности.
Характер ввода-вывода внешней сортировки со слиянием аналогичен (хотя и в противоположном направлении) характеру ввода-вывода внешней сортировки с разделением (external partition sort), а также характеру ввода-вывода разделения при выполнении хэш-соединений и вычислении агрегатных функций на основе хэширования. Кроме того, при наличии трехуровневой иерархии памяти (или даже четырехуровневой, если принимать во внимание и кэши центральных процессоров), также требуется пересмотр двух последних разновидностей алгоритмов [].
Флэш-память со своим очень быстрым временем доступа может вновь пробудить интерес к исполнению запросов на основе индексов [, ]. Оптимальные размеры страниц и интервалы их удержания обсуждались в предыдущих разделах статьи.
