285
правок
Изменения
→Назначение
<wikitex>B-деревья разработаны для использования на дисках (в файловых системах) или иных вторичных устройствах хранения информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья, но они лучше минимизируют количество операций чтения-записи в диске.
=== Использование во вторичной памяти ===
Как известно, наряду с оперативной памятью (первичной памятью) в компьютере используется так называемая вторичная память, как правило, представляющая собой магнитные диски (или твердотельный накопитель).
Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо, гораздо медленнее оперативной памяти. Механическое движение головки относительно диска определяется двумя компонентами — перемещением головки по радиусу и вращением дисков. При скорости вращения 7200 оборотов в минуту один оборот требует примерно 8.33 мс, что почти на 5 порядков превышает время обращения к оперативной памяти (которое составляет примерно 100 нс). То есть, пока мы ждем оборота диска, чтобы считать необходимые нам данные, из оперативной памяти мы могли бы получить эти данные почти 100000 раз. В среднем приходится ждать только половину оборота диска, но это практически ничего не меняет. Радиальное перемещение головок тоже требует времени.
Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц (pages) одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется от $2^{11}$ до $2^{14}$ Байт. После того , как головка позиционирована на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, операции чтения чтение/запись становится полностью электронным процессами, не зависящими от поворота диска, и записи выполняются очень диск может быстрочитать или писать крупные объёмы данных.
В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которыми можно управлять. Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском $Disk_Read$ и $Disk_Write$, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.
Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. </wikitex>
