В-деревей
Cтраница 2
В СУБД, использующих двухуровневую память, вся оптимизация обработки данных исходит из того, что данные в подавляющем большинстве случаев находятся на диске. Поэтому применяются индексные структуры для доступа к данным на основе В-деревьев и специальный буферный пул, отслеживающий размещение данных. При этом учитывается управление памятью со стороны операционной системы, в частности, взаимодействие с механизмом управления замещением страниц виртуальной памяти. Эти СУБД, даже будучи сконфигурированными так, чтобы все данные размещались в оперативной памяти, остаются неэффективными в силу используемых индексных структур и алгоритмов оптимизации запросов, а также организации управления буферным пулом. [16]
В-дерево имеет более сложную структуру, чем бинарное дерево поиска. Известно несколько разновидностей этой структуры, что расширяет диапазон практического применения В-деревьев. [17]
Хотя рассмотренные фундаментальные алгоритмы обладают большими возможностями, разработка реализации файловой системы, основанной на использовании В-деревьев или расширяемого хеширования представляет собой сложную задачу. Во-первых, приведенные в этом разделе программы на C нельзя использовать непосредственно - они должны быть модифицированы для считывания и ссылки на дисковые файлы. Во-вторых, необходимо быть уверенным, что параметры алгоритма ( например, размеры страницы и каталога) подобраны в соответствии с характеристиками конкретного используемого аппаратного обеспечения. В-третьих, следует уделить внимание надежности и выявлению и исправлению ошибок. Например, необходимо иметь возможность убедиться в целостности структуры данных и принять решение о том, как исправлять любые из возможных ошибок. Подобные системные факторы являются критичными и выходят за рамки этой книги. [18]
Для операций включения и удаления над В-деревом можно было бы использовать ту же стратегию, что и в предыдущем разделе, применяя операции включения и удаления к узлам ( блокам) дерева на всех уровнях. Тогда узлы содержали бы от одной записи до максимально возможного их числа. Для В-деревьев обычно применяется, однако, иная стратегия включения и удаления, которая обеспечивает заполненность всех узлов ( за исключением, возможно, корня) не менее чем наполовину. [19]
Расширяемое хеширование объединяет свойства методов хеширования, использования многопозиционных trie - деревьев и последовательного доступа. Для простоты в этом разделе мы будем просто считать, что ключи являются случайными строками разрядов фиксированной длины. Подобно алгоритмам с применением В-деревьев, при использовании расширяемого хеширования элементы хранятся на страницах, которые разделяются на две части при заполнении. Подобно методам индексного последовательного доступа расширяемое хеширование поддерживает каталог, указывающий, где можно найти страницу, содержащую соответствующие искомому ключу элементы. Поскольку оно объединяет эти знакомые свойства в одном алгоритме, расширяемое хеширование как нельзя более подходит для завершения знакомства с алгоритмами поиска. [20]
Такой индекс может сам занимать несколько страниц области, где он хранится, и возникает задача минимизации числа доступов для чтения страниц индекса при поиске нужной хранимой записи. Эта задача решается с помощью многоуровневых индексов иерархической структуры. Весьма эффективной при этом является широко распространенная в последние годы организация многоуровневых индексов в виде сбалансированных деревьев ( В-деревьев), т.е. таких деревьев, в которых все пути от корня к листьям имеют одинаковую длину. Техника В-деревьев используется во многих СУБД для персональных ЭВМ. [21]
Если в результате этой вставки в узле оказывается Л / элементов, мы вызываем функцию разделения, как это делалось для В-деревьев, правда, на этот раз она сложнее. Каждая страница содержит k ведущих разрядов, которые заведомо совпадают в ключах всех элементов на данной странице, и, поскольку разряды нумеруются слева направо, начиная с 0, k определяет также индекс разряда, который необходимо проверять для определения способа разделения элементов. [22]
Решение многих важных проблем требует использования больших баз данных ( БД) в реальном времени. Для выполнения заранее известного набора запросов могут быть применены предварительно организованные специальным образом данные. Для подготовки этих данных могут быть использованы средства создания адекватного запросам набора отношений базы данных, индексирования ключевых атрибутов на основе, например, хэширования или Т -, В-деревьев, предварительной сортировки, и тому подобные приемы, сокращающие время выполнения заранее известных запросов. Однако в случае порождения запросов на основе результатов уже выполненных запросов, что имеет место в современных системах поддержки принятия решений, требуется работа с не организованными специальным образом данными. В этом случае только параллельное выполнение запросов может дать результат в приемлемое время. [23]
Такой индекс может сам занимать несколько страниц области, где он хранится, и возникает задача минимизации числа доступов для чтения страниц индекса при поиске нужной хранимой записи. Эта задача решается с помощью многоуровневых индексов иерархической структуры. Весьма эффективной при этом является широко распространенная в последние годы организация многоуровневых индексов в виде сбалансированных деревьев ( В-деревьев), т.е. таких деревьев, в которых все пути от корня к листьям имеют одинаковую длину. Техника В-деревьев используется во многих СУБД для персональных ЭВМ. [24]
 |
Карты распределения для дисков типа DK. [25] |
СкаВае ВЗУ именем представляются в виде узлов дерева и образуют глобальный массив. Количество индексов соответствует уровню узла в дереве, индексы на одном уровне идентифицируют различные узлы. Узлы дерева, включая корень, могут содержать как данные, так и указатели на нижний уровень. Концевые узлы ( листья) содержат только данные. Физическая структура глобальных данных имеет вид сбалансированных В-деревьев. При этом данные независимо от количества индексов глобальной структуры хранятся только на нижнем уровне соответствующей физической структуры. [26]
Страницы: 1 2