Каждый поиск в Б+дереве начинается с корневого узла. Ускорить поиск можно,
если корневой узел будет все время находиться в памяти. Тогда при поиске элемента
программа обращается к диску меньше на один раз. При этом все равно следует за-
писывать корневой узел при каждом его изменении на диск, в обратном случае при
повторной загрузке после отказа программы изменения в дереве будут потеряны.
Можно также кэшировать в памяти другие узлы Б+дерева Если хранить в па-
мяти все дочерние записи корневого узла, то программе не нужно будет считывать
их с диска. Для Б+дерева порядка К корневой узел содержит от 1 до 2 * К ключей
и поэтому имеет от 2 до 2 * К + 1 дочерних узла. Это означает, что необходимо
кэшировать до 2 * К + 1 узлов.
Программа может также кэшировать узлы при обходе дерева. При прямом об-
ходе, например, программа обращается к каждому узлу и затем рекурсивно обхо-
дит все его дочерние узлы. Программа спускается к первому дочернему узлу, а пос-
ле возврата переходит к следующему. При каждом возврате программа должна
снова обратиться к родительскому узлу, чтобы определить, к какому из дочерних
узлов обращаться в следующую очередь. Кэшируя родительский узел, программа
избегает необходимости снова считывать его с диска.
Рекурсия позволяет программе автоматически сохранять узлы в памяти без
использования сложной схемы кэширования. При каждом обращении к рекурсив-
ному алгоритму обхода объявляется локальная переменная, в которой находится
узел до тех пор, пока он не понадобится. При возврате из рекурсивного вызова
Delphi автоматически освобождает эту переменную. Следующий код демонстри-
рует, как можно реализовать этот алгоритм в Delphi:
procedure Preorder(node_number : Longint);
var
i : Integer;
node : BtreeNode;
begin
// Считывание узла.
Seek(IdxFile,node_nuniber);
Read(IdxFile,node);
// Посещение узла.
VisitNode(node_number);
//Посещение дочерних узлов;
for i := 0 to KEYS_PER_NODE do
begin
if (node.Child[i] < 0) then break;
Preorder(node.Child[i]);
end;
end;
|
Главная
Каталог файлов
