Для того, чтобы считывать данные максимально быстро, программа должна использовать оператор Visual Basic Get для чтения узла целиком. Если использовать цикл For для чтения ключей и данных для каждого элемента по очереди, то программе придется обращаться к диску при чтении каждого элемента. Это намного медленнее, чем считывание всего узла сразу. В одном из тестов, для массива из 1000 элементов определенного пользователем типа чтение элементов по одиночке заняло в 27 раз больше времени, чем чтение их всех сразу. Следующий код демонстрирует оба способа чтения данных из узла:
Dim i As Integer
Dim node As BtreeNode
' Медленный способ доступа к данным.
For i = 1 To KEYS_PER_NODE
Get #filenum, , node.Key(i)
Next i
' Быстрый способ доступа к данным.
Get #filenum, , node
Каждый поиск в Б‑дереве начинается с корневого узла. Можно ускорить поиск, если корневой узел будет все время находиться в памяти. Тогда во время поиска придется на один раз меньше обращаться к диску. При этом все равно необходимо записывать корневой узел на диск при каждом его изменении, иначе при повторной загрузке после отказа программы изменения в Б‑дереве будут потеряны.
Можно также кэшировать в памяти и другие узлы Б‑дерева. Если хранить в памяти все дочерние узлы корня, то их также не потребуется считывать с диска. Для Б‑дерева порядка K, корневой узел будет иметь от 1 до 2 * K ключей и поэтому у него будет от 2 до 2 * K + 1 дочерних узлов. Это значит, что в этом случае придется кэшировать до 2 * K + 1 узлов.
Программа также может кэшировать узлы при обходе Б‑дерева. Например, при прямом обходе программа обращается к каждому узлу и затем рекурсивно обходит все его дочерние узлы. При этом она вначале спускается к первому дочернему узлу, а после возврата переходит к следующему. При каждом возврате, программа должна снова обратиться к родительскому узлу, чтобы определить, к какому из дочерних узлов обращаться в следующую очередь. Кэшируя родительский узел в памяти, программа избегает необходимости снова считывать его с диска.
Применение рекурсии позволяет программе автоматически сохранять узлы в памяти без использования сложной схемы кэширования. При каждом вызове рекурсивного алгоритма обхода, определяется локальная переменная, в которой находится узел до тех пор, пока он не понадобится. При возврате из рекурсивного вызова Visual Basic автоматически освобождает эту переменную. Следующий код демонстрирует, как можно реализовать этот алгоритм обхода на языке Visual Basic.
=======181
Private Sub PreorderPrint(node_index As Integer)
Dim i As Integer
Dim node As BtreeNode
Get #filenum, node_index, node ' Кэшировать узел.
Print node_index ' Обращение к узлу.
For i = 0 To KEYS_PER_NODE
If node.Child(i) < 0 Then Exit For ' Вызов потомков.
PreorderPrint node.Child(i) ' Вызов потомка.
Next i
End Sub
Программа Bplus работает с базой данных на основе Б+дерева, используя два файла данных. Файл Custs.DAT содержит записи с данными о клиентах, а файл Custs.IDX — узлы Б+дерева.
Чтобы добавить новую запись в базу данных, введите данные в поле Customer Record (Запись о клиенте), и затем нажмите на кнопку Add. Для поиска записи заполните поля Last Name (Фамилия) и First Name (Имя) в верхней части формы и нажмите на кнопку Find (Найти).
На рис. 7.23 показано окно программы после выполнения поиска записи для Рода Стивенса. Статистика внизу показывает, что данные были найдены в записи номер 302 после всего лишь трех обращений к диску. Высота Б+дерева в программе равна 3, и оно содержит 1303 записей данных и 118 блоков.
Когда вы вводите запись или проводите поиск, программа Bplus выбирает эту запись из файла. После нажатия на кнопку Remove программа удаляет запись из базы данных.
@Рис. 7.23. Программа Bplus
========182
Если выбрать в меню Display (Показать) команду Internal Nodes (Внутренние узлы), то программа выведет список внутренних узлов дерева. Она также выводит рядом с каждым узлом ключи, чтобы показать внутреннюю структуру дерева.
При помощи команды Complete Tree (Все дерево) из меню Display можно вывести структуру дерева целиком. Данные о клиентах выводятся внутри пунктирных скобок.
Кроме обычных полей адреса и фамилии, программа Bplus также включает поле NextGarbage, которое программа использует для работы со связным списком неиспользуемых в файле записей.
Type CustRecord
LastName As String * 20
FirstName As String * 20
Address As String * 40
City As String * 20
State As String * 2
Zip As String * 10
Phone As String * 12
NextGarbage As Long
End Type
' Размер записи данных о клиенте.
Global Const CUST_SIZE = 20 + 20 + 40 + 20 + 2 + 10 + 12 + 4
Внутренние узлы Б+дерева содержат ключи, которые используются для поиска данных о клиенте. Ключом для записи является фамилия клиента, дополненная в конце пробелами до 20 символов и заканчивающаяся запятой, за которой следует имя клиента, дополненное пробелами до 20 символов. Например, "Washington..........,George..............". При этом полная длина ключа составляет 41 символ.
Каждый внутренний узел также содержит указатели на дочерние узлы. Эти указатели определяют положение записей с данными о клиенте в файле Custs.DAT. Узлы также включают переменную NumKeys, которая содержит число используемых ключей.
Программа читает и пишет данные блоками примерно по 1024 байта. Если предположить, что блок содержит K ключей, то в каждом блоке будет K ключей длиной 41 байт, K + 1 указателей на дочерние узлы длиной по 4 байта, и двухбайтное целое число NumKeys. При этом блоки должны иметь максимально возможный размер и быть не больше 1024 байт.
Решив уравнение 41 * K + 4 * (K + 1) + 2 <= 1.024, получим K <= 22,62, поэтому K должно быть равно 22. В этом случае Б+дерево должно иметь 11 порядок, поэтому оно содержит по 22 ключа в каждом блоке. Каждый блок занимает 41 * 22 + 4 * (22 + 1) + 2 = 996 байт. Следующий код демонстрирует определение блоков в программе Bplus.
=======183
Const KEY_SIZE = 41
Const ORDER = 11
Global Const KEYS_PER_NODE = 2 * ORDER
Type Bucket
NumKeys As Integer
Key(1 To KEYS_PER_NODE) As String * KEY_SIZE
Child(0 To KEYS_PER_NODE) As Long
End Type
Global Const BUCKET_SIZE = 2 + _
KEYS_PER_NODE * KEY_SIZE + _
(KEYS_PER_NODE + 1) * 4
Программа Bplus записывает блоки Б+дерева в файле Custs.IDX. Первая запись в этом файле содержит заголовок, который описывает текущее состояние Б+дерева. В заголовок входит указатель на корневой узел, текущая высота дерева, указатель на первый пустой блок в файле Custs.IDX, и указатель на первый пустой блок в файле Custs.DAT.
Чтобы упростить чтение и запись заголовка, можно определить еще одну структуру, которая имеет в точности такой же размер, что и блоки данных, но содержит поля заголовка. Последнее поле в определении — это строка, которая заполняет конец структуры, чтобы ее размер был точно равен размеру блока.
Global Const HEADER_PADDING = _
BUCKET_SIZE - (7 * 4 + 2)
Type HeaderRecord
NumBuckets As Long
NumRecords As Long
Root As Long
NextTreeRecord As Long
NextCustRecord As Long
FirstTreeGarbage As Long
FirstCustGarbage As Long
Height As Integer
Padding As String * HEADER_PADDING
End Type
При запуске программы она запрашивает директорию, в которой находятся данные, и затем открывает файлы Custs.DAT файлы Custs.IDX в этой директории. Если эти файлы не существуют, то программа их создает. В противном случае, она считывает заголовок с информацией о дереве из файла Custs.IDX. Затем она считывает корневой узел Б+дерева и кэширует его в памяти.
Спускаясь по дереву при вставке или удалении элемента, программа кэширует элементы, к которым она обращается. При рекурсивном возврате эти узлы могут понадобиться снова, если происходило разбиение, слияние или другое переупорядочение узлов. Так как программа кэширует узлы на пути сверху вниз, они будут доступны при возвращении обратно.
Увеличение размера блоков позволяет сделать Б+деревья более эффективными, но при этом тестировать их вручную будет сложнее. Чтобы высота Б+дерева 11 порядка стала равна 2, необходимо добавить к базе данных 23 элемента. Чтобы увеличить высоту дерева до 3 уровня, необходимо добавить более 250 дополнительных элементов.
=======184
Чтобы было проще тестировать программу Bplus, вы можете захотеть уменьшить порядок Б+дерева до 2. Для этого закомментируйте в файле Bplus.BAS строку, которая определяет 11 порядок, и уберите комментарий из строки, которая задает 2 порядок:
'Const ORDER = 11
Const ORDER = 2
Команда Create Data (Создать данные) в меню Data (Данные) позволяет быстро создать множество записей данных. Введите число записей, которые вы хотите создать, и число, которое программа должна использовать для создания первого элемента. Затем программа создаст записи и вставит их в Б+дерево. Например, если задать в программе создание 100 записей, начиная со значения 200, то программа создаст записи 200, 201, … 299, которые будут выглядеть так:
FirstName: First 0000200
LastName: Last 0000200
Address: Addr 0000200
Cuty: City 0000200
Применение сбалансированных деревьев в программе позволяет эффективно работать с данными. Для записи больших баз данных на дисках или других относительно медленных запоминающих устройствах особенно удобны Б+деревья высокого порядка. Более того, можно использовать несколько Б+деревьев для создания нескольких индексов одного и того же большого набора данных.
В главе 11 описана альтернатива сбалансированным деревьям. Хеширование в некоторых случаях позволяет добиться еще более быстрого доступа к данным, хотя оно и не позволяет выполнять такие операции, как последовательный вывод записей.
========185
Многие сложные реальные задачи можно смоделировать при помощи деревьев решений (decision trees). Каждый узел дерева представляет один шаг решения задачи. Каждая ветвь в дереве представляет решение, которое ведет к более полному решению. Листья представляют собой окончательное решение. Цель заключается в том, чтобы найти «наилучший» путь от корня к листу при выполнении определенных условий. Эти условия и значение понятия «наилучший» для пути зависит от задачи.
Деревья решений обычно имеют громадный размер. Дерево решений для игры в крестики‑нолики содержит более полумиллиона узлов. Эта игра довольно проста, и многие реальные задачи намного более сложны. Соответствующие им деревья решений могли бы содержать больше узлов, чем число атомов во вселенной.