Гайдамакин Н. А. 4 страница

 

Рис. 2.5. Пример операции ПЕРЕСЕЧЕНИЕ

• операция ПРОИЗВЕДЕНИЕ (ДЕКАРТОВО) — выпол­няется над таблицами-отношениями с разными схемами. Резуль­татом является таблица-отношение, схема которой включает все поля первой и все поля второй таблицы. Кортежи (строки-за­писи) результирующей таблицы образуются путем последова­тельного сцепления каждого кортежа первой таблицы-отноше­ния к каждому кортежу второй таблицы-отношения. Количе­ство кортежей результирующей таблицы соответственно равно произведению количества кортежей первой таблицы на коли­чество кортежей второй таблицы. На рис. 2.6 иллюстрируется пример операции произведения;

• операция ВЫБОРКА (горизонтальное подмножество) — выполняется над одной таблицей-отношением. Результатом яв­ляется таблица-отношение той же схемы, содержащая подмно­жество кортежей исходной таблицы-отношения, удовлетворя­ющих условию выборки;

Рис. 2.6. Пример операции произведения

• операция ПРОЕКЦИЯ (ВЕРТИКАЛЬНОЕ ПОДМНО­ЖЕСТВО) —также выполняется над одной таблицей-отноше­нием. Результатом является новая таблица-отношение, схема ко­торой содержит только некоторое подмножество полей исход­ной таблицы-отношения. Каждому кортежу исходной таблицы соответствует кортеж итоговой таблицы, образованный соот­ветствующими значениями по полям, вошедшим в итоговую таблицу-отношение. При этом в итоговой таблице кортежи-дуб­ликаты устраняются и поэтому мощность итоговой таблицы (ко­личество кортежей) может быть равна или меньше исходной. На рис. 2.7 приведен пример операции проекции;

Рис. 2.7. Пример операции проекции

• операция СОЕДИНЕНИЕ — выполняется над таблица­ми-отношениями с разными схемами. В каждой таблице-отно­шении выделяется поле, по которому будет осуществляться со­единение. При этом оба поля должны быть определены на од­ном и том же домене. Схема итоговой таблицы-отношения включает все поля первой таблицы и все поля второй таблицы (как в произведении). Кортежи итоговой таблицы-отношения образуются путем сцепления каждого кортежа из первой таб­лицы с теми кортежами второй таблицы, значения которых по полю сцепления одинаковы. На рис. 2.8 приведен пример опе­рации соединения;

Рис. 2.8. Пример операции соединения

• операция ДЕЛЕНИЕ — выполняется над двумя табли­цами-отношениями, первая из которых называется делимым, а вторая делителем. При этом схема таблицы-делителя должна состоять из подмножества полей таблицы делимого. Схема ито­говой таблицы-отношения содержит только те поля таблицы-делимого, которых нет во второй таблице-делителе. Кортежи итоговой таблицы-отношения образуются на основе кортежей первой таблицы (делимого) по значениям полей, вошедших в итоговую таблицу при условии того, что если взять произведе­ние (декартово) итоговой таблицы-отношения и второй табли­цы-отношения (делителя), то образуются соответствующие кор­тежи первой таблицы (делимого). На рис. 2.9 приведен пример операции деления.

Рис. 2.9. Пример операции деления

В своем исходном виде манипуляционная составляющая реляционной модели не предусматривает операции над поля­ми-атрибутами и схемами таблиц-отношений. Однако на прак­тике применение рассмотренных выше операций манипулирования данными может приводить к временным нарушениям тре­бований ограничения целостностей, которые преодолеваются специальными операциями переименования, удаления, добав­ления полей-атрибутов.

Реляционная модель организации данных сыграла трудно переоценимую роль в развитии программного обеспечения АИС. Именно реляционные СУБД были тем программным ин­струментарием, на основе которого происходила массовая ин­форматизация малых и средних предприятий и организаций в 80-х годах. В начале 90-х годов реляционные СУБД стали фак­тическим стандартом для построения самых разнообразных информационных систем. Вместе с тем проявились и определен­ные ограничения реляционной модели, которые не позволяют адекватно описывать такие сложные предметные области, как конструирование, производственные технологические процес­сы и др. Поэтому в 90-х годах были предприняты попытки со­здания новых усовершенствованных моделей организации дан­ных в виде постреляционных СУБД и объектно-ориентирован­ных СУБД. К сожалению, до сей поры ни одна из попыток создания и описания новых моделей описания данных не стандартизована, и количество коммерческих СУБД, основан­ных на новых моделях данных, исчисляется единицами.

2.3. Внутренняя схема баз данных фактографических АИС

Изначально и по сей день программное обеспечение АИС (СУБД) в качестве места физического размещения данных ори­ентировано на внешнюю (дисковую) память. Как уже отмеча­лось, размещение данных во внешней памяти, точнее эффек­тивность доступа к ним во внешней памяти, существенно вли­яет на эффективность обработки данных. В результате важным аспектом АИС является внутренняя схема базы данных, кото­рую организует и поддерживает СУБД.

В общем плане внутренняя схема базы данных включает три основных компонента, представленные на рис. 2.10.

Рис. 2.10. Cocтав внутренней схемы базы данных

Центральным компонентом внутренней схемы являются ин­формационные массивы, включающие собственно данные (ин­формационных объектов логической схемы БД, т.е. в реляци­онных СУБД таблиц), и массивы индексов, являющихся специ­альными дополнительными конструкциями для ускорения доступа к данным основных информационных объектов. Ин­формационные массивы в большинстве СУБД состоят из од­ной или нескольких так называемых страниц, каждая из которых содержит совокупность некоторых единичных элементов, называемых физическими записями. В результате, единичным элементом внутренней схемы баз данных АИС является физи­ческая запись, в большинстве случаев совпадающая по смыслу с логической записью, т. е. в реляционных СУБД с табличной строкой.

Способы организации записей в страницах (расположение, добавления, корректировка, удаление) составляют физические структуры данных, которые образуют третий (низший) уро­вень представления информации в информационной системе (см. рис. 1.4).

Важным компонентом внутренней структуры является ка­талог БД, в котором размещается системная информация по логической структуре БД, включающая описание основных ин­формационных объектов (имена, структура, параметры, связи) и ограничения целостности данных. Организация системной информации БД определяется особенностями конкретной СУБД, а сам каталог может входить непосредственно в файлы данных (область описателей данных) или составлять отдель­ный информационный массив.

Как уже отмечалось, в состав автоматизированного банка данных АИС помимо самой базы данных входит и прикладной компонент, образуемый совокупностью интерфейсных элемен­тов представления, ввода и обработки данных, типовых запро­сов и процедур обработки данных, а также «событий» и «пра­вил», отражающих правила и специфику предметной области АИС (так называемые «правила бизнеса»). Соответственно во внутренней схеме БД выделяется специальная область, в кото­рой размещается информация по прикладному компоненту АИС.

Все три части внутренней структуры и их составные эле­менты (например, информационные массивы отдельных инфор­мационных объектов БД) могут размещаться в одном едином файле базы данных или в разных файлах. Во втором случае внутренняя схема БД определяется совокупностью и порядком расположения данных файлов.

2.3.1. Физические структуры данных

Страничная организация информационных массивов БД оп­ределяется общей спецификой доступа к данным больших объе­мов. Доступ к физическим записям во внешней памяти в боль­шинстве СУБД осуществляется через считывание в оператив­ную память страниц файла данных, содержащих соответствующие записи. Непосредственная обработка записей производится в оперативной памяти, для чего СУБД образует и поддерживает, как уже отмечалось, специальные буферы, в ко­торых временно размещаются страницы, содержащие обраба­тываемые записи. После завершения обработки страница с со­ответствующими записями «выталкивается» из буфера и фик­сируется в дисковом файле.

Аналогичным образом осуществляется размещение и дос­туп к индексным массивам. В итоге общий принцип организа­ции доступа к данным во внешней памяти можно проиллюст­рировать схемой, приведенной на рис. 2.11.

Физические структуры организации файлов данных под­разделяются на линейные и нелинейные.

В линейных структурах в одну страницу файла базы дан­ных объединяются записи-кортежи одной таблицы (информа­ционного объекта), которые располагаются в последователь­ном (линейном) порядке друг за другом. Каких-либо ссылок, указателей на связи между записями не предусматривается.

Если не применяется специального порядка размещения за­писей в страницах (так называемая «расстановка» записей), то при добавлении записей в большинстве случаев в линейных структурах каждая новая запись помещается непосредственно за последней записью. Если страница файла данных заполня­ется, то для соответствующей таблицы выделяется дополни­тельная страница.

Рис. 2.11. Общий принцип организации внутренней схемы базы данных

Удаление записей в линейных структурах может произво­диться двумя способами. В первом способе при удалении запи­си сразу же осуществляется автоматическое перезаписывание на новых позициях всех строк-записей, лежащих за удаляемой, с целью уплотнения и ликвидации появляющихся пустых мест. Подобный подход обеспечивает максимальную эффективность использования дискового пространства, но вызывает существен­ные накладные расходы при любых операциях по удалению записей. Поэтому другим, достаточно распространенным спо­собом является простое «вычеркивание» удаляемой записи без перезаписывания всех записей, лежащих за удаляемой, с соот­ветствующим появлением пустых мест в страницах файла дан­ных. Ведение базы данных в этом случае может быть организо­вано так, чтобы при превышении общего объема пустых мест в странице выше определенного значения (скажем, больше 30%) специальный компонент СУБД автоматически производил дефрагментацию страниц, устраняя пустые места по ранее удален­ным записям. В некоторых СУБД запуск данной процедуры предоставляется непосредственно самому пользователю (адми­нистратору) для периодического уплотнения (сжатия) файла базы данных.

При корректировках записей могут возникать случаи, ког­да новое значение изменяемого поля корректируемой записи может потребовать больше (меньше) дискового пространства, ранее занимаемого под старое значение данного поля. Решение этой проблемы приводит к двум разновидностям линейных структур файлов баз данных.

Первая разновидность основана на подходе, позаимство­ванном из структуры текстовых файлов. Текстовый файл со­стоит из последовательно расположенных строк символов (на­бора байтов, определяющих номера символов строки в соот­ветствии с кодовой таблицей). Строки имеют различную длину и отделяются друг от друга символом возврата каретки. Строка в данном случае является физической записью, а доступ к ней осуществляется по ее номеру k путем последовательного счи­тывания (продвижения) k-1 предшествующих строк-записей (см. рис. 2.12).

Рис. 2.12. Линейная структура текстового файла

Если при корректировке какого-либо поля требуется боль­ше (меньше) дискового пространства, то файл расширяется (уп­лотняется) с автоматическим перезаписыванием на новых позициях всех строк, лежащих за корректируемой. Такой под­ход, так же, как и первый подход при удалениях записей, обес­печивает максимальную эффективность использования диско­вого пространства, но не дает возможности быстрого прямого доступа к нужной строке, так как местоположения записей по­стоянно меняются.

* Точнее говоря, перезаписываются все записи соответствующей страницы. Если она переполняется, то перезаписываются записи и следующей страницы, и т. д.

Другим подходом к организации линейных структур для ре­шения проблем корректировки данных является выделение для каждой записи одинакового дискового пространства, исходя из максимально возможного заполнения строк по установленным типам полей.

Такой подход применяется в широко используемых для со­здания «настольных информационных систем» (системы «ра­бочего стола») СУБД куста dBASE (dBase, FoxPro, C l ipper), ко­торые создают и оперируют базами данных в формате так на­зываемых dbf-файлов. Структура dbf-файла состоит из трех частей* — заголовка, блока описания структуры базы и инфор­мационной части (см. рис. 2.13). В заголовке последовательно представлены поля, которые определяют тип файла базы дан­ных (с memo-полями или без них), дату последнего изменения, номер последней записи, смещение, с которого начинается ин­формационная часть (записи), размер каждой записи. Блок опи­сания структуры размещается после заголовка до информаци­онной части и состоит из последовательности элементов, каж­дый из которых описывает определенное поле логической структуры (схемы) базы данных. Структура описания поля со­держит последовательное описание имени поля, типа поля (чис­ловое, текстовое, дата и т. д.), длины поля и заканчивается спе­циальным символом для отделения описания одного поля от другого. Информационная часть состоит из последовательнос­ти групп байтов одинаковой длины без специальных раздели­телей, каждая из которых собственно и выражает содержимое конкретной физической записи.

* Спенс Р. Сliрреr. Руководство по программированию. Версия 5.01 / Пер. с англ — Мн.: Tивали, 1994-480 с (с.428).

Рис. 2.13. Линейная структура dbf-файла

Такой способ организации данных обеспечивает прямой доступ к любой записи, так как ее положение (смещение) од­нозначно вычисляется по ее номеру и параметрам полей. Вме­сте с тем эффективность использования дискового простран­ства при таком подходе невысокая, так как в полях записей хра­нятся и пустые значения (т. е. физически занимают место). Тем не менее простота и эффективность доступа в таких линейных структурах файлов баз данных обусловили их популярность в тех случаях, когда объем данных невелик и вопросы эффектив­ности использования дискового пространства не существенны.

В нелинейных структурах записи одного информацион­ного объекта необязательно располагаются друг за другом на одной странице файла данных, но обязательно содержат специ­альные указатели на следующую запись объекта (односвязные списки) или на связанные записи других информационных объектов (многосвязные списки, древовидные структуры). Со­ответственно физические записи в нелинейных структурах включают помимо информационных полей одно или несколь­ко полей указателей, где размещаются адреса связанных запи­сей (см. рис. 2.14).

Рис. 2.14. Нелинейная структура данных ни примере односвяз­ного списка (поля указателей выделены жирными рамками)

Непосредственная адресация* связанных записей обеспе­чивает в большинстве случаев более эффективный, чем в ли­нейных структурах, доступ к данным. Однако расплатой за это являются существенно большие и сложные по сравнению с линейными структурами затраты и процедуры преобразова­ния (перетряски) файла базы данных при любых операциях до­бавления, удаления и корректировки записей, так как помимо проблем определения мест размещения записей и появления пустых мест в файле данных добавляется проблема перенаст­ройки указателей на связанные записи после изменения дан­ных.

* Реализуется в виде прямой или косвенной адресации. При прямой адресации в указателях размещаются физические адреса начала связанных записей. При косвенной адресации в указателях находятся номера связанных записей, физические адреса кото­рых отыскиваются по специальному справочнику, в который ставятся на учет физичес­кие адреса всех новых записей.

 

Образование страниц физических записей файлов данных осуществляется на основе той или иной стратегии минимиза­ции расходов на доступ к записям и расходов на операции их добавления, удаления и корректировки, и существенным обра­зом зависит от типа конкретной нелинейной структуры. Одной из таких стратегий является минимизация расходов на доступ к записям, связанным на логическом уровне отношением «Один-ко-многим», что обусловлено широкой распространенностью таких отношений в огромном количестве предметных облас­тей АИС. Данная стратегия основывается на использовании иерархических древовидных структур.

Общая схема этой стратегии такова. Для записей информа­ционного объекта на стороне «Один» образуется страница файла данных, в которую последовательно (как в линейных структу­рах) помещаются соответствующие записи. При появлении в базе данных связанных записей для каждой записи из страни­цы объекта на стороне «Один» образуются «подчиненные стра­ницы» для размещения соответствующих связанных записей объекта на стороне «Многие». В свою очередь, подчиненные записи сами могут иметь свои подчиненные записи, для кото­рых создаются соответствующие страницы, и т. д. (см. рис. 2.15, а.

Рис. 2.15. а. Пример нелинейной древовидной иерархической структуры данных

Если в процессе ведения базы данных какая-либо страни­ца переполняется, то для нее образуется связанная страница-продолжение на основе техники односвязного списка.*

* В конце каждой страницы выделяется специальное поле-указатель на возмож­ное продолжение страницы (т.н. цепной список) помимо того, что каждая запись стра­ницы сама содержит поле-указатель на страницу подчиненных записей.

 

При таком подходе действительно обеспечивается эффек­тивная обработка связанных записей, так как осуществляется не единичное, а сразу страничное их считывание в буферы опе­ративной памяти. Временные затраты на поиск и обработку за­писей в буферах оперативной памяти существенно меньше зат­рат на считывание данных из «медленной» внешней памяти и блоковое (страничное) считывание обеспечивает существенный выигрыш в расходах на доступ и обработку связанных записей.

Однако во многих предметных областях АИС отношения между информационными объектами могут порождать ситуа­ции наличия у определенных записей на стороне «Многие» сра­зу нескольких разных предков на стороне «Один» (см., например, рис. 2.3), что не вписывается в рамки подобных древовид­ных иерархических структур. Решение таких проблем обычно осуществляется через введение избыточности (дублирования) данных по связанным записям или другими способами.

Для формализованного описания нелинейных структур при­меняют аппарат теории графов, в рамках которого подобные иерархические древовидные структуры называются деревья­ми.* На рис. 2.15, б приведено условное изображение корневого дерева, соответствующего иерархической нелинейной струк­туре данных на рис. 2.15, а, а также термины и понятия, связан­ные с ним. Вершины (узлы) дерева по отношению друг к другу могут быть предками или потомками. Предок может иметь не­сколько потомков, но каждый потомок имеет только одного предка. Вершины, имеющие общего предка, называются бра­тьями. Вершины, имеющие потомков, называются внутренни­ми. Внутренняя вершина, не имеющая предков, называется корнем дерева. Вершины, не имеющие потомков называются лис­тьями. Все внутренние вершины корневого дерева упорядочиваются по уровням иерархии. Уровень узла определяется количеством предков до корня дерева. Количество уровней называется высотой дерева.

* Деревом называется связный неориентированный граф без циклов (см., напри­мер Лекции по теории графов / Емелнчев В. А., Мельников О. И., Сарванов В.И., Тышкевич Р.И.—М.: Наука, 1990, или Асанов М.О. Дискретная оптимизация: Учеб­ное пособие. —Екатеринбург: УралНАУКА, 1998.

 

Рис. 2.15, 6. Условное изображение средствами теории графов нелинейной древовидной иерархической структуры

Еще одним важным параметром деревьев является макси­мально возможное количество потомков у одного предка. Дан­ный параметр называется степенью дерева. Деревья степени больше двух называются сильноветвистыми. И наконец, важ­ным в практическом плане для нелинейных структур данных является понятие сбалансированности дерева. Различают сба­лансированность по степени вершин, когда каждая внутрен­няя вершина может иметь количество потомков, ограниченное определенной и одинаковой для всех вершин величиной {ар­ность дерева) и сбалансированность по высоте, когда путь (ко­личество вершин) от корня до любого листа дерева одинаков или различается не более чем на единицу.

Развитый математический аппарат теории графов позволил разработать для древовидных структур данных оптимальные по определенным критериям операции обхода (поиска нужной записи), включения (добавления новой записи) и исключения (удаления записи) с целью минимизации расходов как по дос­тупу, так и по изменению данных. Хорошая алгоритмизируемость этих операций предопределила широкое использование нелинейных древовидных структур в схемах физической орга­низации данных, обеспечиваемых СУБД.

2.3.2. Индексирование данных

Как уже отмечалось, стандартным приемом повышения эф­фективности доступа к записям в базах данных является созда­ние индексных массивов по отдельным, обычно ключевым по­лям. Идея индексов основана на том факте, что если для повы­шения эффективности доступа к конкретному кортежу-записи использовать линейное упорядочение кортежей в таблице (ска­жем, по алфавиту для текстовых ключевых полей или по возра­станию для числовых ключевых полей), то накладные расходы по «перетряске» всей таблицы после добавления/удаления строк-кортежей превысят выигрыш во времени доступа. Струк­тура индексов (индексных массивов) строится так, чтобы на основе некоторого критерия можно было бы быстро находить по значению индексируемого поля указатель на нужную запись (строку) таблицы и получать к ней доступ. При этом совокуп­ность записей-кортежей базовой таблицы не обязательно упо­рядочивать, а при их изменении необходимо изменить только лишь индексный массив.

Как и для информационных массивов самих данных (таб­лиц), так и для индексных массивов применяются линейные и нелинейные структуры. В качестве линейных структур ин­дексов в большинстве случаев выступают инвертированные списки. Инвертированный список строится по схеме таблицы с двумя колонками — «Значение индексируемого поля» и «Но­мера строк»* (см. рис. 2.16). Инвертированные списки чаще все­го применяются для индексации полей, значения которых в раз­ных строках-записях могут повторяться, к примеру, поле «Год рождения» таблицы «Сотрудники» (в реляционных базах дан­ных такие поля не могут быть ключевыми).

* На практике не номера строк базовой таблицы, а номера страниц файла БД, где находится соответствующая строка.

 

Значение индексируемого поля ("Год рождения")	Номера, строк
	5, 17, 123, 256
	31, 32, 77
	11, 45, 58, 167, 231
	7, 8, 9, 10, 234, 235, 236

Рис. 2.16. Пример инвертированного списка

Строки инвертированного списка упорядочиваются по зна­чению индексируемого поля. Для доступа к нужной строке исходной таблицы сначала в упорядоченном инвертированном списке отыскивается строка с требуемым значением поля,* за­тем считывается номер соответствующей строки (строк) в ис­ходной таблице и далее по нему уже осуществляется непосред­ственный доступ к искомой строке базовой таблицы.

* Способы поиска в линейно упорядоченных структурах см., например, в работе: Вирт Н.. Алгоритмы и структуры данных: Пер. с англ.—М.: Мир, 1989.

 

При добавлении новой строки в базовую таблицу ее значение по индексируемому полю ищется в ранее составленном индексе. Если соответствующая строка инвертированного спис­ка отыскивается (т.е. подобное значение индексируемого поля среди строк таблицы уже встречалось и было поставлено на учет), то в ячейку второго столбца соответствующей строки индекса дописывается номер страницы, куда была помещена соответствующая строка базовой таблицы. Если такого значе­ния в индексе нет, то создается новая строка индекса и осуще­ствляется переупорядочение нового состояния индексного мас­сива.

При удалении строки из базовой таблицы также осуществ­ляется поиск соответствующей строки в индексном массиве и осуществляется вычеркивание в индексе соответствующего номера отсылаемой строки базовой таблицы. Если при этом других строк в базовой таблице с таким же значением индекси­руемого поля не осталось (соответствующая ячейка индекса стала пустой), то удаляется и вся данная строка индекса с пос­ледующим переупорядочением всего индексного массива. При этом за счет того, что индекс в виде инвертированного списка содержит лишь один столбец значений, затраты на «перетряс­ку» при добавлении или удалении записей существенно мень­ше по сравнению с тем, если бы переупорядочение происходи­ло непосредственно в самой базовой таблице.*

* Кроме того, строки базовой таблицы можно упорядочивать только лишь по какому-либо одному полю, а индексные массивы можно создавать сразу по нескольким полям.

 

Индексы в виде инвертированных списков являются осо­бенно эффективными в том случае, когда значения индексиру­емого поля часто повторяются, образуя равномерные по мощ­ности группы. В этом случае количество ситуаций, при кото­рых требуется добавление или удаление строк индекса, невелико, и затраты на переупорядочение индекса при измене­ниях данных в базовой таблице незначительны. В результате выигрыш по затратам на доступ существенно превышает на­кладные расходы по переупорядочению индекса в процессе ве­дения базы данных.

Нелинейные структуры индексов применяются для созда­ния индексных массивов ключевых полей или тех полей, значения по которым не повторяются. При организации индексов в таких случаях чаще всего используются уже упоминавшиеся древовидные иерархические структуры в виде Б-деревьев. Б-дерево представляет собой корневое сбалансированное силь­но ветвистое дерево.

Каждая внутренняя вершина, если она полностью запол­нена, содержит информацию о n–1 различных последователь­но возрастающих значениях индексируемого поля по следую­щей схеме, приведенной на рис. 2.17.

где: Х _i – i-е значение индексируемого поля, при этом Х _i J X _{i+ 1} – указатель на вершину, содержащую значения индексируе­мого поля, меньшие или равные X _i.

Рис. 2.17. Структура внутренней вершины Б-дерева

Число n называется порядком Б-дерева.

Листовая вершина, в отличие от внутренней, содержит ин­формацию о нахождении страницы в файле базы данных с за­писями-кортежами, имеющими соответствующие значения ин­дексируемого поля. Схема листовой страницы представлена на рис.2.18.

где: Р _k – указатель на страницу файла данных, содержащую строку (строки) со значением индексируемого поля, равным Х _k.

Рис. 2.18. Структура листовой вершины Б-дерева

Сбалансированность Б-дерева означает одинаковое количество потомков до листовой вершины по любым раз­ветвлениям от корневой вершины. В качестве примера на рис. 2.19 приведено Б-дерево 3-го порядка уровня 2, пост­роенное для поля «Год рождения» таблицы «Сотрудники».

Рис. 2.19. Пример Б-дерева 3-го порядки уровня 2

Как правило, порядок Б-дерева выбирается таким, что­бы информация одной полностью заполненной вершины соответствовала странице файла данных. В силу того что объем одной страницы файлов данных существенно боль­ше размера полей, то в большинстве случаев в одну пол­ностью заполненную страницу вместе с указателями по­мещается большое количество значений индексируемого поля, исчисляемое сотнями и даже тысячами значений (n >> 100...1000). Это обстоятельство обусловливает сравни­тельно небольшой уровень Б-деревьев на практике (поряд­ка 2...4) даже в тех случаях, когда количество строк в ба­зовой таблице исчисляется десятками тысяч. В результате доступ к нужной записи по определенному значению ин­дексируемого поля через Б-дерево осуществляется за небольшое количество страничных обменов между внутрен­ней и внешней памятью по следующему алгоритму: