Btrieve のアーキテクチャ

Btrieve は、Pervasive Softwareが開発したデータベースです。Btrieveのアーキテクチャは、レコード管理を念頭に置いて設計されています。つまり、Btrieve は、基礎となるレコード作成、データ取得、レコード更新、およびデータ削除の基本機能のみを処理します。MicroKernel Database エンジンとともに、基礎となるストレージ メカニズムとしてISAM (Indexed Sequential Access Method) を使用します。

Btrieve は、本質的には、キーとインデックスを使用してデータを整理するデータベースです。ただし、ファイル構造自体は、主に Btrieve で「ページ」と呼ばれる小さなデータ単位を中心に構築されています。Btrieve のさまざまなバージョンで構造は変更されていますが、ファイル構造は依然として、ページの構成を定義するファイル制御レコード (FCR) と、データを含む Btrieve ファイル内のページを中心に展開されています。歴史的に、Btrieve は「物理ページ」、つまりファイル内の固定位置にあるページを使用していました。バージョン 6.0 以降、ページ割り当てテーブル (PAT) にマップされた「論理ページ」が使用されるようになりました。これにより、Btrieve はレコード更新手法を、後に「プリイメージ ページング」として知られるようになった手法から「シャドウ ページング」と呼ばれる手法に変更することができました。

Btrieve は下位互換性を重視しており、バージョン 6.15 までの Btrieve は標準ファイル形式を使用しており、Btrieve 6.0 がリリースされるまでは完全に下位互換性がありました。Btrieve 6.0 では新機能が導入され、より高度な機能を実装するために旧バージョンとの互換性を壊す必要がありました。APIも同様に下位互換性が維持され、削除されたのは 1 つの機能 (ファイルを別のメディアに分割する機能) のみです。ある時点で、Btrieve の元CEO であるRon Harris は、「バージョン 1.0 の API はバージョン 6.15 でも引き続きサポートされており、今後もずっと維持していきます!」と発言しました^{[1] : 11}。

Pervasive は当初、Btrieve を説明するのに「ナビゲーション データベース」という用語を使用していましたが、後にこれを「トランザクション データベース」に変更しました。ナビゲーション データベースという用語の使用は珍しいものでした。ナビゲーションデータベースは「ポインタ」と「パス」を使用してデータレコード間を移動し、これらのポインタはレコード自体に含まれているからです。Btrieve の基本構造である ISAM は、検索時間を短縮するために、これらのポインタを格納するためにセカンダリ インデックス テーブルを使用します。したがって、2 つのデータベースの種類は異なり、Pervasive がデータベースを分類するために異なる用語を使用し始めた理由を説明するかどうかはわかりません。^[a]

バージョン 6.15 以降、Pervasive は、データベースバックエンドを開発者が使用するインターフェイスから分離する新しいモジュール方式を採用しました。コア データベース操作 (レコードの更新、書き込み、削除など) を Btrieve および Scalable SQL モジュールから分離しました。Micro-Kernel Database Engine (MKDE) を他の機能から分離することで、プログラマーはデータベースに同時に複数の方法でアクセスできるようになりました。たとえば、Btrieve API を使用してアプリケーションを作成し、同じデータにアクセスする必要がある別のアプリケーションでは、Scalable SQL を使用するなど、まったく異なる方法を使用する場合があります。レコードプリミティブがこれらの方法から分離されているため、両方のアプリケーションが MKDE を使用して同じデータファイルにアクセスできます。

Micro-Kernel Database Engine は、マイクロカーネルオペレーティング システム カーネルとは無関係です。

Btrieve ファイル形式は、エンジンがI/O操作を実行するときにメモリとストレージ メディア間で移動するデータであるページのみで構成されています。バージョン 6.0 より前では、データ ページ、インデックス ページ、およびファイル制御レコード(FCR) のみが使用されていました。ファイルには、物理​​ページにリンクされた検索用のインデックスがありました。バージョン 6.0 以降では、一連のページ割り当てテーブル (PAT) を使用してディスク上の物理ページ(ファイル内の固定位置にあるページ)にマップされる論理ページが使用されるようになりました。

ファイル制御レコード (FCR) には、Btrieve データベース ファイルに関する重要な情報が含まれています。ページ サイズ、現在使用中のページ数、ファイルのインデックスを作成できるキーの数、ファイル内のレコード数、およびその他の詳細が保持されます。バージョン 6.0 以降では、冗長性のために 2 つの FCR が使用されるようになりました。各 FCR に存在する 32 ビットの使用カウント フィールドは、どの FCR が有効であるかを判断するために使用されます。ファイルに対して操作が実行されるたびに、フィールドが増分されます。使用カウントが最も高い FCR が有効な FCR になります。FCR については、Jim Kyle のソース サンプルで詳しく説明されています。MKDE バージョン 8 の導入により、FCR ページの構造が変更されました。ページ サイズは FCR 内で移動され、通常の 32 ビット フィールドではなくなりました。バージョン 8 以降では、オフセット 0x2A の 32 ビット フィールドを取得して 256 を掛けてページ サイズを計算する必要があります。

ページ割り当てテーブル( PAT) は、論理ページを物理ページにマップします。各 PAT は、明確に定義された場所にある物理ページです。FCR と同様に、PAT は常にペアで発生し、現在有効なコピーは使用回数が多いことで示されます。最初の PAT ペアは最初の 2 つの FCR の直後に続き、物理ページ 2 と 3 を占めます。その後に可変数の他のページが続き、次に新しい PAT ペアが続きます。各 PAT には、論理ページへの固定数のポインターがあり、空の各エントリの値は 0 です。

PAT に格納できる論理レコードの量は、そのページ サイズによって決まります。MKDE バージョン 6.x および 7.x の各ページ ポインターは 4 バイトのスペースを占有し、PAT ヘッダーは 8 バイトを占有するため、PAT 内の論理ページ数は次のようになります。

論理ページ数= (ページサイズ÷ 4) - 8

MKDE バージョン 8 の導入により、ページ ヘッダーのサイズが変更されたため、この式は適用されなくなりましたが、原則は同じままです。

バージョン 6.0 までは、レコードの更新を実行するときにプリイメージ ページングが使用されていました。変更が行われる前に新しい「プリイメージ ファイル」が作成され、元のデータ ファイルのページがこの新しいプリイメージ ファイルに一時的にコピーされます。その後、システムは元のファイルに変更を加えます。更新が中断され、ページに書き込まれたデータの半分だけが残っている場合は、エンジンによってページがロールバックされ、プリイメージ ファイルのページが元のデータベース ファイルの破損したページにコピーされ、一時的なプリイメージ ファイルが削除されます。プリイメージ ファイルには .PRE という拡張子が付けられていたため、システム内でこれらのファイルが見つかった場合、通常はトランザクションが正しく行われず、回復が成功しなかったことを意味します。

バージョン 6.0 以降、プリイメージングの代わりにシャドウ ページングが使用され、現在でも使用されています。ページを一時ファイルにコピーする代わりに、データベース ファイル内の次の予備の物理位置が検索され、その位置にページが書き込まれました。このページは、ファイルの PAT に位置がまだ書き込まれていないため、シャドウ ページと呼ばれます。シャドウ ページの更新が完了すると、PAT が更新され、ファイル内の次の使用可能な現在の物理ページのエントリが PAT に記録されます。ただし、シャドウ ページの更新中にシステム障害が発生すると、PAT は更新されず、現在の次のエントリが PAT で更新されないため、変更は破棄されます。

プリイメージ ページングからシャドウ ページングへの変更により、ファイル形式が大幅に変更され、Btrieve の以前のバージョンと製品バージョン 6.x 間の互換性が失われました。

オルタネート コレーティング シーケンス(ACS) ページは、レコードを異なる順序で並べ替えることができるページです。照合とは、書き込まれた情報を標準の順序にまとめることです。一般的には、これはアルファベット順と呼ばれますが、照合はアルファベットの文字の順序付けに限定されません。たとえば、ACS では、大文字と小文字を区別する順序と区別しない順序の両方で並べ替えることができます。バージョン 6.0 より前は、ファイルに保存できる ACS は 1 つだけでした。しかし、バージョン 6.0 がリリースされた後は、一度に複数の ACS ページをファイルに関連付けることができるようになりました。

バージョン 6.0 以降のファイルでは、実際に使用されているページ数よりも多くの物理ページが存在する場合があります。これは、シャドウ ページングにより、システム内の一部のページに PAT のエントリがない可能性があるためです。これらのページは「追加」ページとしてマークされ、新しいページ用のスペースが割り当てられる前に使い切られます。

Btrieve では、各ページは固定されていますが、レコードはページ サイズよりも大きくなることがあります。つまり、レコードは断片化されて、多くの異なるページに分散される必要があることがよくあります。レコードが非常に大きい場合、レコードを格納するために何百ページも使用する必要がある可能性があります。リンク リスト アプローチでは、この断片化を許容できますが、Btrieve エンジンでは、連続したレコードを読み取るのが困難です。そのため、バージョン 6.1 以降では、データ レコードを構成する各ページへのポインタを格納するテーブルがファイル内で使用されるようになりました。このテーブルは、可変長アロケーション テーブル(VAT) と呼ばれます。

Btrieve は、特定のテーブル列のレコード インデックスを格納するためにb-tree形式を使用します。インデックスは、インデックスが付けられた列の値の各セットを、それらの列の値を持つ行の一意の識別子のセットにマップします。これにより、インデックスが付けられた列を使用してテーブル内の行をすばやく見つけることができます。B-tree はツリー データ構造であり、高速データ取得のメカニズムとして非常に効率的です。b-tree の欠点は、ツリーに挿入されるときにデータのバランスを常に保たなければならないことです。そのため、Btrieve はレコード インデックスを b-tree としてのみ格納し、レコードの挿入と更新にかかる時間を短縮します。システムではインデックスごとに個別の b-tree が保持され、ルート ノード情報は FCR に保持されます。Btrieve 6.x では、ファイルの作成時に新しいインデックスを作成したり、ファイルの作成後に追加したり削除したりできます。インデックス ページも必要に応じて作成されます。Btrieve 6.0 より前では、既存のキー インデックスを削除することはできませんでしたが、必要に応じて補足インデックスを作成したり削除したりできました。

Btrieve では、インデックス内の重複キー値が許可されます。Btrieve は、リンクされた重複メソッドまたは繰り返し重複メソッド (この用語はバージョン 6.0 がリリースされたときに使用され始めました) を使用して重複キーを処理します。リンクされた重複メソッドでは、インデックス ページ自体のレコード ポインターのペアを使用して、重複キーの二重リンク リストの先頭と末尾を指します。つまり、リスト内の重複キーの順序は、入力された順序になります。重複キー メソッドでは、リンクされたリストは使用されず、新しいインデックス キーを作成し、レコード ポインターのアドレスをキーの末尾に追加することで、すべてのキーが一意になります。つまり、キーは位置順序によって取得されます。

Btrieve がレコードにアクセスするためにファイル共有を行う必要がある場合、シングル エンジン ファイル共有(SEFS) モードとマルチ エンジン ファイル共有(MEFS) モードの 2 種類のファイル共有モードを使用できます。SEFS では、そのエンジンにアクセスするクライアントのみがデータベースを変更でき、別のエンジンにアクセスする他のクライアントはデータベースにアクセスできません。MEFS では、異なるエンジンで実行されている異なるクライアントがデータベースにアクセスできます。

Btrieve は、6.x シリーズでは同時トランザクションを処理できました。Btrieve 6.0 より前のエンジンでは、ファイル レベルのロックまたは排他ロックしか実行できませんでしたが、6.0 以降では、レコードを個別にロックできるようになりました。レコード (またはページ) レベルのロックは、同時ロックと呼ばれていました。利点は明らかです。複数のクライアントが同じレコードにアクセスしようとしない限り、同時にファイルにアクセスできるため、パフォーマンスが向上します。さらに、他のクライアントはロックされたページを読み取ることができ、レコードをロックした別のプロセスによる書き込みトランザクションに関係するファイルへの変更は認識されません。

MEFS モードでは、同時ロックは完全にはサポートされていませんでした。クライアントが同時トランザクションを開始し、レコードへの書き込み操作を実行しようとすると、同時ロックが使用されていたにもかかわらず、Btrieve エンジンはファイルがロックされていることを示すステータス コード 85 を返します。

Btrieve バージョン 6.15 以降、システム トランザクションと呼ばれる新しいタイプのデータベース トランザクションが導入されました。これは、ユーザー トランザクションとは分離されています。ユーザー トランザクションは排他的かつ同時実行可能なトランザクションですが、システム トランザクションは非トランザクション操作および/またはユーザー トランザクションのバンドルです。システム トランザクションは、MKDE によるデータ回復にのみ使用されていました。システム障害によってデータが破損した場合、MKDE を再起動すると、システム トランザクションが失敗したすべてのファイルを検出し、回復を試みます。ただし、最後のシステム トランザクションがロールバックされたときにユーザー トランザクションが失われている可能性があるため、エンジンが「操作の終了」要求を受け取ったときに、MKDE がユーザー トランザクションを含むシステム トランザクションを強制的に完了するようにするオプションを設定できます。