B+ деревья

   
На этом шаге мы рассмотрим B+ деревья .

   
B+ дерево является структурой данных, которую можно применять для очень эффектного метода сортировки большого
количества данных; В+ деревья дают возможность использовать эффективный алгоритм поиска и аналогичны
указателям базы данных (В+ деревья иногда сравнивают с указателями).

   
В Visual Prolog B+ деревья находятся во внешней базе данных. Каждый вход в дерево - это пара величин: ключевая
строка и связанный с ней указатель базы данных. При создании базы данных вы сначала заводите в ней запись и
определяете ключ для этой записи. Затем Visual Prolog включает этот ключ и указатель, соответствующий этой записи,
в В+ дерево.

   
При поиске записи в базе данных все, что необходимо сделать, - применить ключ для этой записи, и В+ дерево выдаст
вам соответствующий указатель. Используя указатель, вы можете выбрать запись из базы данных. По мере построения
дерева его элементы содержатся в порядке, определяемом ключами. Таким образом, мы можете легко получить
отсортированный список записей.

   
B+ дерево подобно бинарным деревьям, за исключением того, что в В+ дереве более одна ключевая строка запоминается
в каждом узле. В+ деревья сбалансированы; это значит, что пути поиска каждого ключа в "листьях" дерева имеют одну
и ту же длину. Вследствие этого, поиск каждого ключа (среди миллиона ключей) требует
только нескольких операций доступа к диску, в зависимости от того, как много ключей запоминается в каждом узле.

   
Хотя B+ деревья помещаются во внешних базах данных, они не нуждаются в указана термы в той же самой базе данных.
Есть возможность иметь базу данных, содержащую ряд цепочек и другую базу данных с В+ деревом, указывающим на
термы в этих цепочках.

Страницы, порядок и длина ключа

   
В B+ дереве ключи сгруппированы в страницы, причем каждая страница имеет одинаковый размер, и все страницы могут
содержать, одно и то же число ключей. Это , что все ключи B+ дерева должны иметь, одинаковый размер. Размер
ключей определяется аргументом KeyLen, который вы должны определить в момент создания B+ дерева.
При попытке внесения в В+ дерево строки длиннее, чем KeyLen, Visual Prolog обрежет ее. В общем, вы
должны выбрать минимально возможную величин для KeyLen в целях экономии памяти и увеличения быстродействия.

   
В момент создания В+ дерева необходимо задать величину аргумента Order. Этот аргумент определяет, сколько ключей
должно запоминаться в каждом узле дерева. Наилучшая величина аргумента выбирается методом проб и ошибок.
Хорошее первое приближение для Order - это 4, что соответствует запоминанию от 4 до 8 ключей в каждом узле. Вы
можете выбрать величину Order экспериментально, т. к. скорость поиска в В+ дереве зависит от величин KeyLen и Order,
числа ключей в В+ дереве и конфигурации вашей вычислительной системы.

Двойные ключи

   
Создавая В+ дерево, вы должны предусмотреть возможность использования повторяющихся ключей. Например, если
вы создаете В+ дерево для базы данных покупателей, в которой ключом является фамилия покупателя, вам необходимо
учесть всех покупателей с фамилией Смит. Здесь помогут двойные ключи в В+ дереве.

   
Когда вы удаляете терм из базы данных, необходимо удалить соответствующий вход в В+ дерево с двойными ключами
путем задания как ключа, так и указателя данных.

Множественный просмотр

   
Для того чтобы иметь более одного внутреннего указателя на одно и то же В+ дерево, вы можете открыть это
дерево несколько раз. Заметьте, одна к В+ дерево, на которое ссылается несколько указателей, не может быть
обновлено пока не удалены дополнительные указатели: для этого требуется закрытие В+ дерева соответствующее число раз.

   
На следующем шаге мы рассмотрим стардатные предикаты для B+ деревьев.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий