Вопросы, связанные с обращением к диску

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

Псевдоуказатели

Коллекции и ссылки на объекты удобны для построения деревьев в памяти, но они могут быть бесполезны при хранении дерева на диске. Нельзя создать ссылку на запись в файле.

Вместо этого можно использовать методы работы с псевдоуказателями, похожие на те, которые были описаны во 2 главе. Вместо использования в качестве указателей на узлы дерева ссылок на объекты при этом используется номер записи узла в файле. Предположим, что Б+дерево 12 порядка использует 80‑байтные ключи. Структуру данных узла можно определить в следующем коде:

Global Const ORDER = 12

Global Const KEYS_PER_NODE = 2 * ORDER

Type BtreeNode

Key (1 To KEYS_PER_NODE) As String * 80 ' Ключи.

Child (0 To KEYS_PER_NODE) As Integer ' Указатели потомков.

End Type

Значения элементов массива Child представляют собой номера записей из дочерних узлов в файле. Произвольный доступ к данным Б+дерева из файла осуществляется при помощи записей, которые соответствуют структуре BtreeNode.

@Рис. 7.22. Свободное заполнение Б‑дерева

======179

Dim node As BtreeNode

Open Filename For Random As #filenum Len = Len(node)

После открытия файла, при помощи оператора Get можно выбрать любую запись:

Dim node As BtreeNode

' Выбрать запись с номером recnum.

Get #filenum, recnum, node

Чтобы упростить работу с Б+деревьями, можно хранить узлы Б+дерева и записи данных в разных файлах и использовать для управления каждым из них псевдоуказатели.

Когда счетчик ссылок на объект становится равным нулю, то Visual Basic автоматически уничтожает его. Это облегчает работу со структурами данных в памяти. С другой стороны, если программе больше не нужна какая‑либо запись в файле, то она не может просто очистить все ссылки на нее. Если сделать так, то программа больше не сможет использовать эту запись, но запись по‑прежнему будет занимать место в файле.

Программа должна следить за неиспользуемыми записями, чтобы позднее можно было использовать их. Один из простых способов сделать это — вести связный список неиспользуемых записей. Если запись больше не нужна, она добавляется в список. Если программе нужно место для новой записи, она удаляет одну запись из списка. Если программе нужно вставить еще один элемент, а список пуст, она увеличивает файл данных.

Выбор размера блока

Чтение данных с диска происходит блоками, которые называются кластерами. Размер кластера обычно составляет 512 или 1024 байта, или еще какое‑либо число байтов, равное степени двойки. Чтение всего кластера занимает столько же времени, сколько и чтение одного байта.

Можно воспользоваться этим фактом и создавать блоки, размер которых составляет целое число кластеров, а затем уместить в этот размер максимальное число ключей или записей. Например, предположим, что мы решили создавать блоки размером 2048 байт. При создании Б+дерева с 80‑байтными ключами в каждый блок можно поместить 24 ключа и 25 указателей (если указатель представляет собой 4‑байтное число типа long). Затем можно создать Б+дерево 12 порядка с блоками, которые определяются в следующем коде:

Global Const ORDER = 12

Global Const KEYS_PER_NODE = 2 * ORDER

Type BtreeNode

Key(1 To KEYS_PER_NODE) As String * 80 ' Ключ данных.

Child(0 To KEYS_PER_NODE) As Integer ' Указатели потомков.

End Type

=======180

Для того, чтобы считывать данные максимально быстро, программа должна использовать оператор 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