Indexed Sequential Access Method

Indexed Sequential Access Method (索引付き順次アクセス方式、さくいんつきじゅんじあくせすほうしき、一般にISAM)とは高速にアクセスが可能なデータの格納方法 (ファイル編成法) の一つである。1つ以上のキーによってレコードをシーケンシャルまたはランダムに取得できる。キーフィールドのインデックスは、インデックスファイル内の必要なファイルレコードの高速検索を実現するために維持される。元々はIBMメインフレーム用に開発されたものだが、今日では関係データベース管理システム (RDBMS、関係データベース) をはじめとするほとんど全てのデータベース管理システム (DBMS) でのデータの格納に用いられている。

ISAMという用語は、いくつかの関連する概念で使用される。

  • IBM ISAM製品、およびそれが採用するアルゴリズム[1]
  • アプリケーション開発者がAPIを直接使用してインデックスを検索し、データファイル内のレコードを検索するデータベースシステム。対照的に、関係データベースは、インデックスを自動的に選択するクエリ最適化を使用する[2]
  • データへのシーケンシャルアクセスとキーアクセスの両方を可能にするインデックス付けアルゴリズム[3]。 ほとんどのデータベースは、この目的のためにB木のいくつかの変種を使用するが、元のIBM ISAM実装やVSAM実装では使用していない。
  • 最も一般的には、データベースの任意のインデックス。インデックスは、ほとんどすべてのデータベースで使用される。

概要編集

ISAMを用いたシステムではデータは固定長のレコードとして格納される。元々はキーシーケンスで順番に格納されていた。インデックスと呼ばれるレコードのセカンダリセットには、各レコードの場所へのポインタが含まれているため、全データを検索することなく目的のデータを取り出すことを可能とした。

ISAMの実現は他のデータへのポインタがレコード内に格納されていたナビゲーショナルデータベースからの脱却を実現した。ISAMによる主要な利点は索引のサイズが小さく、高速な検索が可能で、必要なデータのみに直接アクセス可能としたことにある。それに加えてデータの変更が行われた場合にも、該当するデータのみの変更で済ますことが可能であり、関連する他のデータまで波及して変更を加える必要がないことも利点となった。

ISAMファイルが作成されると、インデックスノードは修正され、後で発生する挿入および削除中にそれらのポインタは変更されない(リーフノードのコンテンツのみが後で変更される)。この結果、一部のリーフノードへの挿入がノードの容量を超えると、新しいレコードがオーバーフローチェーンに格納される。テーブルからの削除よりも挿入の数が多い場合、これらのオーバーフローチェーンは徐々に非常に大きくなる可能性があり、これはレコードの取得に必要な時間に影響する[4]

関係データベースはテーブル同士のリンクを正常に維持するロジックが追加されるISAM方式と組み合わせての実装が行いやすい。代表的な例として、外部キーとして使われるフィールドの高速な検索のために索引が用いられる。 これは関連するデータへのポインタをレコードに直接格納する方法よりも遅い処理となるが、データの物理的な構成の変更があった場合でもリンクが正常に保たれるため、ポインタを書き換える必要がない。

ISAMはファイルへの直接の、順番に従ったアクセス方式であり,非常にわかりやすく実装も容易である。逆にISAMの欠点はそれぞれのクライアントマシンがアクセスしているファイルへの自身の接続状態を管理しなければならないことにある。これは一方で複数のデータの追加動作が衝突し、データが矛盾した状態に陥る可能性につながる。一般的にこの問題はクライアントサーバモデルの導入によってサーバがクライアントの要求を直列化して扱うことによって解決されている。これは格納されたデータに対してクライアント側のレイヤーに存在しているデータベース管理システム(DBMS)やSQLトランザクション概念の基礎となっている。

IBMではISAMの代わりにVSAM (Virtual Storage Access Method; 仮想記憶アクセス方式)と呼ばれる技術を用いるようになった。さらにその後、IBMはDB2を開発した。2004年の時点で、IBMはDB2を主要なデータベース管理システムとして推進している。 VSAMは、DB2で使用される物理アクセス方式である[要出典]

OpenVMS編集

OpenVMSオペレーティングシステムは、 Files-11ファイルシステムをRMS(レコード管理サービス)と組み合わせて使用する。 RMSは、アプリケーションとディスク上のファイルの間に追加のレイヤーを提供し、複数の3GLおよび4GL言語間でデータ編成とアクセスの一貫した方法を提供する。 RMSでは、シーケンシャル、相対レコード番号アクセス、レコードファイルアドレスアクセス、インデックス付きアクセスの4つの異なるデータアクセス方法を提供する。

データの読み取りまたは書き込みのインデックス付きアクセス方法は、実際にファイルが適切な事前定義されたキーを持つISAMファイルとして編成されている場合にのみ、望ましい結果を提供する。以前に定義されたキーを介したデータへのアクセスは非常に高速である。複数のキー、重複するキー、およびハッシュテーブル内のキー圧縮がサポートされている。既存のファイルのキーを定義/再定義するユーティリティが提供されている。 「ガベージコレクション」は別のユーティリティを介して行われるが、レコードは削除できる。

設計上の考慮事項編集

ISAMは、コンピュータメモリが不足していた時代に開発された。IBMは、メモリ使用量が最小限になるようシステムを設計した。その反面、入出力チャネル、制御ユニット、ディスクがビジー状態に保たれてしまう。 ISAMファイルは、データレコードのコレクションと2つまたは3つのレベルのインデックスで構成される。トラックインデックスには、インデックスを作成するシリンダー上の各ディスクトラックの最高のキーが含まれる。シリンダーインデックスには、シリンダーの最上位のキーと、対応するトラックインデックスのディスクアドレスが格納される。オプションのマスターインデックスは、通常、大きなファイルにのみ使用され、シリンダーインデックストラックの最上位のキーとそのシリンダーインデックスのディスクアドレスを含む。ファイルがロードされると、データレコードは移動されなくなる。挿入されたレコードは、別のオーバーフロー領域に配置される。キーでレコードを見つけるために、ディスク上のインデックスは複雑な自己書き換えチャネルプログラムによって検索される[5]。 これにより、チャネル、コントロールユニット、およびディスクのビジー時間が増加した。後のシステムで物理メモリと仮想メモリのサイズが大きくなると、これは非効率的であると見なされ、VSAMは、メモリ使用量とディスクアクティビティの間のトレードオフを変更するために開発された。

I/O操作の開始時にCP-67がチャネルプログラム全体を固定メモリにコピーし、仮想アドレスを実アドレスに変換したため、ISAMが自己書き換えチャネルプログラムを使用することで、後でOS/360のCP-67サポートが困難となった[6]

ISAMスタイルの実装編集

関連項目編集

脚注編集

  1. ^ Chin, Y.H. (1975). “Analysis of VSAM's free-space behavior”. VLDB '75: Proceedings of the 1st International Conference on Very Large Data Bases: 514–515. 
  2. ^ Bogue, Robert L. (2004年2月13日). “Explore the differences between ISAM and relational databases”. 2014年10月17日閲覧。
  3. ^ Larson, Per-Åke (1981). “Analysis of index-sequential files with overflow chaining”. ACM Transactions on Database Systems 6 (4). 
  4. ^ Ramakrishnan Raghu, Gehrke Johannes - Database Management Systems, McGraw-Hill Higher Education (2000), 2nd edition (en) page 252
  5. ^ IBM Corporation (1973). DOS/VS LIOCS Volume 3: DAM and ISAM Logic. pp. 63–72. https://archive.org/details/bitsavers_ibm370DOSVIOCSVolume3DAMandISAMLogicRel28Jun73_36886118 2018年12月30日閲覧。 
  6. ^ IBM Corporation (1972). IBM Virtual Machine Facility /370: Planning Guide. p. 45. http://www.bitsavers.org/pdf/ibm/370/VM_370/Release_1/GC20-1801-0_VM370_Planning_Guide_Aug72.pdf 2018年1月8日閲覧。 
  7. ^ Graf. “pblIsamFile Implementation”. mission-base.com. 2017年9月8日閲覧。