1.2 Системы управления базами данных. Основные функции. Базой данных (БД) будем называть совокупность данных, которая предназначена для компьютеризированной обработки. Для обработки данных, хранимых в базе данных, необходимо использовать специализированное программное обеспечение, называемое системой управления базами данных (СУБД). Поскольку все СУБД предназначены для решения сходных задач, то можно выделить ряд общих функций, которые в том или ином виде должны быть реализованы в любой системе. К таким функциям можно отнести, в частности, следующие: ^ 1.Обеспечение доступа к данным. Доступ к данным подразумевает возможность выполнения по крайней мере следующих операций: добавление новых данных, модификация или удаление существующих данных, поиск данных по различным критериям. При этом СУБД может управлять выделением и освобождением памяти на внешних носителях для соответствующих структур данных, поддерживать дополнительные (избыточные) структуры для ускорения поиска, выбирать наиболее эффективные пути доступа к данным. ^ 2.Обеспечение изменения структуры данных. При проектировании БД должны быть предусмотрены структуры для всех видов данных, которые планируется обрабатывать. На практике бывает достаточно сложно предусмотреть все будущие потребности в данных, и поэтому первоначальный проект может потребовать доработки уже при использовании БД. СУБД должна поддерживать внесение изменений в существующие структуры БД, при этом желательно, чтобы программы, которые не затрагиваются этими изменениями, сохраняли свою работоспособность. ^ 3.Защита целостности данных. Из содержательной интерпретации данных могут быть выявлены некоторого рода ограничения на возможное содержание БД. СУБД может проверять эти ограничения, не допуская тем самым случайного (или намеренного) нарушения целостности информации. Рассмотрим в качестве примера БД сотрудников, используемую отделом кадров. В такой БД может хранится дата рождения каждого сотрудника, которая используется при вычислении его возраста (как разницы между текущей датой и датой рождения). Поскольку отдел кадров имеет дело только с действующими сотрудниками, то, очевидно, в БД не может быть сотрудников, возраст которых выходит за пределы, определенные законодательством. Иными словами, не каждая дата может использоваться в качестве даты рождения. Поскольку все изменения в БД выполняются СУБД, она может запрещать изменения персональных данных, которые нарушают данное правило. Другим примером может служить информация о принадлежности сотрудника некоторому отделу. Если регламентом предприятия не предусмотрено совмещение одним человеком должностей в различных отделах, то СУБД может блокировать любые изменения, которые могут привести к появлению одного и того же сотрудника в различных отделах. ^ 4.Обеспечение секретности. Обычно БД используется как централизованное хранилище информации, используемое различными пользователями для различных целей. При этом может оказаться нежелательным, если пользователь имеет доступ ко всем хранимым данным. Пользователю могут быть предоставлены права лишь на часть БД или на выполнение только определенного вида операций (например, только чтение данных, чтение и модификация данных, модификация структуры БД и т.д.). ^ 5.Синхронизация доступа. СУБД должна выполнять некоторые действия по упорядочению совместного доступа к данным различных независимых пользователей. При этом основной целью является получение таких же результатов, какие были бы получены при последовательной (т.е. неперекрывающейся по времени) работе пользователей1. Для этого СУБД использует блокировки - предотвращение одновременного доступа к различным частям БД. ^ 6.Защита от отказов и восстановление. После того, как предприятие начало хранить свои данные в БД, оно стало критически зависеть от успешного функционирования системы. В случае повреждения какой-либо части БД вследствие ошибки человека, отказа оборудования или сбоя в программном обеспечении необходимо иметь возможность восстановить данные с минимальными последствиями для деятельности предприятия. Современные СУБД содержат программное обеспечение для создания резервных копий всей БД или ее частей (в частности, непосредственно во время работы пользователей), восстановления содержимого БД из резервных копий, распределения БД по нескольким носителям (которые могут располагаться на различных вычислительных системах) с возможностью ``горячего'' восстановления. ^ 1.3 Архитектура СУБД Необходимость совместного использования БД накладывает отпечаток на архитектуру программного и аппаратного обеспечения СУБД. По крайней мере, для того, чтобы упорядочивать доступ к данным (управлять блокировками) необходимо иметь общий для всех пользователей программный компонент, через который будут проходить все взаимодействия с БД. Под пользователем здесь понимается не столько человек, сколько процесс, который может обращаться к БД. Поскольку человек всегда использует некоторую программную оболочку для доступа к данным, то нас будет интересовать взаимодействие этой оболочки с СУБД, а не операторская работа человека. Могут существовать недиалоговые процессы (процессы, не требующие вмешательства человека), взаимодействующие с БД. Такие процессы мы также будем рассматривать как пользователей БД. Таким образом, программное обеспечение СУБД распадается на две части: программное обеспечение каждого отдельного пользователя, называемое клиентским программным обеспечением, и программное обеспечение общее для всех пользователей, называемое серверным программным обеспечением. В общем случае клиентское программное обеспечение и серверное программное обеспечение могут быть установлены на различных вычислительных системах, которые взаимодействуют в сетевой среде. В любом случае будем говорить о сервере БД, имея в виду вычислительную систему, где установлено серверное программное обеспечение СУБД, и - о клиенте БД, имея в виду, вычислительную систему, где установлено клиентское программное обеспечение. При этом нужно помнить, что в принципе клиент и сервер могут располагаться на одной и той же вычислительной системе. Программно-аппаратная архитектура, состоящая из единственного сервера БД и одного или нескольких клиентов, называется архитектурой клиент-сервер. Взаимодействие пользователя с БД обычно носит периодический характер. Пользователь время от времени обращается к СУБД с запросами, а остальное время (по крайней мере, с точки зрения СУБД) находится в пассивном состоянии. В это время сервер может заниматься обслуживанием запросов других пользователей. В тех случаях, когда интенсивность обращений пользователей относительно невысока, сервер может одновременно эффективно обслуживать достаточно большое количество пользователей. Производительность системы можно повышать, повышая производительность только сервера БД, например, выделяя для него более мощную машину. Это может оказаться дешевле и проще, чем модернизировать весь парк пользовательских машин (что иногда в принципе невозможно для удаленных систем). Сервер БД и пользователи могут работать на различных программных и аппаратных платформах. Например, довольно часто используется архитектура с сервером БД на базе UNIX-машины, а рабочие станции используют ОС с хорошими графическими средствами отображения информации (например, Windows, Mac-OS). Так или иначе, на этапе проектирования часто бывает невозможно определить каким образом будет использоваться БД в будущем. Поэтому принципиальная возможность подключения к ней любых пользователей может оказаться весьма полезной.^ 1.4 Уровни абстракции данных С точки зрения пользователя СУБД представляет набор примитивных операций, которые можно выполнять над БД. С другой стороны СУБД использует примитивы ОС для организации хранения данных и доступа к ним на уровне аппаратуры. Операции СУБД являются более абстрактными чем операции ОС в том смысле, что данные, с которыми они имеют дело представляют собой логические (абстрактные) конструкции, неизвестные на уровне операционной системы3, и моделируемые программными средствами СУБД. Задача СУБД (наряду с прочими) предоставить пользователю набор операций, которые бы как можно более естественно подходили бы для решения его задач, избавляя его при этом от несущественных технических деталей. Например, отдел кадров, используя свою БД данных, будет иметь дело с сотрудниками, каждый из которых характеризуется некоторым набором данных, отделами и т.д. На уровне ОС эта информация будет организована как совокупность файлов, имеющих определенную структуру. Получение информации о каком-либо сотруднике может потребовать нескольких операций доступа к файлам на уровне ОС. Достаточно стандартный подход к уровням абстракции данных показан на рис. Физическая БД находится на самом нижнем уровне абстракции. Она размещается на устройствах внешней памяти, например, на магнитных дисках. Концептуальная БД содержит данные в том виде как они представляются обобщенному пользователю. Именно концептуальная БД имеет отношение к предметной области. Представления являются абстракциями концептуальной БД, которые подходят для использования конкретным пользователем. Представление выделяет из общей концептуальной БД ту часть информации, которая существенна для пользователя, отбрасывая остальное. При этом представление может быть более абстрактным чем концептуальная БД. Здесь можно повторить уже приводившийся пример с возрастом сотрудника. Вполне естественно, если концептуальная БД будет содержать дату рождения сотрудника. Тогда, если некоторый пользователь нуждается в получении возраста, то соответствующее представление будет вычислять возраст исходя из текущей даты. Другой вариант абстракции, который может использоваться в представлениях, состоит в построении различных ассоциаций между данными. Например, в БД по продаже билетов авиарейсы могут рассматриваться как множества пассажиров, с другой стороны служба продажи билетов может рассматривать каждого пассажира как множество рейсов, на которые он купил билеты. Многие языки программирования требуют описания переменных перед их использованием в программе. Аналогично, перед тем как вносить, модифицировать или выбирать данные, необходимо описать, какие в виды данных в принципе могут находится БД и какие между ними могут существовать связи. Такое описание называется схемой БД. Физическая схема БД описывает особенности хранения данных на устройствах внешней памяти, например, распределение данных по файлам, необходимые индексные структуры для ускорения поиска и т.д. Концептуальная схема БД описывает прикладные виды данных и взаимосвязи между ними (например, именно в концептуальной схеме будет указано, какие данные о сотрудниках необходимо хранить и как эти сотрудники могут быть связаны с отделами). Аналогично, можно говорить о схеме представления как об абстракции некоторой части концептуальной схемы для определенного пользователя. Если схема базы данных (концептуальная или физическая) изменяется относительно редко, то собственно хранимые данные могут меняться достаточно часто. Любое изменение данных о некотором сотруднике изменяет содержимое БД. Рассматривая содержимое БД в какой-то определенный момент времени, будем говорить об экземпляре БД. Поскольку содержимое БД меняется, то может быть много экземпляров БД с одной и той же схемой. Цепочка абстракций на рис. обеспечивает два уровня независимости данных. Изменения в физической схеме могут не затрагивать концептуальную схему (а значит схемы представлений), а значит не повлияют на программы, которые используют данные. Однако такие изменения могут повлиять на эффективность работы этих программ. Такого рода независимость называется физической независимостью данных. По мере использования БД может потребоваться модификация концептуальной схемы, например, для добавления новых видов данных. При этом в некоторых случаях такие изменения не будут затрагивать схемы представлений, а значит - работающие с представлениями программы. Такая независимость называется логической независимостью данных. ^ 2.1 Организация внешней памяти Наиболее распространенным видом внешней памяти, которая используется для размещения БД, в настоящее время является магнитный диск. С точки зрения файловой системы диск обычно представляется в виде последовательности секторов фиксированного размера (например, 4К или 8К), каждый из которых имеет уникальный адрес. Аппаратно могут выполняться операции чтения или записи сектора. Иными словами, сектор - это наименьшая аппаратно адресуемая область дисковой памяти. Дисковая память является памятью произвольного (прямого) доступа в том смысле, что ОС может осуществлять доступ к секторам в произвольном порядке. Т.е. в любой момент времени ОС может читать или записывать любой сектор диска примерно с одинаковой скоростью. Другой распространенный вид внешней памяти - это память на магнитных лентах - обычно используется для хранения архивных копий БД. Это связано прежде всего с тем, что в отличие от диска лента не является устройством произвольного доступа. Чтобы произвести чтение некоторого блока на ленте может, вообще говоря, потребоваться трудоемкая операция перемотки ленты. Иными словами, время доступа к различным участкам такой памяти существенно зависит от адреса участка. Наиболее эффективно доступ к ленте происходит последовательно, по порядку следования блоков. Поэтому ленточное устройство называется устройством с последовательным доступом. Обычно ОС (а точнее, ее компонент - файловая система) организует доступ к внешней памяти, используя понятие файла. На самом абстрактном и неструктурированном уровне будем рассматривать файл как упорядоченную совокупность элементов с символическим именем. Элемент файла - его наименьшая адресуемая единица - вообще говоря не обязательно (и скорее зачастую) совпадает с наименьшей адресуемой единицей устройства внешней памяти. Файловая система организует преобразование адресного пространства файла в адресное пространство внешней памяти. Таким образом можно говорить о виртуальной файловой памяти. Цель концепции файловой виртуальной памяти - обеспечение пользователей простым единообразным линейным пространством для размещения данных (рис. 3). Это пространство может быть далее структурировано (как структурирована память ЭВМ) любым удобным способом, чтобы отразить истинную организацию данных и их обработку. В СУБД элементы файла обычно называют записями. С концептуальной точки зрения запись - это просто упорядоченный список значений. С физической, - запись - это непрерывный участок виртуальной файловой памяти, отведенный для хранения этих значений. Участок внутри записи, где храниться конкретное значение, называется полем этой записи. Тип записи - это описание, которое указывает, какие значения могут входить в запись, порядок их появления в записи и тип данных каждого значения. Тип записи аналогичен понятию структуры, которое встречается во многих языках программирования, а запись - переменной с данным структурным типом. Если все записи файла имеют одинаковый размер (занимают одинаковое количество памяти), то говорят о файле с фиксированной длиной записи. Предположим, что БД сотрудников должна содержать для каждого сотрудника его имя, отчество, фамилию и дату рождения. Причем известно (из общих соображений), что фамилия не может содержать более 60 символов, имя и отчество - более 25, а дата занимает 4 байта (например юлианский день5). Тогда любая запись о сотруднике будет занимать не более 114 байтов (предположим, что символ занимает 1 байт). При организации БД сотрудников в виде файла с фиксированной длиной записи для каждого сотрудника будет отведено ровно 114 байтов, поэтому некоторые записи, например, (``Иван'', ``Иванович'', ``Иванов'', 2440431), будут оставлять неиспользованной некоторую часть памяти (в данном примере 92 байта). Несмотря на то, что файлы с фиксированной длиной записи потенциально могут использовать лишнюю память, такая организация довольно часто используется, поскольку она допускает простую и эффективную реализацию. Действительно, в данном случае адрес каждой записи может быть представлен парой , где - номер виртуального блока файла, а - номер записи в блоке. Поскольку каждый блок имеет фиксированное количество записей (может быть за исключением последнего блока), то возможна реализация, в которой записи имеют сплошную нумерацию (и соответственно должны последовательно располагаться в файле). При этом адрес может быть получен следующим образом: , , где - максимальное количество записей в блоке, а - порядковый номер записи начиная с нуля. Фиксированная длина записи упрощает процедуру модификации записи, т.к. количество памяти отводимое для записи не зависит от значений полей. Если длины записей могут быть разными, говорят о файле с переменной длиной записи. Записи переменной длины появляются тогда, когда размер памяти, отводимый для записи зависит от значений ее полей. Например, длина записи в БД сотрудников вообще говоря зависит от содержимого полей имя, отчество, фамилия. Если в файле фиксированной длины для каждой записи резервировалось пространство с запасом, то в файле с записями переменной длины пытаются выделять только необходимую память (в приведенном примере информация может поместиться в 22 байта). Однако при таком подходе существенно усложняется реализация, поскольку положение записи в файле уже не может быть определено на простой регулярной основе. Более того, изменение значения поля записи может потребовать изменения размера отведенной памяти, при этом может потребоваться перемещение записи или будут образовываться неиспользованные участки. Реализации файлов с фиксированной и переменной длинами записей проиллюстрированы на рис. 4. Рассмотренная последовательная организация файла обладает рядом недостатков, которые ограничивают ее применимость в практических случаях. Самым существенным недостатком, пожалуй, является необходимость перемещения записей при добавлении или удалении. Это приводит к существенным накладным расходам, при этом происходит изменение адресов записей, таким образом существующие ссылки на них могут быть нарушены. Распространенной стратегией распределения памяти под записи, лишенной такого рода недостатков, является куча. Простой способ организации файла в виде кучи для записей фиксированной длины показан на рис. 5. Пространство файла распределено на два списка: список свободного пространства и список использованного пространства, указатели на которые могут храниться в заголовке файла. Основные операции с файлом могут выполняться следующим образом: ^ Добавление записи. Если при добавлении список свободного пространства не пуст, то для размещения новой записи можно взять первый элемент этого списка, после чего указатель на начало списка свободного пространства перемещается к следующему элементу7. Если список свободного пространства пуст, то выделяется новый блок, разбивается на записи, которые добавляются в список свободного пространства. Затем память выделяется из непустого списка свободного пространства. Добавленная запись добавляется к списку использованного пространства. Вообще говоря, запись может быть добавлена в любое место этого списка. Для этого при добавлении помимо значений полей должна быть известна запись (ее адрес), после которой будет добавлена новая запись. ^ Удаление записи. Эта операция состоит в переносе удаляемой записи из списка использованного пространства в список свободного8. Эта операция может быть эффективно реализована только, если список использованного пространства является двунаправленным (в противном случае потребовался бы поиск предыдущей записи). ^ Модификация записи. В случае фиксированной длины записи значения просто заносятся в соответствующие поля записи. Если запись переменной длины, то может потребоваться переразмещение памяти, и, возможно, перемещение записи в другой блок. С концептуальной точки зрения такое действие проще рассматривать как удаление с последующим добавлением. Такая реорганизация может нарушить целостность БД, если для доступа к записям могут использоваться предварительно сохраненные адреса. ^ Перемещение по записям. Список использованного пространства используется для просмотра всех записей в файле (например, при поиске). При этом возможны следующий действия: получить первую запись файла, получить последнюю запись файла, получить запись, следующую за данной, получить запись, предшествующую данной (имеет ввиду не физический порядок записей, а логический порядок их следования в списке). 3.1 Индексы Использование БД прежде всего подразумевает возможность поиска в ней необходимой информации. Различные подходы к поиску опираются на те элементарные операции, которые заложены в физическую структуру соответствующих файлов. На рис. 5 приведена организация файла, в которой на элементарном уровне могут быть реализованы следующие операции поиска: Найти запись по ее адресу, Найти запись, следующую за данной, Найти запись, предшествующую данной, Найти первую запись файла, Найти последнюю запись файла. Эти операции основаны на информации о абсолютном или относительном положении записей, которая храниться в рамках физической организации файла и не имеет никакого отношения к содержимому записей. Однако практический интерес представляет прежде всего поиск на основе содержимого полей записи, т.н. ассоциативный поиск. Например, поиск в файле сотрудников скорее всего должен осуществляться на основе фамилии, имени и отчества сотрудника. Именно по этой информации может потребоваться найти остальные данные такие как возраст, место работы, и т.п. При использовании только базового набора операций для организации такого поиска может потребоваться последовательный просмотр в среднем половины записей, а в худшем случае всего файла. Для эффективной реализации ассоциативного поиска используются специальные структуры данных, которые называются индексами. Общую идею индекса можно продемонстрировать на примере предметного указателя в конце книги. Предметный указатель представляет собой список терминов в алфавитном порядке с указанием страниц, где каждый термин встречается. Поиск какого-либо термина непосредственно в книге состоит в систематическом пролистывании всей книги (если требуется найти все вхождения этого термина). В указателе термин можно быстро найти используя алфавитный порядок и немедленно определить страницы, где этот термин встречается. Чтобы организовать индекс необходимо решить по значениям каких полей будет осуществляться поиск. Совокупность таких полей иногда называют ключом поиска. Обычно индекс реализуется в виде отдельного файла, каждая запись которого содержит значения ключа поиска и указатель (адрес) на соответствующую запись в основном файле(рис. 6). Индекс организуется так, что зная значения полей можно быстро найти соответствующую запись индекса, а затем, используя указатель на основной файл,- саму запись. Если в разных случаях поиск происходит по различным наборам полей, то для одного основного файла можно иметь несколько разных индексов. Существуют два основных в некотором смысле противоположных подхода к организации индекса: упорядочение и хеширование11. Соответственно можно говорить об упорядоченных индексах и о хешированных индексах. В упорядоченном индексе записи поддерживаются в порядке возрастания или убывания значений ключа. При добавлении, изменении или удалении записей из основного файла СУБД автоматически реорганизует индекс так, чтобы он соответствовал текущему содержимому основного файла. Упорядоченность записей позволяет использовать быстрый двоичный поиск для нахождения записи с заданным ключом. Помимо этого упорядоченный индекс позволяет эффективно отыскивать записи, ключи поиска которых находятся в заданном диапазоне, т.е. отвечать на воросы типа: при заданных значениях k1 и k2 отыскать все записи с ключом k таким, что k1Упорядоченный индекс подразумевает возможность сравнения значений ключа. Если значения ключа являются целыми или вещественными числами, то для них определены общепринятые отношения порядка. Для символьных строк определен словарный, или лексикографический порядок. Пусть a1a2…am и b1b2…bn две символьные строки, где ai и bi - отдельные символы. Тогда, a1a2…am m и ai=bi для i (- [1,m] или существует такое i (- [1,min(m,n)], что ai=bi для всех i (- [1,i-1] и ai. При этом подразумевается обычный алфавитный порядок символов. Значений ключа, состоящего более чем из одного поля, можно сортировать в порядке следования полей. В результате сортировки по первому полю образуются группы записей с одним значением в этом поле. После сортировки каждой группы по значению второго поля, получаются группы с одним и теми же значениями в двух полях. Полученные группы сортируются по третьему полю и т.д. Следует отметить, что такое упорядочение аналогично лексикографическому порядку, где в качестве символов выступают значения полей. В хешированном индексе записи распределяются по специальной таблице на основе преобразованного ключа. Преобразование ключа выполняется некоторой хеш-функцией. Вычислив значение хеш-функции для какого-либо ключа, можно быстро определить место в таблице, где расположена запись. Такие индексы позволяют быстро вычислять положение одиночных записей, но не дают никаких преимуществ при поиске внутри диапазона, поскольку записи не упорядочены. 3.2 B-деревья Очевидно, что физическое упорядочение записей индекса имеет те же недостатки, что и физическое упорядочение самих записей основного файла: необходимость реорганизации файла при операциях вставки, удаления, модификации. Следовательно для организации индекса должен использоваться некоторый вариант кучи. Однако при этом недостаточно иметь простую структуру типа двунаправленного списка, поскольку придется при каждой модификации индекса выполнять сортировку. При этом также следует иметь ввиду, что количество записей в индексе может быть очень велико (размеры файла могут во много раз превышать доступную оперативную память), таким образом применение обычных методов сортировки, которые ориентируются на размещение всех сортируемых элементов в ОП, может быть невозможно. В ОП упорядоченные структуры, допускающие эффективную вставку, удаление и модификацию данных обычно организуются в виде сбалансированных деревьев (AVL-деревьев12). Сбалансированные деревья - это двоичные деревья, для которых постоянно поддерживается равномерное распределение вершин между поддеревьями. При этом достигается близкая к теоретической (для двоичного поиска) эффективность поиска (порядка log2N шагов, где N- общее количество элементов, среди которых происходит поиск) при приемлемых затратах на балансировку. Однако использование таких структур для организации индексов во внешней памяти оказывается крайне неэффективным из-за больших затрат на ввод вывод. Действительно, поскольку теперь вершины располагаются не в оперативной памяти, а на внешних устройствах, то каждое обращение к вершине (при поиске или в ходе балансировки) требует отдельной операции чтения или записи. Таким образом, если дерево содержит, например 1000000 вершин, то в среднем может потребоваться около 20 операций обращения к внешней памяти. Количество таких обращений будет больше, если происходит балансировка. Естественным подходом к преодолению данной проблемы является группировка нескольких вершин дерева в один блок ввода-вывода. При этом в древовидную структуру организуются блоки, а не отдельные вершины. Несмотря на то, что возникает необходимость производить поиск внутри блока, количество обращений к устройству внешней памяти сокращается. Весьма распространенный в настоящее время подход к организации упорядоченных индексов был предложен в 1970г. Р.Бэйером и Э.Мак-Kрейтом. Предложенные ими структуры получили название Б-деревьев. Б-дерево представляет собой сильно ветвящееся дерево13, обладающее следующими свойствами: Каждая вершина может содержать не более 2n ключей. Каждая вершина за исключением, может быть, корневой содержит не менее n ключей (корневая вершина,если она не является листом, содержит не менее двух потомков). Каждая вершина либо представляет собой лист и не имеет потомков, либо имеет в точности m+1 потомка, где m- количество ключей в вершине. Все листовые вершины располагаются на одном уровне. Число n называется порядком Б-дерева. Пример Б-дерева показан на рис. 7. Каждая нелистовая вершина Б-дерева имеет вид Здесь pi представляет собой указатель на i-го потомка, а ki- значение ключа поиска (указатели на записи основного файла ради простоты не указаны). Для любого i (- [1,m-1] все ключи, расположенные в поддереве, на которое указывает указатель pi , находятся в диапазоне [ki,ki+!]. Соответственно, все ключи поддерева p0 будут меньше k1, а все ключи поддерева pm- больше km. Поиск некоторого ключа в Б-дереве происходит следующим образом. Начиная с корневой вершины выполняется следующая последовательность действий (рис. 7): Просматриваются ключи k1,k2,…,km. Если искомый ключ k найден, то по соответствующему указателю извлекается запись основного файла. Для поиска ключа в вершине может использоваться либо простой последовательный поиск, если невелико, или двоичный поиск, для достаточно больших . Если ki для I (- [1,m], то поиск продолжается на странице pi. Если k, то поиск продолжается на странице p0. Если k>km, то поиск продолжается на странице pm. При вставке ключа сначала происходит поиск соответствующей вершины (очевидно, что это будет листовая вершина). Затем происходит следующее (рис. 7): Если найденная вершина содержит менее 2n ключей, то ключ просто добавляется к данной вершине. Если страница уже заполнена, то она разделяется на две. При этом 2n из 2n+1 ключей пополам (с учетом порядка) распределяются между получившимися вершинами. Центральный ключ (по значению) помещается в родительскую вершину. При этом может произойти ее разделение. Когда происходит разделение корневой вершины, Б-дерево вырастает на один уровень. При удалении из Б-дерева происходит балансировка и слияние страниц. Процедуру удаления можно описать следующим образом (рис. 8): Если удаляемый ключ находится на листовой вершине, то он просто удаляется. Если удаляемый ключ находится на промежуточной вершине, то он заменяется на смежный элемент, который расположен на листовой вершине. Если в результате удаления количество ключей вершины стало меньше , то выполняется балансировка - ключи поровну распределяются между данной, родительской и смежной вершинами. Если количество ключей на смежной вершине равно , то балансировка невозможна, но можно слить данную и смежную вершины, заняв один ключ из родительской. Это может привести в свою очередь к балансировке или слиянию на следующем уровне. Обычно Б-дерево храниться в файле по вершинам - каждая вершина занимает виртуальный блок файла, а значит требует одной операции ввода/вывода. Порядок дерева зависит от размера блока и от размера ключа поиска. Чем больше количество ключей располагается в блоке, тем меньше будет операции ввода/вывода, однако больше операций потребуется для обработки отдельного блока (например при поиске). Уменьшение количества ключей в блоке приводит к увеличению операций ввода/вывода. На практике критическим местом обычно является именно ввод/вывод, соответственно стремятся увеличивать количество ключей в блоке. Это тем более важно, потому, что доступ к блокам происходит в порядке близком к случайному. Правосторонний или левосторонний обходы дерева позволяют получать записи в порядке убывания или возрастания ключей. Очевидно, что в данном случае достаточно просто организуется поиск внутри диапазона. ^ 4.1 Хешированные индексы Идея хеширования состоит в следующем. Все множество записей разбивается на группы таким образом, что бы по ключу поиска можно было бы быстро вычислить группу в которой находится запись, а затем, просмотрев группу найти саму запись. Если время вычисления группы фиксированно и не зависит от количества записей, то время поиска будет определятся количеством записей в группе. Таким образом чем меньше размер группы тем быстрее поиск. В качестве примера такого разбиения можно привести группировку сотрудников по первой букве фамилии. К первой группе будут относится сотрудники, с фамилией, начинающейса с буквы ``А'', ко второй - с фамилией, начинающейся с буквы ``Б'' и т.д. Каждую группу можно представить списком слов, которые начинаются с соотвествующей буквы. Все группы могут быть организованы в массив, содержащий 33 элемента, так, что по номеру группы в этом массиве можно определить указатель на начало соотвествующего списка. Если задана некоторая фамилия, то зная порядковый номер ее первой буквы в алфавите можно быстро определить группу фамилий. Затем последовательно просматривая эту группу найти нужную запись. Однако такое простое правило определения группы обладает существенным недостатком. В русском языке фамилии распределены по буквам алфавита весьма неравномерно. Поэтому группы при таком распределении будут сильно отличаться по количеству фамилий (например, группа, начинающаяся на букву ``А'', будет содержать, скорее всего больше фамилий, чем группа, начинающаяся на букву ``Э'', тогда как группа для буквы ``Ы'' вероятнее всего будет пустой). Следовательно возникает крайне не желательная ситуация, когда поиск наиболее часто встречающихся фамилий будет требовать больше времени, чем поиск редких. Таким образом необходимо правило распределения, которое более равномерно распределяло бы фамилии по группам. Правило, которое позволяет вычислить группу (точнее адрес группы записей - в нашем примере это индекс в массиве указателей на начало списков фамилий) записей по значению ключа, называется хэш-функцией, а сама процедура распределения - хешированием. Существуют различные способы вычисления хеш-функций. В качестве примера можно привести стратегию, которая оказывается подходящей во многих случаях14: Значение ключа рассматривается как последовательность битов. Если ключ состоит из нескольких полей, то все они могут быть объеденены в одну последовательность битов. Последовательность битов делиться на группы, равные (или кратные) машинному слову. Группы битов складываются как целые числа. Полученная сумма делиться на количество групп ключей и остаток от деления используется как номер группы ключей. Возможная организация хешированного индекса показана на рис. 9. Файл хешированного индекса состоит из двух частей: каталога групп, и области записей. Каталог групп представляет собой массив указателей на списки групп, изанимает требуемое количество последовательных виртуальных блоков файла в начале. Каждый список групп представляет собой список виртуальных блоков, которые отведены под записи группы. В каталоге групп хранится указатель на первый блок группы и каждый блок содержит указатель на следующий блок. Каждый блок содержит несколько записей фиксированной длины с полями под значение ключа, указатель на запись основного файла и флаг использования. Флаг использования говорит о том, содержит ли запись актальные значения или является свободным пространством15.Каталог групп имеет относительно небольшой размер и потому во многих случаях может храниться в ОП. Поиск в хешированном индексе с такой организацией происходит следующим образом: