Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Программа Btree позволяет вам оперировать Б‑деревом. Введите текст, и нажмите на кнопку Add, чтобы добавить элемент в дерево. Для удаления элемента введите его значение и нажмите на кнопку Remove. На рис. 7.19 показано окно программы Btree с Б‑деревом 2 порядка.
@Рис. 7.19. Программа Btree
========175
Разновидности Б‑деревьев
Существует несколько разновидностей Б‑деревьев, из которых здесь описаны только некоторые. Нисходящие Б‑деревья (top‑down B‑trees) немного иначе управляют структурой Б‑дерева. За счет разбиения встречающихся полных узлов, эта разновидность алгоритма использует при вставке элементов более наглядную нисходящую рекурсию вместо восходящей. Эта также уменьшает вероятность возникновения длительной последовательности разбиений блоков.
Другой разновидностью Б‑деревьев являются Б+деревья (B+trees). В Б+деревьях внутренние узлы содержат только ключи данных, а сами записи находятся в листьях. Это позволяет Б+деревьям хранить в каждом блоке больше элементов, поэтому такие деревья короче, чем соответствующие Б‑деревья.
Нисходящие Б‑деревья
Подпрограмма, которая добавляет новый элемент в Б‑дерево, вначале выполняет рекурсивный поиск по дереву, чтобы найти блок, в который его нужно поместить. Когда она пытается вставить новый элемент на его место, ей может понадобиться разбить блок и переместить один из элементов узла в его родительский узел.
При возврате из рекурсивных вызовов процедуры, вызывающая процедура проверяет, требуется ли разбиение родительского узла. Если да, то элемент помещается в родительский узел. При каждом возврате из рекурсивного вызова, вызывающая процедура должна проверять, не требуется ли разбиение следующего предка. Так как эти разбиения блоков происходят при возврате из рекурсивных вызовов процедура, это восходящая рекурсия, поэтому иногда Б‑деревья, которыми манипулируют таким образом, называются восходящими Б‑деревьями (bottom‑up B‑trees).
Другая стратегия состоит в том, чтобы разбивать все полные узлы, которые встречаются процедуре на пути вниз по дереву. При поиске блока, в который нужно поместить новый элемент, процедура разбивает все повстречавшиеся полные узлы. При каждом разбиении узла, она помещает один из его элементов в родительский узел. Так как она уже разбила все выше расположенные полные узлы, то в родительском узле всегда есть место для нового элемента.
Когда процедура доходит до листа, в который нужно поместить элемент, то в его родительском узле всегда есть свободное место, и если программе нужно разбить лист, то всегда можно поместить средний элемент в родительский узел. Так как при этом процедура работает с деревом сверху вниз, Б‑деревья такого типа иногда называются нисходящими Б‑деревьями (top‑down B‑trees).
При этом разбиение блоков происходит чаще, чем это абсолютно необходимо. В нисходящем Б‑дереве полный узел разбивается, даже если в его дочерних узлах достаточно много свободного места. За счет предварительного разбиения узлов, при использовании нисходящего метода в дереве содержится больше пустого пространства, чем в восходящем Б‑дереве. С другой стороны, такой подход уменьшает вероятность возникновения длительной последовательности разбиений блоков.
К сожалению, не существует нисходящей версии для слияния узлов. При продвижении вниз по дереву, процедура удаления узлов не может объединять встречающиеся наполовину пустые узлы, потому что в этот момент еще неизвестно, нужно ли будет объединить два дочерних узла и удалить элемент из их родителя. Так как неизвестно также, будет ли удален элемент из родительского узла, то нельзя заранее сказать, потребуется ли слияние родителя с одним из узлов, находящимся на том же уровне.
==========176
Б+деревья
Б+деревья часто используются для хранения больших записей. Типичное Б‑дерево может содержать записи о сотрудниках, каждая из которых может занимать несколько килобайт памяти. Записи могли бы располагаться в Б‑дереве в соответствии с ключевым полем, например фамилией сотрудника или его идентификационным номером.
В этом случае упорядочение элементов может быть достаточно медленным. Чтобы слить два блока, программе может понадобиться переместить множество записей, каждая из которых может быть достаточно большой. Аналогично, для разбиения блока может потребоваться переместить множество записей большого объема.
Чтобы избежать перемещения больших блоков данных, программа может записывать во внутренних узлах Б‑дерева только ключи. При этом узлы также содержат ссылки на сами записи данных, которые записаны в другом месте. Теперь, если программе требуется переупорядочить блоки, то нужно переместить только ключи и указатели, а не сами записи. Этот тип Б‑дерева называется Б+деревом (B+tree).
То, что элементы в Б+дереве достаточно малы, также позволяет программе хранить больше ключей в каждом узле. При том же размере узла, программа может увеличить порядок дерева и сделать его более коротким.
Например, предположим, что имеется Б‑дерево 2 порядка, то есть каждый узел имеет от трех до пяти дочерних узлов. Такое дерево, содержащее миллион записей, должно было бы иметь высоту между log5(1.000.000) и log3(1.000.000), или между 9 и 13. Чтобы найти элемент в таком дереве, программа должна выполнить от 9 до 13 обращений к диску.
Теперь допустим, что те же миллион записей находятся в Б+дереве, узлы которого имеют примерно тот же размер в байтах. Поскольку в узлах Б+дерева содержатся только ключи, то в каждом узле дерева может храниться до 20 ключей к записям. В этом случае, каждый узел будет иметь от 11 до 21 дочерних узлов, поэтому высота дерева будет от log21(1.000.000) до log11(1.000.000), или между 5 и 6. Чтобы найти элемент, программе понадобится всего 6 обращений к диску для нахождения его ключа, и еще одно обращение к диску, чтобы считать сам элемент.
В Б+деревьях также просто связать с набором записей множество ключей. В системе, оперирующей записями о сотрудниках, одно Б+дерево может использовать в качестве ключей фамилии, а другое — идентификационные номера социального страхования. Оба дерева будут содержать указатели на записи данных, которые будут находиться за пределами деревьев.
Улучшение производительности Б‑деревьев
В этом разделе описаны два метода улучшения производительности Б‑ и Б+деревьев. Первый метод позволяет перераспределить элементы между узлами одного уровня, чтобы избежать разбиения блоков. Второй позволяет помещать пустые ячейки в дерево, чтобы уменьшить вероятность необходимости разбиения блоков в будущем.
=======177
Балансировка для устранения разбиения блоков
При добавлении элемента к блоку, который уже заполнен, блок разбивается на два. Этого можно избежать, если выполнить балансировку этого узла с одним из узлов на том же уровне. Например, вставка нового элемента Q в Б‑дерево, показанное слева на рис. 7.20 обычно вызывает разбиение блока. Этого можно избежать, выполнив балансировку узла, содержащего J, K, L и N и левого узла на том же уровне, содержащего B и E. При этом получается дерево, показанное на рис. 7.20 справа.
Такая балансировка имеет ряд преимуществ. Во‑первых, при этом блоки используются более эффективно. В них находится меньше пустых ячеек, при этом уменьшится количество расходуемой понапрасну памяти.
Что более важно, если не нужно будет разбиение блоков, то не понадобится и перемещение элемента в родительский узел. Это предотвращает возникновение длительной последовательности разбиений блоков.
С другой стороны, уменьшение числа неиспользуемых элементов в дереве увеличивает вероятность необходимости разбиения блоков в будущем. Так как в дереве остается меньше свободных ячеек, то более вероятно, что узел окажется уже полон, когда понадобится вставить новый элемент.
Добавление свободного пространства
Предположим, что имеется небольшая база данных клиентов, содержащая 10 записей. Можно загружать записи в Б‑дерево так, чтобы они заполняли каждый блок целиком, как показано на рис. 7.21. При этом дерево содержит мало свободного пространства, и вставка нового элемента сразу же приводит к разбиению блоков. Фактически, так как все блоки заполнены, она вызовет последовательность разбиения блоков, которая дойдет до корневого узла.
Вместо плотного заполнения дерева, можно добавлять к каждому узлу некоторое количество пустых ячеек, как показано на рис. 7.22. Хотя при этом дерево будет несколько больше, в него можно будет добавлять элементы, не вызывая сразу же последовательность разбиений блоков. После работы с деревом в течение некоторого времени, количество свободного пространства может уменьшиться до такой степени, при которой разбиения блоков могут возникнуть. Тогда можно перестроить дерево, добавив больше свободного пространства.
В реальных приложениях Б‑деревья обычно имеют намного больший порядок, чем деревья, приведенные здесь. Добавление свободного пространства в дерево значительно уменьшает необходимость балансировки и разбиения блоков. Например, можно добавить в Б‑дерево 10 порядка 10 процентов свободного пространства, чтобы в каждом узле было место еще для двух элементов. С таким деревом можно будет работать достаточно долго, прежде чем возникнут длинные цепочки разбиений блоков.
Это очередной пример пространственно‑временного компромисса. Добавка в узлы пустого пространства увеличивает размер дерева, но уменьшает вероятность разбиения блоков.
@Рис. 7.20. Балансировка для устранения разбиения блоков
=======178
@Рис. 7.21. Плотное заполнение Б‑дерева
Вопросы, связанные с обращением к диску
Б‑ и Б+деревья хорошо подходят для создания больших приложений баз данных. Типичное Б+дерево может содержать сотни, тысячи и даже миллионы записей. В этом случае в любой момент времени в памяти будет находиться только небольшая часть дерева и при каждом обращении к узлу, программе понадобится загрузить его с диска. В этом разделе описаны три момента, учитывать которые особенно важно, если данные находятся на диске: применение псевдоуказателей, выбор размера блоков, и кэширование корневого узла.
Псевдоуказатели
Коллекции и ссылки на объекты удобны для построения деревьев в памяти, но они могут быть бесполезны при хранении дерева на диске. Нельзя создать ссылку на запись в файле.
Вместо этого можно использовать методы работы с псевдоуказателями, похожие на те, которые были описаны во 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
Кэширование узлов
Каждый поиск в Б‑дереве начинается с корневого узла. Можно ускорить поиск, если корневой узел будет все время находиться в памяти. Тогда во время поиска придется на один раз меньше обращаться к диску. При этом все равно необходимо записывать корневой узел на диск при каждом его изменении, иначе при повторной загрузке после отказа программы изменения в Б‑дереве будут потеряны.
Можно также кэшировать в памяти и другие узлы Б‑дерева. Если хранить в памяти все дочерние узлы корня, то их также не потребуется считывать с диска. Для Б‑дерева порядка K, корневой узел будет иметь от 1 до 2 * K ключей и поэтому у него будет от 2 до 2 * K + 1 дочерних узлов. Это значит, что в этом случае придется кэшировать до 2 * K + 1 узлов.
Программа также может кэшировать узлы при обходе Б‑дерева. Например, при прямом обходе программа обращается к каждому узлу и затем рекурсивно обходит все его дочерние узлы. При этом она вначале спускается к первому дочернему узлу, а после возврата переходит к следующему. При каждом возврате, программа должна снова обратиться к родительскому узлу, чтобы определить, к какому из дочерних узлов обращаться в следующую очередь. Кэшируя родительский узел в памяти, программа избегает необходимости снова считывать его с диска.
Применение рекурсии позволяет программе автоматически сохранять узлы в памяти без использования сложной схемы кэширования. При каждом вызове рекурсивного алгоритма обхода, определяется локальная переменная, в которой находится узел до тех пор, пока он не понадобится. При возврате из рекурсивного вызова Visual Basic автоматически освобождает эту переменную. Следующий код демонстрирует, как можно реализовать этот алгоритм обхода на языке Visual Basic.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48
