Читайте также:
|
Отсортированный файл данных с первичным индексом называется индексированным последовательным файлом, или индексно-последовательным файлом. Эта структура является компромиссом между файлами с полностью последовательной и полностью произвольной организацией. В таком файле записи могут обрабатываться как последовательно, так и выборочно, с произвольным доступом, осуществляемым на основу поиска по заданному значению ключа с использованием индекса. Индексированный последовательный файл имеет более универсальную структуру, которая обычно включает следующие компоненты:
Обычно большая часть первичного индекса может храниться в оперативной памяти, что позволяет обрабатывать его намного быстрее. Для ускорения поиска могут применяться специальные методы доступа, например метод бинарного поиска. Основным недостатком использования первичного индекса (как и при работе с любым другим отсортированным файлом) является необходимость соблюдения последовательности сортировки при вставке и удалении записей. Эти проблемы усложняются тем, что требуется поддерживать порядок сортировки как в файле данных, так и в индексном файле. В подобном случае может использоваться метод, заключающийся в применении области переполнения и цепочки связанных указателей, аналогично методу, используемому для разрешения конфликтов в хэшированных файлах.
15) Организация индексов в виде B-деревьев
Калькированный термин «В-дерево», в котором смешивается английский символ «В» и добавочное слово на русском языке, настолько устоялся в литературе, посвященной организации физического хранения данных, что я не решусь его корректировать.
Встретив как-то термин «B-дерево», я долго его трактовала, потому что привыкла уже к устоявшемуся обозначению. Поэтому будем работать с этим термином.
Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может быть рассмотрена нами как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.
Мы в общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanced) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин «сбалансированное» от английского «balanced» — «сбалансированный, взвешенный» и дал название данному методу организации индекса.
Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску.
На первом уровне число блоков равно числу блоков основной области, это нам известно, — оно равно 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс.
Мы не будем менять длину индексной записи, а будем считать ее прежней, равной 14 байтам. Количество индексных записей в одном блоке нам тоже известно, и оно равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока.
КIВ3 = KIB2/KZIB = 172/73 = 3 блока
Мы снова округляем в большую сторону, потому что последний, третий, блок будет заполнен не полностью.
И над третьим уровнем строим новый, и на нем будет всего один блок, в котором будет всего три записи. Поэтому число уровней в построенном дереве равно четырем, и соответственно количество обращений к диску для доступа к произвольной записи равно четырем (рис. 9.9). Это не максимально возможное число обращений, а всегда одно и то же, одинаковое для доступа к любой записи.
16) Физическая организация данных. Доступ к базе данных. Страничная организация данных в СУБД.
Под физической организацией БД понимается совокупность методов и средств размещения данных во внешней памяти и созданная на их основе внутренняя (физическая) модель данных. Внутренняя модель является средством отображения логической модели данных в физическую среду хранения. В отличие от логических моделей физическая модель данных связана со способами организации данных на носителях, методами доступа к данным. Она указывает, каким образом записи размещаются в базе данных, как они упорядочиваются, как организуются связи, каким путем можно локализовать записи и осуществить их выборку.
Внутренняя модель разрабатывается средствами СУБД.
Очевидно, что любая логическая модель может быть отображена множеством внутренних моделей данных подобно тому, как один и тот же алгоритм может быть представлен множеством эквивалентных программ, составленных на одном или разных языках программирования. Одна из внутренних моделей будет оптимальной. В качестве критериев оптимальности используются минимальное время ответа системы, минимальный объем памяти, минимальные затраты на ведение баз данных и др.
Страничная организация данных в СУБД
Каждая БД состоит из одного или нес-ких ф-ов. Любая обл. памяти разбив на страниц. В начале стр. размещ служ-ая инф которая наз-ся заголовком страницы. Данная инф исп СУБД для упр-я стр-ей. На стр обычно распол-ся неск-ко записей и ост-ся своб-е пр-во к-ое исп-ся для добавл записи. К-ая запись сост из 2-ух частей. Из служ-ой и инф-ой. Служ-я часть исп-ся для идентификации зап-си, опр-ия ее типа и хранения признака удаления зап-и. Идент-ия зап осущ-ся ч/з ключ БД к-ый предст собой номер стр-ы и байт опр-ий смещение зап от конца стр. Поэтому КБД нельзя отожд-ть с первич ключом к-ый задайтся пол-лем Инф часть записи содерж дан. Сущ-ет 2-а спос-а размещ Д в зап.
1) Размещ в зар-ие зад-ой позиц.
1| Иванов И.И. ……..21|зав. каф-ой……41|год рожд…….|44
Можно подсчит V-м памяти 44*3 зап.=132
2) Размещ Д с разделителем. После записи одного эл-та Д ст-ся разд-ль и сразу зап-ся нов эл-т Д. В этом случ память исп-ся более рац-но, но треб доп время для расшиф-ки.
17) Физическая организация данных(см 16 и телефон). Файловые структуры баз данных
Дата добавления: 2015-02-16; просмотров: 173 | Поможем написать вашу работу | Нарушение авторских прав |