На этом шаге мы рассмотрим 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+ деревьев.
