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