В-деревей

Cтраница 1

Алгоритмы В-деревьев строятся на основе этого базового набора абстракций. Как и в главе 13, существует значительная свобода в выборе конкретных представлений таких деревьев. Для внешнего поиска мы используем еще более простое представление в виде упорядоченного массива, при условии, что значение М достаточно велико, чтобы Л / - узлы заполняли страницу. Коэффициент ветвления равен, по меньшей мере, М / 2, поэтому, как следует из леммы 16.1, количество зондирований, необходимое для выполнения любого поиска или вставки, по сути, постоянно. [1]

При использовании В-деревьев каждый поиск или вставка привязывается к корню, поэтому корень всегда будет присутствовать в кэше. В противном случае, при достаточно большом значении М, типичные случаи поиска или вставки сопряжены максимум с двумя случаями отсутствия в кэше. При достаточно большом объеме кэшпамяти существует высокая вероятность того, что первая страница ( дочерняя страница корня), к которой происходит обращение при поиске, уже присутствует в кэше, поэтому средние затраты на один поиск, скорее всего, будут значительно меньше двух зондирований. [2]

Логическая структура глобального массива А. [3]

Из физической структуры используемых В-деревьев следует, что поиск требуемого индекса ведется в пределах не более чем одного блока на каждом уровне, что позволяет осуществлять поиск глобальных узлов строго сверху вниз в дереве, без перебора блоков продолжения на одном уровне. [4]

Как и в случае В-деревьев, на каждой странице остается свободное место, чтобы можно было выполнять разделение после вставки; это упрощает код. Следует снова отметить, что эта технология имеет небольшое практическое значение, и ее влиянием можно пренебречь при анализе. [5]

В системе ДИАМС свойства В-деревьев формулируются следующим образом. [6]

Рассмотрите эвристический вариант родственного разделения В-деревьев ( или В - дерево): когда требуется разделить узел, поскольку он содержит М записей, мы объединяем узел с его родственным узлом. Если родственный узел содержит k записей, при k М - 1, мы перераспределяем элементы, помещая и в родственный, и в полный узел приблизительно по ( Л / k) / 2 записей. В противном случае мы создаем новый узел и помещаем в каждый узел дерева приблизительно по 2Л / / 3 записей. Кроме того, мы позволяем корню разрастаться, чтобы в нем могло содержаться около 4Л / / 3, разделяя его и создавая новый корневой узел с двумя записями, когда его размер достигает этого предельного значения. [7]

Так же как и в случае В-деревьев, правильная реализация операции remove представляет собой сложную задачу, но разрешение наличия незаполненных страниц - легко реализуемая альтернатива, которая может оказаться эффективной во многих возникающих на практике ситуациях. [8]

Как обычно, эта реализация операции search для В-деревьев основывается на рекурсивной функции. Для внутренних узлов ( имеющих положительную высоту) мы выполняем просмотр с целью отыскания ключа, который больше искомого, и осуществляем рекурсивный вызов поддерева, указанного предыдущей связью. Для внешних узлов ( высота которых равно 0) мы выполняем просмотр, чтобы выяснить, содержат ли они элемент, ключ которого равен искомому. [9]

С точки зрения производительности наибольший интерес представляют количество используемых страниц ( как и в случае В-деревьев) и размер каталога. Для этого алгоритма рандомизация обеспечивается хеш-функциями, поэтому характеристики производительности, определенные для среднего случая, сохраняются для любой последовательности N различных вставок. [10]

Если используемая система поддерживает виртуальную память, разработайте и проведите эксперименты с целью сравнения производительности В-деревьев с производительностью бинарного поиска при выполнении случайных поисков в очень большой таблице символов. [11]

В частности, структура данных, используемая для расширяемого хеширования, значительно проще использованной для В-деревьев. Значение d выбирается достаточно большим, чтобы на каждой странице гарантированно хранилось менее М элементов. [12]

Два последних свойства в этом перечне несущественны, однако удобны во многих ситуациях и обычно встречаются в реализациях В-деревьев. [13]

Тогда можно поддерживать каталог 2d ссылок различных страниц, использовать d разрядов ключей для индексных указателей внутрь каталога и хранить на одной и той же странице все ключи, первые k разрядов которых совпадают, как показано на рис. 16.10. Подобно тому, как это делалось в случае В-деревьев, элементы на страницах хранятся по порядку, и достигнув страницы, которая соответствует элементу с заданным искомым ключом, мы выполняем последовательный поиск. [14]

Чтобы вставить элемент в расширяемую хеш-таблицу, мы выполняем поиск; затем мы вставляем элемент в указанную страницу; далее, разделяем страницу, если вставка вызывает переполнение. Общая схема не отличается от используемой для В-деревьев, но алгоритмы поиска и разделения иные. Функция разделения создает новый узел, затем проверяет / с-тый разряд ( считая слева) ключа каждого элемента: если разряд равен 0, элемент остается в старом узле; если он равен 1, элемент перемещается в новый узел. Значение k 1 присваивается полю заведомо идентичных ведущих разрядов обоих узлов после разделения. Если этот процесс не приводит к помещению по меньшей мере одного ключа в каждом узле, разделение выполняется снова, пока подобным образом не будут разделены все элементы. В конце процесса мы вставляем указатель нового узла в каталог. [15]

Страницы: 1 2