B-Tree Filer 5.0
----------------
Руководство пользователя
------------------------
Авторские права (с) 1989, TurboPower Software.
Все права сохраняются.
Первое издание март 1989.
P.O.Box 66747
Scotts Valley, CA 95066
Служба технической поддержки: 408-438-8608
Compuserve: 724572131
с 9 утра до 5 дня по среднетихоокеанскому времени,
с понедельника до пятницы.
Упоминаемые торговые марки
--------------------------
TurboPower Software и отдельный логотип TurboPower это
торговые марки фирмы TurboPower Software.
Turbo Professional это зарегистрированная торговая марка
фирмы Sunny Hill Software, используемая по лицензии TurboPower
Software.
B-Tree Filer это торговая марка фирмы TurboPower Software.
BTREE-ISAM это торговая марка фирмы Enz EDV-Beratung Gmbh
(Западная Германия).
Turbo Pascal, Turbo Assembler, Turbo Database Toolbox и
Turbo Editor Toolbox это торговые марки и зарегистрированные
торговые марки фирмы Borland International.
MS-DOS, MS-NET и Macro Assembler это торговые марки фирмы
Microsoft Corporation.
IBM PC, XT, AT, PS/2, IBM PC LAN и NetBIOS это торговые
марки или зарегистрированные торговые марки фирмы International
Buisiness Machines Corporation.
Novell, NetWare, SFT, TTS и International Packet Exchange
(IPX) это торговые марки или зарегистрированные торговые марки
фирмы Novell Inc.
Arcnet это зарегистрированная торговая марка фирмы Datapoint
Corporation.
3Com это торговая марка фирмы 3Com Corporation.
Network-OS это торговая марки фирмы CBIS, Inc.
PC-NET это торговая марка фирмы Orchid Technology, Inc.
PC-MOS/386 это торговая марка фирмы Software Link, Inc.
Ethernet, Internetwork Packet Protocol и Sequenced Packet
Protocol это торговые марки фирмы Xerox Corporation.
Btrieve это зарегистрированная торговая марка SoftCraft, Inc.
WordStar это зарегистрированная торговая марка MicroPro
International Corporation.
Содержание
----------
1. Введение ...............................................
A. Требования к системе ...............................
В. Поставляемые файлы .................................
С. Как приступить к работе.............................
D. Соглашение о приобретении...........................
2. Принципы работы .........................................
A. Данные и ключи......................................
В. Организация B-дерева................................
С. Управление ключами..................................
3. Использование B-Tree Filer...............................
A. Файловые блоки......................................
В. Организация программы...............................
С. Примеры программирования............................
D. Управление файловым блоком..........................
4. Идентификаторы B-Tree Filer..............................
A. Константы...........................................
В. Типы................................................
С. Переменные..........................................
D. Процедуры и функции.................................
5. Введение в B-Tree Net....................................
A. Требования к системе................................
В. Задание сети........................................
С. Номера рабочих станций..............................
D. Сетевой интерфейс...................................
6. Использование B-Tree Net.................................
A. Организация программы...............................
В. Степени запирания...................................
С. Преобразование однопользовательских программ........
D. Примеры программирования............................
7. Идентификаторы B-Tree Net................................
8. Утилиты B-Tree Filer.....................................
A. Записи переменной длины.............................
В. Экранный просмотр...................................
С. Перепостроение поврежденного файлового блока........
D. Реорганизация файлового блока.......................
E. Сортировка..........................................
F. Числовые ключи......................................
9. Сетевые утилиты..........................................
А. Novell NetWare......................................
B. NetBios.............................................
C. SHARE...............................................
D. Сетевые демонстрационные программы..................
10. Приложения..............................................
A. Коды ошибок.........................................
В. Краткие описания процедур и функций.................
С. Преобразование из Borland Database Toolbox..........
D. Преобразование из Softcraft Btrieve.................
E. Использование B-Tree Filer с Turbo Professional.....
F. Исходный код B-Tree Filer...........................
G. Оверлеи и B-Tree Filer..............................
1. Введение
-----------
Хранение и управление данными представляют собой одну из
центральных проблем в электронной обработке данных. Не будет
преувеличением, если сказать, что многие программисты имеют
основной доход именно от работы с базами данных. До сих пор не
существовало достаточного числа программных средств, которые
позволяли бы быстро и эффективно писать программы в Turbo Pascal,
работающие с базами данных. И тут на сцену выходит B-Tree Filer.
B-Tree Filer предлагает вам высококачественную библиотеку
для простого и эффективного управления базами данных. Он включает
в себя многие средства, делающие его вне конкуренции:
- Интегральная поддержка многопользовательских, сетевых баз
данных.
- Строгий контроль ошибок и режимы безопасности,
обеспечивающие максимальную целостность данных.
- Он написан на Turbo Pascal, причем обеспечивается полный
исходный код продукта.
- Поддержка записей фиксированной и переменной длины.
- Все индексы хранятся в одном файле для минимизации
числа используемых логических номеров файлов.
- Отдельные файлы данных и файлы индексов для максимизации
целостности данных.
- Во время выполнения не требуется иметь резидентных в
оперативной памяти программ (TSR-программ).
- Мощные модули с утилитами для полноэкранного просмотра,
реорганизации и сортировки файлов данных.
- Поддержка сетей Novell, MS-NET, а также всех прочих сетей,
совместимых по NetBIOS.
- Модули доступа к сети, обеспечивающие управление файлами,
управление принтерами и передачу сообщений в сети.
B-Tree Filer основан на улучшенной версии алгоритма
сбалансированного B-дерева, который зарекомендовал себя как
лучший метод доступа к данным в больших базах данных. Емкость
базы данных, поддерживаемая B-Tree Filer, настолько велика, что
вам практически не нужно об этом беспокоиться:
- Максимальное число записей данных: 2,147,483,647
- Максимальное число ключевых элементов: 2,147,483,647
- Длина ключа: от 1 до 255, по умолчанию 30 символов максимум
- Максимальное число индексов на одну базу данных: 750,
по умолчанию 100
- Диапазон длины записи данных: от 21 до 2,147,483,647 (DOS
и архитектура 8086 ограничивают эту величину значением 65,535)
- Максимальное число рабочих стпнций: 32,767 (по умолчанию
50)
Как вы уже, наверное, знаете, B-Tree Filer существует в двух
версиях. Однопользовательская версия позволяет вам писать базы
данных, работающие на отдельных PC, тогда как
многопользовательская версия включает в себя средства для
запирания записей и доступа к сети. Для различения этих версий в
данном руководстве мы используем фразу "B-Tree Net", когда речь
идет о средствах, специфичных для сетевой версии, и "B-Tree
Filer", когда данное средство работает независимо от версии.
Каждый раздел настоящего руководства поясняет, какие средства
обеспечивает каждая из версий. Отметим, однако, что B-Tree Filer
разработан таким образом, что вы можете писать с его помощью
простые однопользовательские прикладные программы, которые затем
легко можно модифцировать для работы в сети.
B-Tree Filer является версией TurboPower Software солидного
и респектабельного продукта из Западной Германии: BTREE-ISAM.
Этот продукт появился в Европе два года назад и имеет заслуженную
репутацию благодаря высокому быстродействию и надежности. Кроме
перевод на английский, фирма TurboPower Software улучшила
исходный пакет, включив в него новые утилиты виртуальной
сортировки и доступа к сети. Мы обеспечиваем тот же самый высокий
уровень обслуживания и поддержки данного продукта, к которому
наши пользователи привыкли по предыдущим продуктам нашей фирмы.
А. Требования к системе
-----------------------
Для того, чтобы использовать B-Tree Filer, вам необходимо
иметь следующее:
1. IBM PC, XT, AT (или близко совместимую машину), либо
PS/2, работающую в операционной системе DOS 2.0 или старше. При
использовании B-Tree Net сама сеть может потребовать наличия DOS
3.1 или старше.
2. Turbo Pascal версии 4.0 или 5.0.
3. Два дисковода для гибких дисков. Безусловно, желательно
иметь и жесткий диск.
4. Используемый размер оперативной памяти сильно зависит от
длины ключа и выделенных буферов. Обычно B-Tree Filer использует
50К или 100К оперативной памяти.
Необязательные средства:
5. Borland Turbo Assembler (TASM) или Microsoft Macro
Assembler (MASM). Требуется тоько при необходимости
модифицировать исходный код на языке ассемблера в конкретных
участках B-Tree Filer.
6. Сетевое аппаратное обеспечение и операционная система,
совместимые с B-Tree Filer. Сюда входят Novell, 3Com, PC-Net, PC
LAN, MS-NET, Network-OS, PC-MOS/386 и другие. Любая сеть,
поддерживающая вызовы DOS 3.x для запирания записей, может
работать совместно с B-Tree Filer.
Существуют также и определенные требования к программисту. B
-Tree Filer представляет собой полную реализацию алгоритма
индексации Байера-Баума (обычно известного как В-дерево). Хотя B-
Tree Filer и содержит реализацию данного алгоритма, программист
должен быть знаком с основами произвольного доступа к файлам и
использованием модулей, к которым обращается компилятор Turbo
Pascal. Для полного понимания многих из кодов ошибки,
генерируемых B-Tree Filer, рекомендуется также знакомство с
файловой системой MS-DOS.
B. Поставляемые файлы
---------------------
B-Tree Filer поставляется на одной дискете в случае
однопользовательской версии, либо на двух дискетах в случае
версии, поддерживающей работу в сети. Прежде чем пользоваться
этими дискетами, рекомендуется сделать их запасные копии. Файлы
на дискетах не защищены от копирования.
На дискете(дискетах) вы найдете следующин файлы:
Диск FILER (одно- и многопользовательские версии):
--------------------------------------------------
READ.ME
Если вы обнаружите на дискете файл с этим именем, прочтите
его, прежде чем продолжить работу. Этот файл содержит самые
последние дополнения к типографски изданной документации.
NETDEMO.EXE
ADDRESS.DAT
ADDRESS.IX
Обеспечивают полную демонстрацию свойств B-Tree Filer. Более
подробную информацию о том, как использовать данную программу,
см. в разделе 1.С, "Как приступить к работе". Отметим, что
NETDEMO компилируется для работы в однопользовательскй системе.
Для активации многопользовательских средств необходимо
разархивировать и перекомпилировать исходный код, который
находится в FILER.ARC. NETDEMO использует преимущества,
предоставляемые библиотекой Turbo Professional фирмы TurboPower
для ввода данных и редактирования поля памяти (memo). Вторая,
более простая версия, называемая SIMPDEMO, также включена только
в исходной форме; для компиляции этой версии Turbo Professional
не требуется.
BIGSORT.EXE
Пример использования модуля виртуальной сортировки, MSORT.
Сортирует текстовые файлы любых размеров. Для получения списка
опций сортировки просто наберите BIGSORT.
GETFILER.BAT
Командный файл для извлечения из архива FILER.ARC конкретных
модулей B-Tree Filer. Инструкции по использованию данного
команднного файла см. в Приложении F.
ARCX.COM
Малая версия утилиты ARC, выполняющая только разархивацию.
Данная утилита извлекает несжатые файлы из FILER.ARC. Для
получения краткой справки по работе программы наберите ARCX и
затем . Для разархивации исходных текстов B-Tree Filer без
использования GETFILER.BAT просто скопируйте FILER.ARC в рабочую
директорию, где имеется еще как минимум 700К свободной памяти и
введите ARCX FILER.ARC, находясь в этой директории. По завершении
разархивации FILER.ARC можно удалить из этой директории.
FILER.ARC
Данный архив содержит полный исходный код для
однопользовательской версии B-Tree Filer, включая модули FILER,
BROWSER, VREC, REBUILD, REORG, VREORG, VREBUILD, MSORT и NUMKEYS,
а также исходные коды NETDEMO и SIMPDEMO. Этот архив следует
раскрыть для использования указанных модулей при компиляции
B-Tree Filer как одно-, так и многопользовательской версии. В
архив включен также файл FILER.MAK.
Диск NET (только для многопользовательской версии)
--------------------------------------------------
NETINFO.EXE
Демонстрация модулей сетевых утилит. Идентифицирует текущую
сеть и обеспечивает информацию об ее конфигурации.
NSEND.EXE
NRECEIVE.EXE
Демонстрация техники пересылки сообщений в сети; использует
правила NetWare или NetBios, в зависимости от того, что именно
доступно. Более подробную информацию см. в разделе 9.D, "Сетевые
демонстрационные программы".
GETNET.BAT
Командный файл для извлечения из архива NETFILER.ARC
конкретных модулей B-Tree Net. Использование данного командного
файла описано в Приложении F.
ARCX.COM
Вторая копия утилиты для разархивации. Для разархивации
многопользовательского исходного кода без использования
GETNET.BAT просто скопируйте NETFILER.ARC в рабочую область с как
минимум 500К свободной дисковой памяти и введите ARCX NETFILER.
NETFILER.ARC
Этот архив хранит полный исходный код многопользовательской
версии B-Tree Filer, включая сетевую поддержку модулями FILER,
NETWARE, NETBIOS и SHARE, а также исходные коды демонстрационных
программ. Вы должны раскрыть данный архив, чтобы активировать
многопользовательские средства модуля FILER. В архив также входит
файл NETFILER.MAK.
C. Как приступить к работе
--------------------------
Для того, чтобы прочувствовать свойства B-Tree Filer, вы,
вероятно, захотите запустить программу NETDEMO. Версия,
поставляемая на дискете FILER, компилируется для
однопользовательского режима и содержит небольшие файлы данных и
индексов, готовые для просмотра и внесения изменений. Чтобы
воспользоваться ими, скопируйте NETDEMO.EXE, ADDRESS.DAT и
ADDRESS.IX в рабочую директорию. (Если вы хотите попробовать
запустить сетевую версию NETDEMO, вам потребуется сначала
перекомпилировать ее с соответствующими определениями. Информацию
по этому вопросу см. в разделе 5.B, "Задание сети".)
NETDEMO демонстрирует различные свойства B-Tree Filer, в том
числе:
- Одно- или многопользовательские действия в одной и той же
программе.
- Множественные типы ключей в одном индексном файле.
- Режим сохранности, защищающий целостность данных.
- Записи переменной длины.
- Полноэкранное редактирование баз данных.
- Средства высокого уровня, обеспечивающие очистку файлов
данных и пересоздание индексных файлов.
NETDEMO.EXE включает также средства библиотеки TurboPower
Turbo Professional - экраны вводы данных с контролем их
достоверности, а также редактирование полей памяти (memo). Для
перекомпиляции NETDEMO.EXE вы должны иметь Turbo Professional
версии 5.02 или старше. Если у вас нет этой версии, вы можете
поэкспериментировать с поставляемым исходным файлом SIMPDEMO.PAS,
который также заархивирован в FILER.ARC. Он работает подобно
NETDEMO, но в нем отсутствуют средства записей переменной длины и
экранов ввода с контролем достоверности.
NETDEMO работает с файлом адресов, который имеет следующие
поля:
FirstName : String[15];
LastName : String[15];
Company : String[25];
Address : String[25];
City : String[15];
State : String[02];
Zip : String[10];
Telephone : String[12];
MemoLen : Word;
Memo : variable length buffer of 1-1200 bytes
Для быстрого поиска записей используются индексные ключи.
Первичный ключ (не позволяющий наличия дубликатов) представляет
собой комбинацию полей LastName и FirstName. Вторичным ключем
является поле Zip.
Программа NetDemo позволяет вам добавлять, модифицировать
или удалять записи, просматривать список записей, отсортированный
по любому ключу, выполнять поиск по любому ключу, печатать
записи, а также перестраивать индексы после очистки файла от
удаленных записей. Для упрощения всех этих операций NETDEMO
использует полноэкранный режим отображения на дисплее.
B-Tree Filer Demo Program Modify Key: Last Name
========================================================================
| Zip Name ======= Modifying Record #4 =============== |
|02100 Dukakis, Michael | First name [Philippe ] | |
|10016 Dvorak, John C. | Last name [Kahn ] | |
|95066 Folks at, The | Company [Borland International ] | |
|98073 Gates, Bill | Address [1800 Green Hills Road ] | |
|67890 Goeshere, Your Name | City [Scotts Valley ] | |
|60123 Jackson, Jesse | State [CA] | |
|95999 Jobs, Stehpen | Zip [95066-0001] | |
|95066 Kahn, Philippe | Telephone [408-438-8400] | |
|95555 Lucas, George | Notes [ ] | |
|97520 Mace, Paul =========================================== |
|02142 Manzi, Jim ================ Notes ==================== |
|12121 North, Oliver |Sure, Microsoft's bigger, but they don't | |
|90403 Norton, Peter |have a horns section | |
|84057 Petersen, Paul | | |
|03458 Pournelle, Jerry | | |
|77071 Presley, Elvis | | |
|11111 Quayle, J. Danforth | | |
|23456 Swaggart, Jimmy | | |
|30311 Turner, Ted | | |
|56789 Tyson, Mike ==Line:1 Column:1 7% Insert Indent Wrap= |
========================================================================
ModAddDelFindKeyPrnInfoPurgeQuit
Поскольку программа NETDEMO предназначена для сетевых
операций, она должна быть способна определить уникальный номер
рабочей станции, который нужен для B-Tree Filer. Если ваша опция
поддержки сети определена как NoNet (по умолчанию компилируется в
поставляемом .EXE-файле), Novell или MsNetMachName, вам не о чем
беспокоиться, так как в этом случае номер станции определяется
автоматически. Однако, если была задана сетевая опция MsNet, вы
должны передать NETDEMO в командной строке одну опцию - номер
рабочей станции. Например,
NETDEMO 10
зарегистрирует вас на рабочей сстанции номер 10.
Затем NETDEMO спросит у вас, желаете ли вы работать в "Режиме
сохранности данных" ("Save Mode"). В этом режиме B-Tree Filer
всегда может восстановить данные в случае системного или сетевого
сбоя. Такая надежность обеспечивается за счет скорости выполнения
программ, но в случае интерактивного ввода данных потери скорости
будут неощутимы для пользователя.
NetDemo пытается открыть существующий набор данных в файлах
ADDRESS.DAT и ADDRESS.IX. Если эти файлы найдены, NETDEMO
продолжает работу. В противном случае программа спрашивает,
желаете ли вы создать новый (пустой) наор данных. Для того, чтобы
вам было легче исследовать работу программы NETDEMO, мы поставляем
некоторый набор адресов в указанных файлах.
Если вы создаете новый набор данных, NETDEMO сперва направит
вас к экрану ввода записей. Введите соответственные поля записи, а
затем нажмите , чтобы выйти из редактора записи.
Помните, что ключ, образуемый комбинацией полей LastName и
FirstName, должен быть уникальным во всем наборе записей.
(использование в качестве первичного ключа только имени как
правило не годится, поскольку при этом относительно велика
вероятность дублирования записей. NETDEMO избегает создания
искусственного поля типа "номер клиента" или другого такого поля.
В случае появления дублирующихся ключей в NETDEMO вы должны
специально изменить одно из входящих в ключ имен.)
После того, как набор данных будет содержать как минимум одну
запись, NETDEMO предложит вам полноэкранное окно редактирования. В
этом окне вы можете использовать клавиши и для
навигации между записями набора данных, клавиши и -
для горизонтального скроллинга, позволяющего просматривать все
поля, а также процие клавиши управления курсором для изменения
позиции высвеченной линейки, обозначающей текщую выбранную запись.
Модифицировать или удалять выбранные записи можно при помощи
других команд NETDEMO.
При активном окне полноэкранного редактирования вам выдается
линейка меню, расположенная в нижней части экрана. В этой линейке
указаны функциональные клавиши, нажатия которых активизируют
различные функции NETDEMO. Эта линейка выглядит следующим образом:
ModAddDelFindKeyPrnInfoPurgeQuit
Ниже приводится краткое описание каждой команды:
Модификация
Редактирование содержимого текущей выбранной записи. По
окончании редактирования NETDEMO перестроит индекс записи.
Помните, что запись должна иметь уникальный первичный ключ.
Закончив редактирование, нажмите , чтобы подтвердить
правильность внесенных изменений, либо , чтобы отменить их и
вернуться к предыдущей версии. Вы можете также модифицировать
данную запись, нажав Enter>, когда высвеченная линейка находится
на данной записи.
Добавление
Добавление новой записи. Для подтверждения необходимости
добавления новой записи нажмите затем , а для отмены
добавления - .
Удаление
Удаление текущей выбранной записи. NETDEMO позволит вам затем
подтвердить или отменить решение об удалении записи.
Поиск
поиск записи. NETDEMO предоставит вам полноэкранный шаблон
поиска, в котором вы сможете ввести параметры поиска по любым
интересующим вас полям. Поиск в NETDEMO производится без учета
регистра, и соответствие не обязательно должно быть полным.
Например, введение "IB" в имени компании будет при поиске
соответствовать записям вида "IBM" или "Ibsen Baking Company".
Если вводимые вами поля поиска являются частью индексных полей
NETDEMO (LastName и Zip), то NETDEMO выполнит быстрый поиск по
индексу, чтобы найти исходное соответствие, за которым может
следовать последовательный поиск для просмотра других,
не-индексных полей поиска. Если NETDEMO не находит полного
соответствия, она пытается поместить курсор в окне полноэкранного
редактирования в позицию, как можно ближе соответствующую
заданному критерию поиска.
Выбор ключа
По умолчанию NETDEMO представляет записи, отсортированные по
первичному ключу (LastName). При помощи клавиши можно
переключиться на любой другой ключ, когда записи будут выведены по
ключу Zip. Текущий активный ключ сортировки всегда указан в
верхней строке экрана.
печать
Печать всех записей. При нажатии NETDEMO сначала выводит
на дисплей небольшое меню. вы можете выбрать печать записей в
последовательности ключей LastName или Zip, либо вообще отменить
запрос печати. Если вы выбрали печать, NETDEMO записывает все
записи (одна строка на каждую запись) на принтер PRN по умолчанию.
Когда NETDEMO печатает, вы в любой момент нажатием любой клавиши
можете снять печать.
Информация
В нижней строке экрана выводится информация о текущем наборе
данных с адресами. Сюда входит общее число записей в файле данных,
число удаленных записей, режим работы базы данных (Save или Normal
- повышенной защиты или обычный), а также текущий номер рабочей
станции. для продолжения работы после вывода информации нажмите
любую клавишу. (При использовании записей переменной длины счетчик
записей может сбиваться. Вместо числа логических записей в базе
данных он будет показывать число "секций" для записей
фиксированной длины. Более подробную информацию см. в разделе 8.A)
Очистка
Перестраивает файлы данных и индексов в соответствии с
имеющимся файлом данных. Сначала файлы закрываются, а затем файл
данных читается в последовательном порядке. Ранее помеченные на
удаление записи фзически очищаются из файла данных, а затем
перестраивается индексный файл из промежуточного файла.
Выход
Эта команда служит для выхода в DOS. NETDEMO даст вам
возможность изменить решение о выходе в DOS.
Устройство программы NETDEMO
----------------------------
NETDEMO спользует простой метод запирания данных в
многопользовательской среде. Когда ей требуется гарантировать
доступ к конкретной записи, NETDEMO просто запирает всю базу
данных целиком (при помощи ) на самый
короткий, насколько это возможно, промежуток времени. При чтении
записей она сначала проверяет, не заперты ли они другими
пользователми. Если запись заперта, NETDEMO запрашивает, нужно ли
повторить попытку, либо отменяет операцию, если таков ваш выбор.
(Фактически процесс запирания более сложен, нежели описано здесь.
Полное описание его см. в разделе 6.B).
NETDEMO буферизует текущую выбранную запись в оперативной
памяти. Тем самым минимизируется число дополнительных операций
чтения, требуемой при модификации записи. Однако, это требует
дополнительного внимания, когда модифицированная запись должна
быть записана обратно на диск. Была ли запись за это время
удалена? Модифицировал ли ее кто-либо другой? Методы, используемые
для обработки этих ситуаций, см. в разделе 6.C и описании
процедуры NETDEMO Modify.
Помимо использования стандартных подпрограмм манипулирования
записями и ключами, NETDEMO также демонстрирует использование
модулей VREC, BROWSER и VREBUILD. Эти модули высокого уровня
упрощают работу с записями переменной длины, полноэкранное
отображение записей на дисплее, а также функции автоматической
перестройки индексных файлов.
Использование модулей B-Tree Filer
----------------------------------
Поскольку B-Tree Filer работает либо в Turbo Pascal 4.0 или
5.0, и поскольку многопользовательская версия требует, чтобы вы
задали директиву компиляции, специфичную для вашей сети, мы решили
не гадать, какие именно прекомпилированные файлы TPU вам
понадобятся. Вместо этого вы просто разархивируете исходные файлы
BTree Filer в рабочей директории, а остальную работу за вас
сделает компилятор.
Для разархивирования исходного кода скопируйте в рабочую
директорию следующие файлы:
ARCX.COM Программа разархивации с дискеты FILER
FILER.ARC Однопользовательское В-дерево с дискеты FILER
NETFILER.ARC Сетевые коды с дискеты NET, только в случае
приобретения вами многопользовательской
версии B-Tree Filer
Затем на приглашение DOS введите:
ARCX FILER
ARCX NETFILER
что вызовет разархивацию исходного кода. По завершении
разархивации вы можете удалить файлы архивов из вашей рабочей
директории.
для выбора конкретной сетевой опции вы должны отрежактировать
исходный файл BTDEFINE.INC и изменить директиву $DEFINE, которая
находится в верхней части этого файла. Выберите нужное определение
из числа приведенных после существующего определения. Более
подробную информацию о сетевых опциях см. в разделе 5.B.
Добавьте директорию, где находятся исходные файлы, в маршруты
поиска для компилятора. Компилятору понадобятся включаемые файлы,
файлы модулей, а также объектные файлы: не забудьте обновить все
установки компилятора для этих файлов.
После того, как все подготовительные операции выполнены, вы
можете использовать в ваших программах любые модули B-Tree Filer.
Для этого достаточно внести в ваши программы соответствующий
оператор USES, как показано ниже:
program Myprogram;
Uses ..., FILER, ...;
Еще примеры находятся в NETDEMO.PAS или SIMPDEMO.PAS. Кроме
того, см. разделы 3.B, "Организация программы" и 3.C, "Прмеры
программирования", где находится дополнительная вводная информация
о написании программ с использованием B-Tree Filer.
В каждом исходном архиве находится .MAK-файл, который вы
можете использовать с утилитой MAKE фирмы Borland (но не фирмы
Microsoft). Если вы приобрели многопользовательскую версию B-Tree
Filer, соответствующим файлом является NETFILER.MAK. В случае же
однопользовательской версии это файл FILER.MAKE. Использование
этих файлов не является обязательным, поскольку компилятор Turbo
Pascal имеет соответствующее встроенное средство. Тем не менее, мы
поставляем эти файлы, поскольку они полностью задают зависимости
между всеми файлами B-Tree Filer. Для чтения и модификации
.MAK-файлов можно использовать любой текстовый редактор. Каждый
файл включает в себя полные инструкции о работе с файлом. Если вы
пожелаете более подробно углубиться в исходный код B-Tree Filer,
обратитесь к Приложению F, где содержимое каждого исходного файла
описано более подробно.
D. Соглашение о приобретении
-----------------------------
Данное программное обеспечение и сопутствующая документация
защищены законом об авторских правах Соединенных Штатов, а также
положениями Международного Договора. Любое использование данного
программного обеспечения в нарушение закона об авторских правах
или в нарушение положений данного Соглашения будут преследоваться
нами в силу наших возможностей.
Большие части данного программного обеспечения представляют
собой авторское право (c) 1986,87,88 Дипломированного математика
Ральфа Найгеля (Dipl.Math. Ralf Nagel). другие части программного
обеспечения представляют собой авторское право (c) 1989 фирмы
TurboPower Software. TurboPower Software распространяет защищенные
авторским правом работы Ральфа Найгеля по эксклюзивной лицензии
Enz EDV-Beratung Gmbh из Западной Германии.
TurboPower Software разрешает вам делать архивные копии
данного программного обеспечения для личного использования путем
получения запасной копии и защиты вашего приобретения от случайной
потери. Ни при каких обстоятельствах вы не можете копировать
данное программное обеспечение или документацию в целях
распространения между другими лицами. Ни при каких обстоятельствах
вы не можете удалить являющиеся частью программного обеспечения
или документации уведомления об авторских правах.
Вы можете распространять, без платы за версию времени
выполнения или любых других лицензий, ваши собственные
скомпилированные программы, основанные на любом исходном коде
B-Tree Filer. Вы не имеете право распространять любые исходные
коды B-Tree Filer, скомпилированные модули или скомпилированные
примеры программ без письменного разрешения TurboPower Software.
Отметим, что предыдущие ограничения не запрещают вам
распространять ваши собственные исходные коды или модули,
зависящие от B-Tree Filer. Однако, тот, кто получает от вас такие
исходные коды или модули, должен приобрести собственную копию
B-Tree Filer, чтобы на законном основании компилировать исходный
код или писать программы, использующие модули, обращающиеся к
B-Tree Filer.
Поставляемое программное обеспечение может быть использовано
только одним лицом на стольких компьютерных системах, сколько это
лицо использует. Мы расчитываем, что группы разработчиков
программного обеспечения будут приобретать у нас индивидуальные
копии программного обеспечения и документации по числу сотрудников
такой группы. По вопросам скидки с общего объема и по поводу
соглашений о лицензировании рабочих мест обращайтесь к TurboPower
Software.
Относительно физических экземпдяров дискет и документации,
поставляемых с B-Tree Filer, TurboPower Software гарантирует их
исправность и отсутствие в них дефектов материала и изготовления
на период в 30 дней с момента получения покупателем. Если в
гарантийный срок вы уведомили нас о таком дефекте, TurboPower
Software заменит дефектную дискету(дискеты) или документацию
бесплатно.
TurboPower Software гарантирует, что программное обеспечение
будет работать, как описано в данной документации, в течение 30
дней от даты получения. При обнаружении программной ошибки или
дефектности нам потребуется подробный отчет о возникших проблемах,
который позволит нам найти и зафиксировать проблему. Если вы
правильно уведомите нас о такой проблеме с программным
обеспечением в течение гарантийного срока, TurboPower Software
заменит дефектное программное обеспечение бесплатно.
TurboPower Software гарантирует также, что покупатель
останется полностью удовлетворен нашим продуктом весь период 30
дней со дня получения. Если по какой-то причине вы не
удовдетворены, а TurboPower Software не может решить вашу
проблему, обратитесь к стороне, у которой была произведена
покупка, за разрешением на возврат. Если продукт был приобретен
непосредственно у TurboPower Software, мы вернем вам полную
стоимость покупки данного программного продукта после получения
исходной дискеты (дискет) с программным обеспечением и
документации в неповрежденном виде. TurboPower Software практикует
возврат продуктов от своих официальных дилеров, но не поддерживает
прямого возврата платежа тем, кто не приобрел продукт
непосредственно на нашей фирме.
TurboPower Software не предполагает ответственности за
использование B-Tree Filer в сумме, превышающей исходную стоимость
приобретения данного программного обеспечения. TurboPower Software
ни в коем случае не может быть ответственна за любой
дополнительный ущерб, включая потерянные прибыли, потерянную
экономию, либо любой другой случайный или закономерный ущерб,
возникший вследствие использования или невозможности использования
данных программ, даже если TurboPower Software предупреждала о
возможности такого ущерба.
При использовании данного программного обеспечения
предполагается, что вы согласны с положениями настоящего
раздела. Если вы не согласны с ними, вы должны немедленно верную
весь пакет B-Tree Filer для получения возвращаемого платежа.
TurboPower Software предлагает телефонную поддержку B-Tree
Filer при технической возможности без дополнительных платежей. Мы
приглашаем вас звонить нам по телефону поддержки с понедельника по
пятницу с 9 утра до 5 вечера (по тихоокеанскому времени), и
обращаться за помощью. Мы также абонируем для поддержки
пользователя код CompuServe. Этот код и номера телефонов приведены
на титульном листе данного руководства.
Мы верим в поддержку наших клиентов и сделаем все от нас
зависящее, чтобы наше программное обеспечение делало ту работу,
для которой мы его разрабатывали!
2. Принципы работы
------------------
В данной главе приводятся некоторые теоретические
обоснования B-Tree Filer, определяется терминология и
описывается, каким образом происходит фундаментальное действие В-
дерева. Если вы уже прошли курс, рассматривающий В-деревья, либо
если вас не интересуют подробности устройства пакета, вы можете
непосредственно перейти к главе 3.
Разработчики программного обеспечения используют термин
"база данных" настолько часто, что его смысл в каждом конкретном
контексте часто остается неясным. В данном руководстве мы
используем этот термин для обозначения единственно некоторой
совокупности данных, хранимых для использования в прикладной
программе, не уточняя, в какой форме находится эта совокупность.
Мы формально определяем термин "Файловый блок" для обозначения
комбинации файла данных, индексного файла, хранящего ключи к
нему, и другой информации, используемой для управлением доступа к
этим файлам. С учетом этой терминологии мы можем перейти к
общим понятиям данных и ключей.
A. Данные и ключи
-----------------
Существует два базовых метода поиска в базе данных
конкретной информации:
- последовательный доступ к данным;
- индексно-последовательный доступ к данным, также известный
как прямой доступ.
Поиск при последовательном доступе сводится к чтению данных
от начала к концу файла, причем производится сравнение каждой
записи данных с желаемым значением. В случае больших наборов
данных этот метод является медленным и неэффективным. Для прямого
доступа к данным требуется знать позицию желаемой записи данных в
последовательном файле данных. Зная эту позицию, можно за одно
обращение прочесть нужную запись.
Информация, которая необходима для поиска записи данных,
доступна благодаря информации об индексном ключе, хранимой в
B-Tree Filer. Записи данных и ключи хранятся в двух независимых
файлах, файле данных и индексном файле.
Файл данных состоит из записей данных фиксированного
размера, хранимых одна за другой. Каждая запись данных
соответствует некоторому номеру, являющемуся адресом записи
данных, и определяющему позицию записи данных в файле данных.
Например, адрес 0 ссылается на самую первую запись файла данных
(в B-Tree Filer резервируется для внутреннего использования), а
адрес 1 определяет первую запись файла, доступную для
пользователя. Когда запись вводится в файл данных при помощи
подпрограммы B-Tree Filer , возвращается адрес записи
данных в файле данных, который затем может быть добавлен в
индексный файл с соответствующим ключом. Индексный файл содержит
ключи и значения адресов соответствующих записей в файле данных.
(Термины "адрес записи данных" и "номер записи" чередуются в
документации).
Для поиска конкретной записи данных в индексном файле ищется
ключ, для чего служит одна из подпрограмм B-Tree Filer, например,
. Если ключ найден, запись данных может быть прочитана
при помощи другой процедуры B-Tree Filer, , по номеру
адреса, возвращенному процедурой поиска. Если ключ не найден, то
метод поиска в В-дереве гарантирует, что такая запись данных
действительно не существует.
B. Организация В-дерева
-----------------------
Деревья представляют собой наиболее исследованные структуры
данных в вычислительной технике, а В-дерево является одним из
наиболее популярных деревьев. Многие думают, что В-дерево
означает "бинарное дерево", однако это не так. Буква "В" - это
первая буква фамилии "Bayer", который является одним из
изобретателей этой структуры данных. В-дерево - это гораздо более
богатая структура данных, нежели двоичное дерево, которая
специально была разработана для оптимизации поиска записей в
больших базах данных. Оставшаяся часть этой главы определяет
терминологию В-деревьев в целом, затем описывет, каким образом В-
деревья применяются для реализации баз данных. В следующем
разделе рассматриваются базовые алгоритмы В-дерева, применяемые
для поиска по дереву, а также для удаления и добавления к нему
элементов.
Терминология В-дерева
---------------------
Термин "древовидная структура" происходит от аналогии этой
общей структуры данных и изображения перевернутого дерева.
"Узел" В-дерева представляет собой совокупность одного или более
индексных ключей. "Ветви", соединяющие узлы, определяют
последовательность поиска для того, чтобы найти конкретное
значение ключа. Ветви дерева направлены вниз, начиная с "корня",
и кончая узлами, из которых уже новые ветви не выходят. Такие
узлы называются "листьями" дерева. (См. Рис.1 ниже.)
Высота дерева определяется максимальным числом ветвей, через
которое нужно "пройти" от корня до любого листа. Корень имеет
уровень 1, его прямые ветви имеют уровень 2, в свою очередь их
прямые потомки имеют уровень 3, и т.д. Все узлы-листья, т.е. все
узлы, не имеющие потомков, в случае структуры В-дерева
заканчиваются на одном и том же уровне.
^ ---------------
| | Корень |
| ---------------
| / \ <------- Ветвь
| / \
| -------- --------
Высота | Узел | | Узел |
| -------- --------
| / \ / \
| / \ / \
| -------- -------- -------- --------
\/ | Лист | | Лист | | Лист | | Лист |
-------- -------- -------- --------
Рис. 1: В-дерево порядка 2 и высоты 3
Число ветвей, выходящих из данного узла, называется
"степенью" узла; максимальная степень определяет степень дерева.
Например, двоичное дерево имеет степень два, поскольку каждый
узел имеет две ветви. Деревья со многими ветвями, например,
В-дерево, имеет степень выше двух. В B-Tree Filer степень дерева
устанавливается неявно, через константу , в значение
+1.
"Порядок" дерева определяется как минимальное число ветвей
для любого узла. Каждый узел В-дерева, за исключением корня,
должен быть как минимум наполовину заполнен; следовательно,
каждый узел, кроме корня, должен иметь не менее /2+1
ветвей. Это приводит к эффективному использованию памяти.
"Сбалансированным" является дерево, для которого уровни
узлов-листьев отличаются максимум на единицу. В-дерево
простирает эту оптимизацию далее, требуя, чтобы все дистья-узлы
имели один и тот же уровень. Это подразумевает, что безразлично,
по какому маршруту идет путь от корня, так как число шагов до
любого узла-листа всегда одинаково.
Конструкция В-дерева, по контрасту с бинарным деревом,
использует больше памяти, но гарантирует меньше обращений к диску
и следовательно, доступ к данным происходит значительно быстрее.
В-деревья для баз данных
------------------------
В-дерево организовано как "дерево поиска", т.е. ключи
хранятся в дереве в определенном порядке. Ключи, используемые для
доступа к записям в файле данных, хранятся в узлах этого дерева.
Элементарные индексы хранятся в каждом узле в порядке
возрастания. Первый элементарный индекс содержит наименьший ключ
для данного узла; последний элементарный индекс содержит
максимальный ключ для данного узла.
Элементарные индексы определяются как записи, содержащие
следующие поля:
- соответствующий ключ
- ссылка (адрес) к записи данных
- ссылка к узлу вперед
Ссылка к узлу (указатель в прямом направлении) указывает на
узел, содержащий ключ, имеющий большее значение, чем то, что
хранится в текущем элементе инжекса. (См. Рис.2 ниже.)
=======
---> | 'A' |
========================== | | 'B' |
---| Счетчик | | | 'C' |
| | Указатель назад |---- | x |
| |========================| -------
| | 'D' | =======
| | | ---> | 'E' |
| | | | | 'L' |
| | |---- | x |
| |------------------------| | x |
| | 'M' | -------
| | | =======
| | | ---> | 'N' |
| | | | | 'P' |
| | |---- | 'Q' |
| |------------------------| | 'S' |
-->| Ключ 'X' | -------
| Ссылка (адрес) к данным| =======
| Указатель вперед |--------> | 'Y' |
| | | 'Z' |
| | | x |
|------------------------| | x |
|xxxxxxxxxxxxxxxxxxxxxxxx| -------
|xxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxx|
==========================
Рис.2: Внутренняя структура В-дерева
Сам узел объявлен как запись и содержит:
- целое число, содержащее фактическое число элементарных
индексов, хранимых в данном узле
- обратная ссылка к узлу назад (указатель назад),
указывающая на узел, содержащий ключи, меньшие любого ключа в
данном узле
- массив собственно элементарных индексов.
В-дерево позволяет перемещаться по нему от узла к узлу,
благодаря использованию обратных указателей, что позволяет
находить меньшие ключи, и прямых указателей для поиска больших
ключей.
Наименьший ключ В-дерева является первым элементом в
узле-листе в левом краю дерева (который не имеет обратного
указателя, поскольку не существует меньших ключей), а наибольший
ключ - это последний элемент в самом правом узле-листе (который
не имеет указателя вперед, поскольку не существует больших
ключей). Маршрут поиска (начиная от корня) для нахождения
наименьшего и наибольшего ключа имеет одинаковую длину, поскольку
все листья-узлы В-дерева должны лежать на одном уровне.
Каждый узел содержит минимум и максимум
элементарных индексов. Корень составляет единственное
исключение в том смысле, что он может содержать менее
элементарных индексов.
Выбор значения требует некоторого компромисса.
Поиск ключей в больших страницах требует меньше обращений к
диску, и следовательно, работает быстрее, чем в случае меньших
страниц. поиск в странице идет сравнительно быстрее, чем загрузка
страницы с диска. Однако, большее значение увеличивает
требования B-Tree Filer к памяти, а также увеличивает время
чтения страницы. Значение по умолчанию 62 было выбрано
на основе тщательных экспериментов и гарантирует оптимум для
времени доступа и использования памяти.
B-Tree Filer также определяет максимальную высоту В-дерева
константой . При значении по умолчанию 8 В-дерево не
будет заполнено, пока туда не будет добавлено 10^14 ключей*
Поскольку 2^32 ключей меньше, чем 10^10, опасности переполнения В
-дерева не существует!
Ключи в индексном файле
-----------------------
Как уже было описано выше, ключи в индексном файле
обеспечивают связь с записями данных в файле данных. Каждый раз
при вводе записи данных должен быть добавлен соответственный
ключ, таким образом, чтобы запись данных могла быть найдена
индексным методом доступа.
Поскольку файлы индексов и данных хранятся раздельно, с
каждым из них возможны отдельные манипуляции. При удалении ключа
соответственная запись данных автоматически не удаляется. В этом
случае запись данных не может быть найдена методом индексного
доступа. Индексный доступ также невозможен, если запись данных
вводится в файл данных без одновременного добавления в индексный
файл элементарного ключа. Следовательно, для правильного
функционирования B-Tree Filer важно одновременно манипулировать
файлами индекса и данных.
Индексные ключи должны иметь тип String ().
Если в качестве ключа должно использоваться число, оно должно
сначала быть преобразовано в строку символов. (Подпрограммы для
таких преобразований находятся в модуле NUMKEYS, который описан в
разделе 8.F). Значение каждого элемента в строке является
величиной ASCII. При построении строк следует быть осторожным
(например, при использовании заглавных и строчных букв), чтобы
обеспечивалось правильное сравнение ключей.
Существует два типа ключей, которые различаются следующим
образом:
- первичные ключи: ключи, уникальные в базе данных
- вторичные ключи: ключи, которые можно вводить многократно.
Первичные ключи не могут быть дублированы в индексном файле
(это требование устанавливается подпрограммами индексации B-Tree
Filer). В качестве первичных ключей могут быть использованы
уникальные номера клиентов, счетов и т.д.
Вторичные ключи используются для не-уникальных элементов:
имен, адресов, весов и т.д. B-Tree Filer хранит внутри себя эти
возможно дублирующиеся ключи раздельно, комбинируя уникальные
ссылки к записи данных с каждым ключом. (Процесс комбинирования
выполняется логически, не требуя дополнительной памяти для
хранения ключа).
Максимальная длина ключа определяется константой
, которая может лежать в диапазоне от 1 до 255
(значение по умолчанию 30). Длина и тип каждого ключа
определяются значениями полей и , задаваемыми в
переменной B-Tree Filer типа .
Каждый ключ соответствует в точности одной записи данных,
хотя множество ключей может указывать на запись данных. В базе
данных с адресами ключом может являться имя, адрес или любое
другое поле. Число ключей, которое может указывать на запись
данных, определяется параметром , передаваемым
процедуре . В B-Tree Filer неважно, сколько ключей
используется для управления базой данных, так как все ключи
хранятся в одном индексном файле.
C. Управление ключами
---------------------
Как мы увидим ниже, добавление или удаление одного ключа
может потребовать существенной реорганизации В-дерева, чтобы
сохранить его требуемые свойства. В данном разделе мы описываем,
каким образом B-Tree Filer прозрачным для программиста образом
управляет В-деревом.
Поиск ключа
-----------
Поиск ключа в В-дереве всегда начинается с корневого узла.
Корень, как и любой другой загружаемый узел, просматривается
путем двоичного поиска. Число элементарных индексов, в текущий
момент хранимое в узле, делится пополам, и берется средний
индекс. Затем его ключевой элемент сравнивается с искомым ключом.
Если они идентичны, то поиск закончился успешно.
Если элементарный ключ не совпал с искомым ключом, то поиск
должен продолжаться. Поскольку ключи в узле всегда хранятся в
порядке возрастания, то сравнение текущего ключа с искомым
указывает направление для дальнейшего поиска. Если сравненный
ключ меньше искомого, то поиск идет вправо. Если же он больше
искомого, то поиск идет влево. Если ключ найден где-либо в
текущем узле, то поиск на этом оканчивается.
В противном случае для нахождения следующего узла могут быть
использованы прямые и обратные указатели. Прямой указатель
последнего элементарного индекса, ключ которого меньше желаемого
ключа, ведет к новому узлу с ключами, большими последнего
элемента, и меньшими, чем следующий элемент исходного узла. Затем
поиск повторяется в этом новом узле, который может находиться уже
в оперативной памяти, либо потребовать для доступа к нему
обращения к диску. Только когда поиск приводит к узлу, где
наименьший элементарный индекс больше ключа поиска, используется
обратный указатель. Далее поиск продолжается в этом узле, где
ключи меньше искомого. Поиск завершается успешно, если найден
заданный ключ, либо при неудачном завершении поиска, когда
достигнут узел-лист дерева, а соответствие обнаружено не было.
В-дерево позволяет также доступ к записям базы данных в
отсортированном последовательном порядке. Начиная с заданной
стартовой точки прямой указатель текущего индексного элемента
ведет к следующему ключу в отсортированной последовательности.
При достижении узла-листа алгоритм возвращается на предыдущий
уровень узла и продолжает со следующего, большего индексного
элемента. Это эквивалентно первому по глубине траверсированию
В-дерева. Для обозначения конкретного адреса в В-дереве
используется термин "последовательный указатель". Фактически
последовательный указатель представляет собой массив записей,
каждая из которых содержит одно число, определяющее узел, и
второе, указывающее на активный элемент в узле. Последовательный
указатель можно рассматривать как маршрут, ведущий от корня к
узлу, содержащему текущий элемент. Конкретные подпрограммы B-Tree
Filer инициализируют последовательный указатель известным
значением. Другие подпрограммы переопределяют указатель,
присваивая ему временное значение. Описания подпрограмм содержат
и описание воздействие их на последовательный указатель.
Добавление ключа
----------------
Если в индексный файл должен быть добавлен новый ключ, то
сначала В-дерево просматривается описанным выше методом, чтобы
убедиться, что такого ключа до сих пор не было. Если ключ
существует, то генерируется ошибка. (Помните, что дублирующиеся
ключи делаются уникальными путем включения адресных номеров их
записей данных). Если ключ не существует, то поиск заканчивается
в узле-листе с негативным результатом. По этому адресу
добавляется новый ключ. Если в этом узле-листе есть место еще для
одного ключа, то добавление выполняется добавлением нового ключа
в отсортированную позицию в индексном массиве узла. Однако, если
узел-лист заполнен - там уже имеется ключей, - то
В-дерево должно быть модифицировано таким образом, чтобы создать
место для хранения нового ключа. (См. рис.3 ниже.)
Требуемая область хранение создается расщеплением данного
узла на два. Индексные элементы, меньшие чем /2,
остаются в старом узле, а большие помещаются в новый узел.
Средний индексный элемент, меньший, чем индексные элементы нового
узла, используется для указания на этот новый узел, путем ввода
его в узел на предыдущем уровне дерева.
Если узел, в который должен вводиться этот средний индексный
элемент, также полон, то происходит расщепление следующего узла.
Рекурсивные применения этого метода могут привести к "делению"
всех узлов до корневого уровня. Даже сам корень при необходимости
может быть расщеплен. В таком случае средний индексный элемент из
последнего деления станет новым корнем, а дерево вырастет на один
уровень. Это единственный случай, когда высота дерева
увеличивается. Данное правило добавления ключей сохраняет четкую
характеристику В-дерева, состоящую в том, что все узлы-листья
должны лежать на одном уровне.
-------------
| J | |
-------------
/ \ Исходное состояние
------------- -------------
| J | | | M | |
------------- -------------
-------------
| J | |
-------------
/ \ Добавление P
------------- -------------
| J | | | M | P |
------------- -------------
-------------
| J | P |
-------------
/ | \ Добавление Q
------------- ------------- -------------
| F | | | M | | | Q | |
------------- ------------- -------------
Рис.3: Добавление ключей в В-дерево
При реализации расщепления узлов B-Tree Filer предлагает
дпльнейшее усовершенствование базовой теории В-дерева.
Перед расщеплением узла делается попытка выполнить "баланс
страницы", который делает свободнее некоторые узлы. Здесь
проверяется число индексных элементов соседнего узла. Если там
число элементов меньше, чем , индексные элементы из
переполненных узлов перемещаются в более свободные. Это позволяет
избежать лишних делений узлов.
Этот метод лучше в том плане, что он позволяет заполнить все
узлы ключами, экономя тем самым память. Это дает следующие
преимущества:
- уменьшается время поиска
- уменьшается размер индексного файла
- в памяти можно держать больше ключей одновременно.
При использовании непрерывно растущих, имеющих
последовательные значения ключей (номеров клиентов, например),
размер индексного файла может быть уменьшен на 30-50%.
Удаление ключа
--------------
Если ключ должен быть удален, сначала должен быть определен
адрес ключа в дереве. Это выполняется описанным выше способом.
Как и при добавлении ключа, ключ, найденный в узле-листе,
удалить легко. Для этого достаточно удалить элемент из массива
индексов этого узла.
Если после удаления узел имеет менее /2 индексных
элементов ("недостача"), можно предпринять одно из двух действий.
Либо из соседнего узла туда могут быть помещены индексные
элементы ("баланс страницы"), как описано выше для добавления
новых ключей. Либо, в случае, когда соседний узел также страдает
от "недостачи", две страницы могут быть объединены в одну
("слияние узлов", операция, обратная расщеплению). Страница,
являющаяся родительской для объединившихся узлов, также
уменьшается на один индексный элемент. Если она также будет
страдать от "недостачи", а балансировка страниц невозможна, то
опять повторится объединение с соседней страницей. При некоторых
обстоятельствах этот процесс дойдет до корня. Если произойдет
удаление единственного индексного элемента, составляющего корень,
то дерево сожмется до одного уровня. Это единственный путь, когда
В-дерево может потерять высоту.
Снова отметим, что файлы индексов и данных хранятся
раздельно. Если индексный элемент удаляется без удаления
соответственной записи данных, то такая запись остается
"сиротой" в файле данных, т.е. ее больше нельзя найти по
индексной ссылке.
Если ключ должен быть удален из другого адреса, нежели узел-
лист дерева, прямой указатель, указывающий на узел с большими
ключами, также будет потерян при удалении такого ключа, и
структура дерева будет испорчена. Чтобы предотвратить это,
берется следующий, наибольший по величине ключ в дереве, и
помещается по адресу, который занимал удаленный ключ. Вследствие
упорядоченности ключей он всегда будет находиться в листе-узле.
Таким образом, прямой указатель удаленного ключа останется
достоверным. После того, как новый ключ скопирован в позицию,
ранее занимаемую удаленным ключрм, он также должен быть удален из
своей бывшей позиции. Это выполняется по той же схеме, по которой
ключ удаляется из узла-листа. В случае, если узел, из которого
был удален ключ, имеет теперь менее /2 элементов, то
происходит его корректировка методами балансировки или слияния
узлов.
3. Использование B-Tree Filer
-----------------------------
По сравнению с плотным концептуальным изложением Главы 2,
данная глава более затрагивает практические вопросы. Здесь мы
покажем, как использовать B-Tree Filer при разработке ваших
прикладных программ. Примеры программ в разделе С помогут быстрее
войти в курс дело тем, кто лучше обучается на примерах.
A. Файловые блоки
-----------------
Как уже было отмечено выше, "файловый блок" представляет
собой комбинацию файла данных, индексного файла и прочей
информации, хранимой в оперативной памяти и на диске, и
описывающей состояние файлов данных и индексов. В случае
однопользовательских баз данных эта "прочая информация" хранится
в оперативной памяти и является первой записью файла данных,
которая всегда резервируется для внутреннего использования BTree
Filer. Для баз данных, открываемых в режиме сохранности, и для
многопользовательских баз данных файловый блок включает в себя
третий файл, называемый файлом диалога. В режиме сохранности этот
файл временно хранит данныеи ключи до тех пор, пока они не будут
успешно записаны в фактический файл данных или индексов. в
многопользовательских прикладных задачах файл диалога хранит
дополнительную информацию, требуемую для организации
взаимодействия между рабочими станциями сети.
B-Tree Filer может организовывать любое число файловых
блоков, ограниченное исключительно числом открытых файлов,
допустимое в данной операционной системе. Для каждого файла
данных существует только один индексный файл, независимо от числа
определенных для него ключей. Следовательно, если одновременно
должно быть открыто пять однопользовательских файловых блоков, то
операционная система должна разрешать десять различных открытых
файлов. Если должно быть открыто три многопользовательских
файловых блока, то операционная система должна допускать девять
открытых файлов DOS.
(MS-DOS для каждого процесса может максимально управлять
числом файлов, заданным параметром FILES=ЧИСЛО в файле
CONFIG.SYS. Поскольку первые пять файлов всегда используются DOS,
учтите это при подсчете общего числа файлов в запросе. Без
расширений DOS позволяет иметь в данной программе до 20
одновременно открытых файлов. B-Tree Filer включает в себя
процедуру , которая при работе в DOS 3.3 или
старше дает возможность увеличивать это число.)
Обращения к базам данных B-Tree Filer происходит через
указатель к файловому блоку. Это минимизирует распределение
статических данных за счет использования "кучи" для хранения
информации файлового блока, которая должна находиться в памяти.
Прикладная программа объявляет для каждого файлового блока
переменную-указатель типа , занимающуювсего
четыре байта в сегменте данных.
В. Организация программы
------------------------
Для доступа к подпрограммам B-Tree Filer используйте
оператор USE с именем модуля FILER в вашей главной программе и в
любых других модулях, где это необходимо. Программа должна быть
организована в следующую последовательность действий:
Макет программы
---------------
1. Создание страничного буфера вызовом
2. Открытие или создание нескольких файловых блоков вызовом
, или
3. Использование процедур или функций B-Tree Filer для
открытых файловых блоков
4. Закрытие всех открытых файловых блоков при помощи
5. Освобождение страничного буфера вызовом
Данная последовательность может быть повторена столько раз,
сколько это нужно. Кроме того, в промежутке между пунктами один и
пять файлы могут открываться и закрываться столько раз, сколько
потребуется.
Еще один важный аспект работы программы, который должен
обрабатываться на верхнем уровне программы, связан с обработкой
ошибок. B-Tree Filer экспортирует на верхний уровень булеву
переменную , которая устанавливается в значение True при
успешном завершении и в False в случае ошибки. Далее доступна
целочисленная переменная , позволяющая
классифицировать ошибку. Почти каждый вызов подпрограммы B-Tree
Filer следует завершать проверкой .
Режим сохранности или нормальный режим?
---------------------------------------
При открытии файлового блока вы имеете на выбор -
использовать либо , либо , -
чтобы определить, должен ли файловый блок обрабатываться
нормальным образом, или же должна применяться специальная схема,
обеспечивающая сохранность. При выборе схема
защиты использует третий файл, называемый диалоговым файлом (с
расширением "DIA"), который становится частью файлового блока.
При каждом доступе для записи к файлу данных или индексов в
режиме сохранности изменяемые данные сначала помещаются в
диалоговый файл. Новые данные вносятся в файл данных или индексов
только после успешной записи в файл диалога. Если это внесение
новых данных также завершилось успешно, то данные удаляются из
диалогового файла, и операция считается законченной. Кроме того,
после каждой дисковой операции все буферы DOS также сбрасываются
на диск, что гарантирует возможность реконструкции данных при
случайном срывае питания. При необходимости такая реконструкция
будет выполнена автоматически при следующем открытии файлового
блока (даже если он открывается в нормальном режиме).
Совершенно понятно, что протокол, ведущийся в режиме
сохранности, существенно увеличивает затраты времени на
обновление файлов B-Tree Filer. Прежде чем использовать режим
сохранности, рассмотрите следующие вопросы:
- Режим сохранности следует использовать только когда
описанный выше процесс реконструкции неприемлем. Реконструкция
5000 записей данных с 4 ключами занимает от 5 до 20 минут.
- Успешное завершение процедур или
независимо друг от друга гарантирует, что
все данные будут записаны на физический диск.
- Каждая прикладная программа в любом случае должна иметь
опцию Rebuild.
- Данные, используемые только одним пользователем, не столь
критичны, как например, данные, доступные через файл-сервер
многим пользователям сети.
Файловый блок, используемый в сети, является идеальным
случаем, когда желателен режим сохранности. Более подробная
информация находится в Главе 6.
Подготовка к использованию сетевых средств
------------------------------------------
Многие однопользовательские прикладные программы в конце
концов переносятся в сетевую среду. Для упрощения этой задачи все
вызовы процедур и функций B-Tree Net доступны и в
однопользовательской версии. Эти подпрограммы не выполняют
фактических обращений к сети, а вызывают вместо этого
соответственные однопользовательские подпрограммы. Если в
однопользовательской среде выполняемые ими действия не
определены, то такие подпрограммы просто не выполняют никаких
действий. См. Главу 5, где находится введение в
сете-ориентированные подпрограммы B-Tree Filer.
Любая однопользовательская прикладная программа, для которой
существует хотя бы минимальная вероятность последующего переноса
в многопользовательскую среду, должна использовать вызовы сетевой
версии, а не однопользовательской. Дополнительные затраты
ресурсов для многопользовательских вызовов минимальны, тогда как
экономия усилий при конечном переносе программы в сеть может быть
значительной. См. в Главе 7 таблицу, в которой приводятся
соответствия между одно- и многопользвательскими подпрограммами.
С. Примеры программирования
---------------------------
Следующие примеры программирования иллюстрируют операции с
файловыми блоками B-Tree Filer. Каждое основное действие -
определение структуры записи, открытие базы данных, добавление и
удаление записей и ключей, а также поиск информации, - отображено
в приводимых примерах. Вы можете отметить, что многие
подпрограммы представляют собой просто оболочку вокруг
подпрограмм Filer нижнего уровня, в которую добавлена обработка
ошибок и конкретная информация для данной прикладной программы.
Такой подход вообще рекомендуется для прикладных программ,
написанных на базе B-Tree Filer.
Следующие примеры кодов можно найти в файле EXAMPLES.PAS на
дискете FILER. (EXAMPLES.PAS фактически не служит ни для каких
целей, но он может оказаться полезным с точки зрения
использования его фрагментов в ваших программах).
Определения данных
------------------
Сначала пользователь должен определить тип записи, в которой
будет храниться информация базы данных. Этот тип может иметь
следующий вид:
type
PersonDef =
record
Del : LongInt;
FirstName : String[20];
LastName : String[25];
Street : String[30];
City : String[30];
State : String[2];
ZipCode : String[5];
Telephone : String[15];
Comments : String[70];
Age : Integer;
end;
Первое поле, , типа LongInt, должно инициализироваться
прикладной программой в нулевое значение. Хотя это поле не
является обязательным требованием B-Tree Filer, мы рекомендуем
вам начинать такими полями все записи данных. B-Tree Filer
переопределяет значение этих первых четырех байтов при удалении
записи, чтобы организовать связный список свободного для
повторного использования пространства в файле данных. Многие
свойства B-Tree Filer, в частности перепостроения и реорганизации
файловых блоков, определяют достоверность данной записи, проверяя
для этого, содержат ли первые четыре байта записи нулевое
значение. (Удаленные записи всегда имеют ненулевое значение, а
достоверные - нулевое). Если поле не определено, то все эти
средства работать не будут.
Остальные поля относятся к предметной области программы.
Единственное накладываемое B-Tree Filer ограничение состоит в
том, что запись должна иметь размер в 21 байт или более. Это
ограничение является следствием того, что первая запись любого
файла данных содержит информацию, описывающую базу данных в
целом, позволяя B-Tree Filer открывать ее без использования
дополнительных файлов.
Для доступа к соответственному файловому блоку должна быть
объявлена переменная типа , как описано в
разделе 3.B, "Организация программы". Обычно эта переменная
должна являться глобальной по отношению ко всей программе.
var
PF : IsamFileBlockPtr; {Символическое имя для доступа к базе данных}
Распределение страничных буферов
--------------------------------
B-Tree Filer использует страничные буферы для хранения в
оперативной памяти стольких узлов В-дерева, сколько поместится,
оптимизируя тем самым время поиска. Его алгоритм требует, чтобы в
оперативной памяти одновременно находилось как минимум
узлов. Для распределения памяти этим страничным
буферам используется подпрограмма . Она позволяет
зарезервировать область кучи для другого использования, а затем
выделить оставшуюся часть кучи буферам.
procedure AllocatePageBuffer(HeapToRemain : LongInt);
var
NumberOfPages : Word;
begin
NumberOfPages := GetPageStack(HeapToRemain);
if not IsamOK then begin
{Не хватает памяти}
Halt;
end;
end;
возвращает ошибку только при невозможности
выделить память для минимум страниц. В этом случае
возвращаемое значение (здесь это NumberOfPages) будет содержать
число страниц, которое могло быть распределено, но не было
распределено. Типичная реакция на недостаточное количество памяти
состоит в выдаче сообщения об ошибке и последущем останове.
Для того, чтобы избежать избыточного расходования ресурсов
во многих подпрограммах нижнего уровня B-Tree Filer не проверяет,
была ли вызвана . Это должны обеспечить вы сами:
если об этом забыть, возможен сбой программы.
Дальнейшие детали относительно страничных буферов см. в
разделе с описанием .
Создание файлового блока
------------------------
К вашему удобству вы можете объявить константы, описывающие
число и длину ключей. Они будут использоваться во многих местах
программы, и когда вам наконец все же понадобится изменить число
или тип ключей, вы сможете оценить, насколько удобны эти
константы.
const
NrKeys = 3; {Число ключей}
Key1Len = 30; {Имя и фамилия}
Key2Len = 5; {Почтовый код}
Key3Len = 15; {Телефон}
function CreateFile : Boolean;
var
IID : IsamIndDescr;
begin
IID[1].KeyL := Key1Len; IID[1].AllowDupK := False;
IID[2].KeyL := Key2Len; IID[2].AllowDupK := True;
IID[3].KeyL := Key3Len; IID[3].AllowDupK := True;
MakeFileBlock(PF, 'TEST', SizeOf(PersonDef), NrKeys, IID);
CreateFile := IsamOK;
end;
CreateFile создаст необходимые файлы данных для нового
файлового блока. В вашем примере присваивает
PF файлу данных 'TEST.DAT' и индексному файлу
'TEST.IX'. Функция Паскаля SizeOf дает длину записи данных, т.е.
размер записи.
Параметр, описывающий ключи, определен в переменной IID типа
. IID перед вызовом должен быть
инициализирован. В данном примере для каждой записи данных
существует три ключа. (B-Tree Filer позволяет определить для
каждой записи до 100 ключей, каждый ключ до 30 символов в длину.
Эти значения могут быть изменены путем изменения констант в
FILER.PAS. Подробности см. в разделе 4.А).
описывает каждый ключ, задавая максимальную длину каждой троки и
то, является ли этот ключ первичным (уникальным) или вторичным
(допускающим существование дубликатов). Ключи могут создаваться
из любых данных; они не ограничиваются данными из одного поля. В
нашем примере первичный ключ буде являться результатом
конкатенации фамилии и имени. Вторичными ключами будут почтовый
код и номер телефона.
Открытие файлового блока
------------------------
function OpenFile : Boolean;
begin
OpenFileBlock(PF, 'TEST');
if not IsamOK then begin
OpenFile := False;
{Здесь может находиться часть программмы для сообщения об
ошибке на основе и .
Могут следовать действия по исправлению ошибки, например
реконструкция запорченного индексного файла,
как описано в разделах 3.D и 8.С.}
Exit;
end else
OpenFile := True;
end;
OpenFile показывает, каким образом может выглядеть функция
для открытия существующего файлового блока. Она содержит вызов
процедуры , которая открывает файловый блок в
нормальном режиме. (Вызов приведет к открытию
в режиме сохранности.) Использование глобальных переменных
и позволяет обнаруживать ошибки, которые
могут произойти при открытии файлов. Отметим, что информация о
длине записи или ключах для открытия уже существующего файлового
блока не нужна. B-Tree Filer считывает эту информацию из файла
данных и хранит ее в соответствующем файловом блоке в памяти.
Закрытие файлового блока
------------------------
function CloseFile : Boolean;
begin
CloseFileBlock(PF);
if not IsamOK then begin
CloseFile := False;
{Обработка ошибки}
Exit;
end else
CloseFile := True;
end;
Важным является то, чтобы перед выходом из программы каждый
файловый блок был закрыт. В противном случае буферизуемая
индексная информация может не попасть на диск, что приведет к
ошибкам при ее последующем использовании. Функция CloseFile может
выполнить эту задачу. Она закрывает индексный файл и файл данных,
вызывая для этого . Здесь также может происходить
обработка ошибок, хотя в этой точке число возможных
восстановительных действий невелико.
Операции с файлами индексов и данных
------------------------------------
Удобно написать одну функцию, которая возвращала бы ключи, с
которыми возможен доступ к файлу данных. Это гарантирует
непротиворечивость доступа к записям во всей задаче. CreateKey
представляет собой пример такой функции, создающей любую из трех
различных ключевых строк из полей записи.
function CreateKey(P : PersonDef; KeyNr : Integer) : IsamKeyStr;
begin
with P do
case KeyNr of
1 : CreateKey := StUpcase(Copy(LastName, 1, 20)+Copy(FirstName, 1, 10));
2 : CreateKey := ZipCode;
3 : CreateKey := Telephone;
else
CreateKey := '';
end;
end;
StUpcase это функция для преобразования строки аргумента к
верхнему регистру.
Теперь, когда файлы существуют и ключи могут быть созданы,
вам понадобятся подпрограммы для добавления, удаления, изменения
и поиска данных.
Добавление данных в файловый блок
---------------------------------
Для выполнения вставки новой записи требуется два шага.
Сначала вызывается для добавления записи в файл данных.
Эта подпрограмма возвращает (адрес записи данных),
описывающий положение записи в файле. Второй шаг требует
добавления каждого ключа в индексный файл при помощи .
Следующий пример проясняет ситуацию:
procedure UndoAdd(P : PersonDef; RefNr : LongInt; LastKey : Integer);
var
KeyNr : Integer;
Key : IsamKeyStr;
begin
for KeyNr := 1 to LastKey do begin
Key := CreateKey(P, KeyNr);
DeleteKey(PF, KeyNr, RefNr, Key);
if not IsamOK then begin
{Abort: слишком много ошибок}
Halt;
end;
end;
end;
function AddRecord(P : PersonDef) : Boolean;
var
KeyNr : Integer;
RefNr : LongInt;
Key : IsamKeyStr;
begin
AddRecord := False;
AddRec(PF, RefNr, P);
if not IsamOK then begin
{Обработка ошибки}
Exit;
end;
for KeyNr := 1 to NrKeys do begin
Key := CreateKey(P, KeyNr);
AddKey(PF, KeyNr, RefNr, Key);
if not IsamOK then begin
{Удаление до сих пор добавленных ключей}
UndoAdd(P, RefNr, KeyNr-1);
{Удаление новой записи}
DeleteRec(PF, RefNr);
{Обработка ошибки}
Exit;
end;
end;
AddRecord := True;
end;
После того, как новая запись данных была успешно введена в
файл при помощи , в цикле FOR один за другим создаются
ключи и добавляются в индексный файл при помощи .
Переменная RefNr содержит адрес, по которому записана новая
запись данных. Если во время операций с ключами встретились
ошибки (например, =10230, что означает дублирование
ключей), функция UndoAdd пытается удалить добавленные до сих пор
ключи, поэтому выход AddRecord может произойти аккуратно, не
испортив файловый блок. Однако, если при удалении произошли еще
ошибки, то дальнейшие попытки восстановления могут дать больше
проблем, чем решить6 поэтому программа должна быть абортирована.
AddRecord возвратит True, если все операции завершились успешно.
Удаление данных из файлового блока
----------------------------------
Функция DeleteRecord аналогична Addrecord.
procedure UndoDel(P : PersonDef; RefNr : LongInt; LastKey : Integer);
var
KeyNr : Integer;
Key : IsamKeyStr;
begin
for KeyNr := 1 to LastKey do begin
Key := CreateKey(P, KeyNr);
AddKey(PF, KeyNr, RefNr, Key);
if not IsamOK then begin
{Abort: слишком много ошибок}
Halt;
end;
end;
end;
function DeleteRecord(P : PersonDef; RefNr : LongInt) : Boolean;
var
KeyNr : Integer;
Key : IsamKeyStr;
begin
DeleteRecord := False;
{Убедиться, что эта запись не является уже удаленной}
if P.Del <> 0 then
Exit;
for KeyNr := 1 to NrKeys do begin
Key := CreateKey(P, KeyNr);
DeleteKey(PF, KeyNr, RefNr, Key);
if not IsamOK then begin
{Добавить ключи, удаленные к тому моменту}
UndoDel(P, RefNr, KeyNr-1);
{Обработка ошибки}
Exit;
end;
end;
DeleteRec(PF, RefNr);
if IsamOK then
DeleteRecord := True;
end;
Для того, чтобы предупредить разрушительные последствия
попытки удаления уже удаленной записи, проверяется поле P.Del,
чтобы убедиться, что эта запись данных не была удалена ранее. При
удалении записи данных действия в точности обратны тем, что
выполняются при добавлении записи. сначала делается попытка
удаления ключей, а затем записи данных. Делать ли попытку
отменить удаление в случае ошибки - это спорный вопрос. Мы
показали здесь UndoDel, однако вы можете решить, что имеет смысл
продолжать удаление ключей даже при неудачном завершении
.
Модифицирование записей
-----------------------
При необходимости модифицировать существующую запись
требуется обновление не только файла данных, но и удаление старых
ключей с добавлением новых. для этого требуется достаточно
сложная процедура, как показано в ModifyRecord.
function CheckRecord(P, POld : PersonDef) : Boolean;
begin
{Проверить, что: новая запись содержит достоверные ключи,
новая запись отлична от старой}
CheckRecord := True;
end;
procedure UndoMod(P, POld : PersonDef; RefNr : LongInt; LastKey : Integer);
begin
{Удалить все новые ключи}
UndoAdd(P, RefNr, LastKey);
if not IsamOK then begin
{Abort: слишком много ключей}
Halt;
end;
{Вернуть старые ключи}
UndoDel(POld, RefNr, LastKey);
if not IsamOK then begin
{Abort: слишком много ошибок}
Halt;
end;
{Вернуть старую запись}
PutRec(PF, RefNr, POld);
if not IsamOK then begin
{Abort: слишком много ошибок}
Halt;
end;
end;
function ModifyRecord(P, POld : PersonDef; RefNr : LongInt) : Boolean;
var
KeyNr : Integer;
begin
ModifyRecord := False;
if not CheckRecord(P, POld) then
Exit;
PutRec(PF, RefNr, P);
if not IsamOK then begin
{Обработка ошибки}
Exit;
end;
for KeyNr := 1 to NrKeys do begin
{Обновить модифицированные ключи}
if CreateKey(P, KeyNr) <> CreateKey(POld, KeyNr) then begin
DeleteKey(PF, KeyNr, RefNr, CreateKey(POld, KeyNr));
if IsamOK then
AddKey(PF, KeyNr, RefNr, CreateKey(P, KeyNr));
if not IsamOK then begin
UndoMod(P, POld, RefNr, KeyNr-1);
{Обработка ошибки}
Exit;
end;
end;
end;
ModifyRecord := True;
end;
Подпрограмма CheckRecord проверит, что новая запись, Р,
генерирует допустимые ключи (т.е. ее первичные ключи должны быть
непустыми). CheckRecord также проверит, чтобы новая и старая
записи не были идентичными, так как при этом только теряется
время.
ModifyRecord вызывает для перезаписи старой записи
данных на новую. Затем она удаляет из индексного файла каждый
измененный ключ и добавляет туда новый. В случае ошибки она
вызывает UndoMod, которая пытается выполнить аккуратное
восстановление исходной записи и ключей.
Переход к следующей или предыдущей записи данных
-------------------------------------------------
NextPrevRecord показывает, каким образом может быть
реализована функция для сканирования файла данных в порядке
индексов. "Последовательный указатель доступа" должен быть
спозиционирован за известным ключом, прежде чем NextPrevrecord
может быть вызвана в первый раз. Это можно сделать при помощи
любой из функций, , , ,
или .
function NextPrevRecord(var P : PersonDef;
var RefNr : LongInt;
KeyNr : Integer;
var Key : IsamKeyStr;
Next : Boolean) : Boolean;
begin
NextPrevRecord := False;
if Next then begin
NextKey(PF, KeyNr, RefNr, Key);
if not IsamOK and (IsamError = 10250) then
{Следующего ключа не было. Переход к первому ключу в файле}
NextKey(PF, KeyNr, RefNr, Key);
end else begin
PrevKey(PF, KeyNr, RefNr, Key);
if not IsamOK and (IsamError = 10260) then
{Следующего ключа не было. Переход к последнему ключу в файле}
PrevKey(PF, KeyNr, RefNr, Key);
end;
if not IsamOK then
Exit;
GetRec(PF, RefNr, P);
if not IsamOK then begin
{Обработка ошибки}
Exit;
end;
NextPrevRecord := True;
end;
Поиск записей данных
--------------------
Для того, чтобы найти запись данных индексным методом
доступа, ключ поиска должен быть задан по значению или по
соответствующему номеру ключа. Следующая подпрограмма
демонстрирует индексный поиск.
function FindRecord(var P : PersonDef;
var RefNr : LongInt;
KeyNr : Integer;
var Key : IsamKeyStr) : Boolean;
begin
FindRecord := False;
SearchKey(PF, KeyNr, RefNr, Key);
if not IsamOK then begin
{Определение причины неудачного завершения SearchKey,например:
IsamError = 10210 Не найдено ни заданного, ни большего ключей.
IsamError = 10175 Параметр KeyNr содержит неверное число.
Это ошибка программирования, которая не
может встречаться в законченной программе.}
Exit;
end;
GetRec(PF, RefNr, P);
if not IsamOK then begin
{Обработка ошибки}
Exit;
end;
FindRecord := True;
end;
Подпрограмма абортируется, если имеет значение
False после вызова из-за того, что запись данных
недоступна или произошла ошибка. возвращает True даже
если соответствия ключа найдено не было, если при этом доступна
следующая запись, с большим значением ключа. Фактический ключ
возвращается в вызывающую программу через переменную-параметр
FindRecord, Key. Если соответствия ключа не найдено,
также возвращает в RefNr относительный номер записи (адрес в
файле). По этому номеру считывает запись данных и
возвращает в Р. Процедура должна использоваться вместо
, если требуется точное соответствие ключей.
Поиск записи по не-индексированному полю несколько хитрее и
может быть реализован несколькими способами. Один из методов
игнорирует порядок индексов и просто читает из файла данных все
записи, пропуская помеченные на удаление. Другой метод состоит в
использовании подпрограммы для поиска записей в
последовательности сортировки по ключу. Это метод имеет
преимущество, если требуется поиск, состоящий из двух частей:
первая часть это индексный поиск по возможно дублирующемуся
ключу, а вторая часть это не-индексный поиск по другому полю.
Использование обеспечивает, чтобы первый ключ по
возможности оставался достоверным. ScanForRecord приводит пример
такого метода:
function MatchedRecord(P, Q : PersonDef) : Boolean;
begin
{Возврат True, если P и Q соответствуют
по некоторому критерию, например...}
MatchedRecord := (StUpcase(P.City) = StUpcase(Q.City));
end;
function ScanForRecord(var P : PersonDef;
KeyNr : Integer;
var RefNr : LongInt) : Boolean;
var
Done : Boolean;
Goal : PersonDef;
Key : IsamKeyStr;
begin
ScanForRecord := False;
Goal := P;
Done := False;
repeat
NextKey(PF, KeyNr, RefNr, Key);
if not IsamOK then
{Возможно, достигнут наибольший ключ}
Done := True
else begin
GetRec(PF, RefNr, P);
if not IsamOK then begin
{Обработка ошибки}
Done := True;
end else if MatchedRecord(P, Goal) then begin
{Найдено соответствие}
Done := True;
ScanForRecord := True;
end;
end;
until Done;
end;
В данном примере выполняется поиск записи, которая
"соответствует" исходной записи, переданной в параметре Р. Поиск
начинается с записи, следующей за той, что связана с текущим
последовательным указателем, и продолжается до записи, имеющей
наибольший ключ типа KeyNr. Подпрограмма MatchedRecord сравнивает
текущую запись с целью поиска, и если соответствие найдено,
ScanForRecord возвращает номер записи (в RefNo) и ее содержимое
(в Р).
В этих небольших примерах мы представили наиболее важные
операции B-Tree Filer. Эти подпрограммы были написано достаточно
просто, чтобы дать ясную иллюстрацию концепции. Более обширные
примеры можно найти в демонстрационной программе NETDEMO.
D. Управление файловым блоком
-----------------------------
Если файловый блок не был правильно закрыт в
, следующая попытка открыть его в
приведет к установке в значение 10010. Это всегда
будет происходить, если данные, которые находились в памяти, не
были записаны на диск.
Для восстановления прикладная программа или отдельная
утилита должна вызывать процедуру из модуля
REBUILD. (См. раздел 8.С).
Событий, ведущих к процессу перепостроения, можно избежать
несколькими способами:
- Вызывая в обработчике выхода из программы
Turbo Pascal, чтобы гарантировать, что файловый блок был закрыт
даже в случае неожиданной ошибки в программе.
- Используя режим сохранности (для этого файловый блок
должен быть открыт при помощи ).
- Вызывая в нужное время .
Использование может быть также
желательным, когда из файлового блока было удалено много записей,
а ввод вместо них новых в ближайшем будущем не ожидается.
Сетевые файловые блоки также могут быть реконструированы
этой процедурой. Во время реконструкции доступ к файловому блоку
другим рабочим станциям не разрешен.
4. Идентификаторы B-Tree Filer
------------------------------
Данная глава описывает большинство идентификаторов модуля
FILER пакета B-Tree Filer. Функции и процедуры организованы в
алфавитном порядке. Приложение В содержит список процедур и
функций, организованный по их назначению.
Некоторые идентификаторы здесь не описаны. Они предназначены
для внутреннего использования в модуле и служат для связи с
другими модулями, поставляемыми в составе B-Tree Filer.
Подробности см. в исходном коде.
А. Константы
------------
DatExtension = 'DAT';
IxExtension = 'IX';
DiaExtension = 'DIA';
Расширения файлов данных, индексов и диалога, соответственно.
MaxHeight = 8;
Задает самый глубокий уровень В-дерева.
MaxKeyLen = 30;
содержит максимально допустимую глубину ключа.
Более длинные ключи усекаются до этого значения. Допустимая длина
лежит вообще в диапазоне от 1 до 255 с умолчанием 30. Эту
константу можно модифицировать, отредактировав соответствующим
образом FILER.PAS и перекомпилировав модуль FILER.
MaxNrOfKeys = 100;
определяет максимальное число ключей для
одного файлового блока. Допустимые значения лежат в диапазоне от
1 до 750, с умолчанием 100. Непосредственное увеличение данной
константы увеличит память, требуемую для хранения переменной типа
. Эту константу можно модифицировать,
отредактировав соответствующим образом FILER.PAS и
перекомпилировав модуль FILER.
MaxNrOfWorkStations = 50;
содержит максимальное число рабочих
станций, используемое в сети. Обычно для типовой установки сети
достаточно значения 50, хотя многие современные сети могут иметь
до 100 и более станций. Допустимый диапазон имеет значения от 1
до 32767, но неоправданно увеличивая значение этой константы
повысит время доступа для всех сетевых операций. Эту константу
можно модифицировать, отредактировав соответствующим образом
FILER.PAS и перекомпилировав модуль FILER.
PageSize = 62;
Задает максимальное число ключей на странице В-дерева. Более
подробная информация об этой константе находится в описании
. Значение 62 близко к оптимуму характеристик
быстродействия файловых блоков на обычном жестком диске.
SearchForSequentialDefault : Boolean = False;
Состояние по умолчанию метода поиска, применяемого в
операциях и . Этот метод полезен для
восстановления из состояния ошибки типа "последовательный доступ
не разрешен", которое может возникнуть при модификации файлового
блока несколькими рабочими станциями. Более подробную информацию
см. в описании в Главе 7.
В. Типы
-------
IsamFileBlockName = string[64];
Все имена файлов, передаваемые в ,
или , должны быть этого типа.
Переменные этого типа должны содержать имя допустимого файла DOS,
прежде чем они будут переданы одной из вышеназванных процедур.
Имя дисковода и маршрута в имени файла опциональны. Отметим, что
и самое длинное имя маршрута ограничено длиной в 64 символа.
Расширения задавать нельзя. Они добавляются к имени
автоматически, используя для этого описанные выше константы.
IsamKeyStr = string[MaxKeyLen];
Все ключи, которые будут использованы для выполнения
индексных операций, должны быть этого типа.
IsamFileBlockPtr = ^IsamFileBlock;
Этот тип указывает на информацию6 описывающую каждый
файловый блок, открытый прикладной программой. Переменная этого
типа инициализируется при вызове любой из процедур:
, или . Все
последующие операции с файлами индексов и данных выполняются с
этой переменной.
IsamIndDescr = array[1..MaxNrOfKeys] of
record
KeyL : 1..MaxKeyLen;
AllowDupK : Boolean;
end;
Этот тип используется для передачи параметров, описывающих
индексный файл. Переменная этого типа передается в
. В переменной этого типа описаны длина и тип
каждого ключа. Дли на ключа можт быть значением от 1 до
и хранится в поле . Ключи могут быть двух
разных типов, в зависимости от того, могут ли встречаться
дублирующиеся ключи:
1. Первичные ключи: AllowDupKey = False. Например, номер
клиента, который всегда уникален. В пределах данного
может быть определено более одного первичного
ключа. Помните, что B-Tree Filer не допускает добавления
дублирующихся первичных ключей при помощи .
2. Вторичные ключи: AllowDupK = True. Например, фамилия или
почтовый код, которые не обязательно уникальны. будет
всегда добавлять вторичные ключи. Она делает их уникальными во
внутреннем представлении, включая в качестве неявной части ключа
относительный номер (адрес) записи данных.
NetSupportType = (NoNet, Novell, MsNet, MsNetMachName, CBISNet,
PCMOS386);
Этот тип описывает текущую активную опцю поддержки сети.
Функция возвращает значение данного типа. Для
однопользовательской версии B-Tree Filer всегда возвращается
значение NoNet ("Нет сети"). В противном случае возвращаемое
значение зависит от того, как был компилирован модуль FILER.
Подробности см. в разделе 5.В.
С. Переменные
-------------
IsamOK : Boolean;
Данная переменная устанавливается каждой подпрограммой
B-Tree Filer. Если ее значение равно True, то желаемая операция
была выполнена успешно. В противном случае переменная
будет содержать код, конкретизирующий происшедшую ошибку. Для
того, чтобы реализовать правильную обработку ошибок, гарантируя
тем самым надежность прикладного программного обеспечения,
следует проверять после вызова каждой подпрограммы
B-Tree Filer.
IsamError : Integer;
Эта переменная устанавливается каждой подпрограммой B-Tree
Filer. При удачном завершении операции эта переменная получает
нулевое значение; в противном случае она получает ненулевое
значение. Если переменная имеет значение False, то
соответствует типу происшедшей ошибки. Классификация
ошибки верхнего уровня может быть получена посредством вызова
функции . Полный список кодов ошибок приводится в
Приложении А.
D. Процедуры и функции
----------------------
Некоторые процедуры и функции не описаны здесь в
подробностях. Они используются в основном для взаимодействия с
другими модулями B-Tree Filer, такими как REORG и REBUILD. Если
вы работаете с B-Tree Filer на нижнем уровне, вы можете найти их
полезными для себя. Более подробную информацию см. в их исходном
коде.
procedure IsamAssign(var F : IsamFile; FName : IsamFileBlockName);
{ Присваивает имя DOS переменной типа IsamFile }
procedure IsamBlockRead(var F : IsamFile; var Destination; Len : Word);
{ Читает байтов из файла начиная с текущей позиции указателя
файла в }
procedure IsamBlockWrite(var F : IsamFile; var Source; Len : Word);
{ Записывает байтов в файл начиная с текущей позиции указателя
файла из }
procedure IsamClose(var F : IsamFile);
{ Закрывает файл }
procedure IsamDelete(var F : IsamFile);
{ Удаляет неоткрытый файл }
function IsamExists(Name : IsamFileBlockName) : Boolean;
{ Проверяет существование файла DOS }
function IsamForceExtension(Name, Ext : IsamFileBlockName) :
IsamFileBlockName;
{ Возвращает маршрут с заданным расширением }
procedure IsamGetBlock(var F : IsamFile; Ref, Len : LongInt;
var Destination);
{ Читает байтов из файла начиная с позиции
в }
procedure IsamLongSeek(var F : IsamFile; Ref : LongInt);
{ Устанавливает указатель позиции файла в адрес }
procedure IsamLongSeekEOF(var F : IsamFile);
{ Ищет конец файла }
procedure IsamPutBlock(var F : IsamFile; Ref, Len : LongInt;
var Source);
{ Записывает байтов в файл начиная с позиции
из }
procedure IsamRename(var F : IsamFile; FName : IsamFileBlockName);
{ Переименовывает неоткрытый файл в }
procedure IsamReset(var F : IsamFile; Mode : Byte);
{ Открывает файл в режиме доступа }
procedure IsamRewrite(var F : IsamFile);
{ Создает файл (стирая любой существующий файл с этим именем }
Ниже следуют подробные описания остальных подпрограмм:
AddKey
-----------------------------------------------------------------
Объявление
----------
procedure AddKey(IFBPtr : IsamFileBlockPtr;
Key : Integer;
UserDatRef : LongInt;
UserKey : IsamKeyStr);
Параметры
---------
IFBPtr Указатель файлового блока
Key Номер ключа, как в параметре , передаваемом
в
UserDatRef Номер записи данных, полученный из предыдущего
вызова
UserKey Добавляемый ключ
Описание
--------
После того, как новая запись данных была добавлена при помощи
, индексный файл должен быть также обновлен. Это
выполняется при помощи с номером записи данных,
полученным при вызове . должна вызываться один
раз для каждого ключа.
Отметим, что все ключи должны иметь форму строки символов.
Поставляемый модуль NUMKEYS обеспечивает подпрограммы для
преобразования всех числовых типов Turbo Pascal в форму строки,
поддерживая правильную последовательность сортировки и минимизируя
длину строки. NUMKEYS также обеспечивает функции для упаковки
ASCII-строк, создавая ключи, на 38% короче. Более подробную
информацию см. в разделе 8.F.
Ошибки
------
9900..9906 Ошибки операционной системы
10003 (Только в режиме сохранности). Операция была
абортирована вследствие суровой ошибки ввода/
вывода. Реконструкция файловых блоков не нужна,
поскольку "ремонт" был выполнен успешно.
10178 Параметр "Key" содержит неверный параметр.
10230 Была сделана попытка добавить дублирующийся ключ.
Для первичного ключа это означает, что переданный ключ
уже имеется в индексном файле. Если
переданный ключ был объявлен как вторичный, он
уже существует с тем же относительным номером
записи данных .
Примечания
----------
Теория В-дерева требует уникальных ключей. Если нужно
разрешить возможность дублирующихся ключей, они должны различаться
тем не менее во внутреннем представлении. Для вторичных ключей это
различие достигается за счет объединения с .
(Этот процесс объединения выполняется на логическом уровне и не
требует дополнительной памяти для хранения ключа). всегда
влияет на внутренний последовательный указатель. Следовательно,
и не могут быть вызваны после , пока
последовательный указатель не будер реинициализирован вызовом
, , , , PrevDiffKey>,
или .
AddRec
-----------------------------------------------------------------
Объявление
----------
procedure AddRec(IFBPtr : IsamFileBlockPtr;
var RefNr : LongInt;
var Source);
Параметры
---------
IFBPtr Указатель файлового блока.
RefNr Позиция в файле данных, куда была записана запись
данных (относительный номер записи в файле);
используется для добавления индекса при помощи
.
Source Добавляемая запись данных.
Описание
--------
Запись данных добавляется в файл данных при помощи .
дописывается в конец файла данных, если файл не имеет
удаленных элементов; в противном случае одна из удаленных записей
замещается новой и используется повторно. Будущие
ссылки на эту запись данных выполняются посредством типа
LongInt, возвращаемого . В качестве параметра может быть
передана любая запись, поскольку параметр нетипирован,
однако всегда будет записывать число байтов, заданное при
вызове .
Если первое четырех-байтовое поле записи данных было
зарезервировано в качестве признака удаления, не забывайте
инициализировать его нулем, прежде чем вызвать .
Ошибки
------
9900..9906 Ошибки операционной системы
10001 (Только в режиме сохранности). Операция была
абортирована вследствие суровой ошибки ввода/
вывода. Реконструкция файловых блоков не нужна,
поскольку "ремонт" был выполнен успешно.
ClearKey
-----------------------------------------------------------------
Объявление
----------
procedure ClearKey(IFBPtr : IsamFileBlockPtr; Key : Integer);
Параметры
---------
IFBPtr Указатель файлового блока
Key Номер ключа, как в параметре , передаваемом
в
Описание
--------
сбрасывает последовательный указатель ключа с
номером . Это позволяет возвратить первый
(наименьший) ключ, - последний (наибольший) ключ.
Ошибки
------
10171 Параметр содержит неверный номер.
CloseFileBlock
-----------------------------------------------------------------
Объявление
----------
procedure CloseFileBlock(var IFBPtr : IsamFileBlockPtr);
Параметры
---------
IFBPtr Указатель закрываемого файлового блока.
Описание
--------
Закрывает файловый блок и освобождает память,
выделенную , или
.
Ошибки
------
9900..9906 Ошибка операционной системы.
10080 Файловый блок не был открыт.
10160 Файловый блок не мог быть правильно закрыт.
Примечания
----------
Этот вызов важет с точки зрения сохранения целостности
файлового блока. Если не вызывать, то следующий
раз при запуске программы может понадобиться пересоздание
индексного файла. Это очень важно при тестировании программы: если
программа сбивается, когда файлы открыты и были выполнены
индексные операции, то индексный файл должен быть регенерирован. B
-Tree Filer реализует процедуру выхода Turbo Pascal, которая
автоматически закрывает все открытые файловые блоки при завершении
программы, как нормальном, так и аварийном, с ошибкой времени
выполнения. При "зависании" программы этого не происходит.
Предупреждение: если встречает системную
ошибку, она все же пытается продолжить закрытие файлов. Когда это
нужно и возможно, она записывает в файл данных флаг, указывающий
на то, что индексный файл был запорчен. Поскольку
в случае ошибки продолжае работу, возвращаемое значение
не позволяет сделать вывод о причине ошибки. Память,
выделенная , или
, всегда освобождается.
DatRecordSize
-----------------------------------------------------------------
Объявление
----------
function DatRecordSize(IFBPtr :IsamFileBlockPtr) : LongInt;
Параметры
---------
IFBPtr Указатель файлового блока.
Результат Длина записи данных файлового блока .
Описание
--------
Если запись данных должна быть добавлена при помощи ,
и возвращает ноль, возвращает число
байтов, которое будет записано на диск.
DeleteFileBlock
-----------------------------------------------------------------
Объявление
----------
procedure DeleteFileBlock(FName : IsamFileBlockName);
Параметры
---------
FName Имя DOS, включающее необязательные имена дисковода и
маршрута, но без расширения.
Описание
--------
Удаляет все файлы DOS, принадлежащие файловому блоку с именем
, т.е. все файлы с именем и расширением '.DAT',
'.IX' и '.DIA'.
Ошибки
------
9900..9906 Ошибки операционной системы.
DeleteKey
-----------------------------------------------------------------
Объявление
----------
procedure DeleteKey(IFBPtr : IsamFileBlockPtr;
Key : Integer;
UserDatRef : LongInt;
UserKey : IsamKeyStr);
Параметры
---------
IFBPtr Указатель файлового блока
Key Номер ключа, как в параметре , передаваемом
в
UserDatRef Номер записи данных, позволяющий различать вторичные
ключи. Для вторичного ключа этот параметр должен
быть корректным, а для первичного параметра
он игнорируется.
UserKey Удаляемый ключ
Описание
--------
После того, как запись данных была удалена при помощи
, индексный файл должен быть также обновлен. Это
выполняется при помощи один раз для каждого ключа.
Если ни одного такого ключа не найдено, удаление не происходит.
Ошибки
------
9900..9906 Ошибки операционной системы
10004 (Только в режиме сохранности). Операция была
абортирована вследствие суровой ошибки ввода/
вывода. Реконструкция файловых блоков не нужна,
поскольку "ремонт" был выполнен успешно.
10179 Параметр "Key" содержит неверный параметр.
10220 Была сделана попытка удалить несуществующий ключ.
Для первичного ключа это означает, что переданный ключ
не был найден в индексном файле.
Для вторичного ключа это означает, что ключ не найден в
индексном файле или (даже если ключ существует)
номер записи не относится к этому
ключу.
Примечания
----------
Теория В-дерева требует уникальных ключей. Если нужно
разрешить возможность дублирующихся ключей, они должны различаться
тем не менее во внутреннем представлении. Для вторичных ключей это
различие достигается за счет объединения с .
всегда влияет на внутренний последовательный
указатель, независимо от успешности завершения операции.
Последовательный указатель всегда должен быть реинициализирован,
прежде чем снова можно будет использовать