JPH0628231A - コンピュータシステム内にエントリするデータベースを記憶し且つ維持する方法及びデータベース管理システム - Google Patents

コンピュータシステム内にエントリするデータベースを記憶し且つ維持する方法及びデータベース管理システム

Info

Publication number
JPH0628231A
JPH0628231A JP4167824A JP16782492A JPH0628231A JP H0628231 A JPH0628231 A JP H0628231A JP 4167824 A JP4167824 A JP 4167824A JP 16782492 A JP16782492 A JP 16782492A JP H0628231 A JPH0628231 A JP H0628231A
Authority
JP
Japan
Prior art keywords
data structure
indexed
tree data
pointer
database
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP4167824A
Other languages
English (en)
Other versions
JP2515950B2 (ja
Inventor
Edward C Cheng
チ−マン チェン エドワード
Dieter Gawlick
ゴーリック ダイエター
Patrick E O'neil
イー オニール パトリック
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Digital Equipment Corp
Original Assignee
Digital Equipment Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Digital Equipment Corp filed Critical Digital Equipment Corp
Publication of JPH0628231A publication Critical patent/JPH0628231A/ja
Application granted granted Critical
Publication of JP2515950B2 publication Critical patent/JP2515950B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9027—Trees
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99941—Database schema or data structure
    • Y10S707/99943—Generating database or data structure, e.g. via user interface

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【目的】 主メモリと補助メモリとを効率よく使用でき
るようにする。 【構成】 データベース指標ファイルを主ランダムアク
セスメモリと補助メモリとを有するコンピュータにより
維持する。データベースに付加する各項目に対する記録
は補助メモリ内の順次編成ファイル内に記憶し新規記録
への指標付ポインタは主メモリ内の小Ｂトリー内に記憶
する。データベースに対する全指標ファイルは補助メモ
リ内の第２の大Ｂトリーである。全指標ファイルの葉ノ
ードは指標付順序で記憶する。周期的に、メモリ常駐小
Ｂトリーの一部分を、指標値の選択範囲内の全部の指標
付ポインタを補助メモリから検索することにより、大Ｂ
トリーの相当する部分と組み合わせる。指標値の選択範
囲内の第１Ｂトリー内の指標付ポインタを検索記録内へ
組合わせ、指標付ポインタの結果としての組合せ集合を
補助メモリの隣接する範囲内に指標付順序で補助メモリ
内に記憶する。新付加データベース記録に対する指標付
ポインタをバッチで補助メモリ内へ書き込む。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は一般的に大きいデータベ
ースを記憶するためのデータベース管理システムに関す
るものであり、且つ特に高いデータ挿入周波数により大
きいデータベースを記憶する場合に、主記憶装置と補助
記憶装置との効率的な使用をさせる方法とシステムとに
関するものである。
【０００２】
【本発明の背景技術】コンピュータシステムにより実行
される全部のトランザクションの累積のジャーナル（し
ばしばログファイルと呼ばれる）を維持するマルチユー
ザコンピュータシステムを考えよう。典型的には、各ロ
グエントリがそのトランザクションを識別し、そのトラ
ンザクションが計算されるか又はアボートされるかのい
ずれかを指示し、且つ他の関連するデータを含んでい
る。時間を越えて、非常に多数のそのようなログエント
リが累積し、且つこれらのエントリが順アクセスディス
クファイル内に記憶される。永続するトランザクション
と大きく且つ連続するトランザクションの負荷とを有す
るコンピュータシステムを取り扱う複雑なトランザクシ
ョンにおいて、ログ記録は高周波数でファイル内へログ
記録の挿入を要求しながら、非常な高速度で作り出され
る。
【０００３】少なくとも幾つかの状態では、一つ以上の
指標付値によるログ記録への遅れたアクセスが望まし
い。例えば、幾つかのシステムユーザが十分な周波数に
より、そのファイルがこのデータへの効果的なアクセス
を可能にするために指標付参照符号を用いて、指定され
たデータベース管理システム（DBMS; database manage-
ment system)内に記憶されることを必要とするような歴
史的記録をアクセスできる。
【０００４】多くのトランザクション操作コンピュータ
システムにおいて、ロギングがシステム障害からの回復
を装うことに集中されてきて、従って事象の比較的短い
期間の履歴を参照し帰すことができるようなシステムを
必要としてきた。しかしながら、システム負荷は成長し
続け、且つトランザクションシステムは、もっと複雑な
アクティビティに対する応答性を取るから、アクティビ
ティ記録（事象ロギング）に対する要求は単純な回復ロ
ギングから長期間アクティデヒィ流れ管理補助やシステ
ムモニタリング、気密保護、その他へ偏移する。この偏
移によって、単一の永続性トランザクションを作り上げ
る事象の期間と数とが、所定の時間に取り上げられるス
テップを見直す、人の代行者に対する頻繁な要求が存在
する点まで増大する。同時に、システムには既知の活動
中の事象の全数が、今活動中の事象のトラックを維持す
るために用いられているメモリ常駐データ構造がもはや
利用できない点まで増大する。
【０００５】マルチユーザ銀行業務システム例 １秒当たり100 トランザクションを実行するマルチユー
ザ銀行業務システムを一例として考えよう。各トランザ
クションが幾つかの異なる表の一つから無作為に選択さ
れた列内のある行値を更新する。三つの一次表を有する
システムを用いて、それらの表のうちの二つは主記憶装
置内に維持されるために十分に小さく、且つそれらの表
のうちの一つは補助記憶装置内に維持される場合には、
トランザクションが、平均して、二つの入出力動作を必
要とし、１秒当たり全部で200 ディスク入出力動作を必
要とする。ディスク記憶装置の各ディスクアームが１秒
当たり25入出力動作以上は取り扱えない場合には、８デ
ィスクアームがこのレベルのトランザクションアクティ
ビティを取り扱うために必要となるであろう。
【０００６】なんらかの数のキー；過去のトランザクシ
ョンについての会計ホルダよる質問に解答するためのタ
イムスタンプと連結された会計識別子；現金引き出し不
平衡を解決することを容易にするためのタイムスタンプ
と連結されたテラー識別子、その他；によるログ記録の
指標を付けられた検索に対する使用が、誰でも容易に想
像できる。そのような指標に対する挿入の期間は非常に
長くなり得る。
【０００７】標準多方向探索樹 (B-tree; 以下Ｂトリー
と略称する）指標付ファイルを用いて、一箇月を越える
期間の長い記録について会計−ＩＤ−タイムスタンプ指
標を維持することを必要とする付加される資源を考えよ
う。Ｂトリー指標について馴染みがない読者に対して
は、これらの種類の指標は従来技術において周知である
こと、及び以下に少し詳細に説明することに注目された
い。さし当たり、標準Ｂトリー指標の使用の唯一の重要
性は、各連続する記録に対するログ記録の指標の位置が
無作為であることであり−それがそのファイル内のいか
なる位置にあってもよいことを意味する。100 個の新し
いログ指標エントリが会計−ＩＤ−タイムスタンプ指標
に対して１秒当たりに発生し、１日当たり８時間、１月
当たり20労働日である。かくして、１月当たりでは約5
7,600,000個の新しいエントリが発生する。それに加え
て、各指標エントリは少なくとも10バイトを必要とし、
１ギガバイトの記憶空間の約半分を占有する指標テーブ
ルとなる。明らかに、ほとんどの指標テーブルはメモリ
常駐ではない。各新挿入ログ記録の位置は無作為である
から、各トランザクションに対するログ記録を挿入する
ためには、１頁読取と１頁書込との平均が典型的に必要
であろう。かくして、この種の各指標は１秒当たり約20
0 ディスク入出力動作、すなわち付加的な８ディスクア
ームを加える。
【０００８】長さが20日のみに対してログ指標を維持す
ることを要求される削除動作は、ピークでない使用時間
の間に多分実行され得る。さもなければ、そのような削
除動作はそのシステムの負荷へ、１秒当たり約別の200
ディスク入出力動作を付加するであろう。
【０００９】二つ又は三つのそのようなトランザクショ
ンログ指標が維持される場合には、トランザクションの
流れを取り扱うために必要なディスク記憶装置の数は、
銀行の基本的機能記録を維持するために必要なディスク
記憶装置の数を越えるであろう。
【００１０】本発明は高周波数データ挿入に関連する上
述のディスク入出力ボトルネックを克服する。非常に少
ないディスクアーム使用による、それ故に非常に低い費
用による大きいデータベースの指標内への高周波数挿入
を実行することを、本発明がコンピュータシステムにで
きるようにする。特に、本発明は指標変化を延ばし、且
つ指標がディスク上へ記憶される順序と整合する予定さ
れた順序でバッチで記憶されたログ指標へのそのような
更新を取り扱う。結果として、ディスク装置に課せられ
る負荷は非常に低減される。
【００１１】また、そのような指標を維持するアクティ
ビティは主データベースとデータベース管理システムプ
ログラムとから個別のプロセッサ及び個別のディスク上
で実行され得る。結果として、高い挿入速度データベー
スに対する指標を維持する処理が、新しく挿入される記
録を確実に且つ早急に記憶している主データベース管理
システムアクティビティの実行を傷つけない。
【００１２】
【本発明の概要】本発明の広い形態においては、本発明
は主ランダムアクセス記憶装置と補助記憶装置とを有す
るコンピュータシステム内にエントリするデータベース
を記憶し且つ維持する方法であり、前記コンピュータシ
ステムにより実行される方法のステップは、要求に際し
て、データベースファイル内に新しい記録を記憶するス
テップ、主記憶装置内に記憶されている第１トリーデー
タ構造内へ前記新しい記録への指標付ポインタを記憶す
るステップ、補助記憶装置内に第２トリーデータ構造を
記憶し、前記第２トリーデータ構造は指標付ポインタが
前記第１トリーデータ構造内に記憶される記録以外の全
部の前記データベースファイル内の記録への指標付ポイ
ンタを含んでおり、そこで前記第２トリーデータ構造内
の前記指標付ポインタは前記補助記憶装置内に予定され
た順序で記憶されるステップ、前記第１トリーデータ構
造の一部を前記第２トリーデータ構造内へ、(1A)前記第
１トリーデータ構造内の指標付ポインタの一部を選択
し、(1B)前記第２トリーデータ構造内の前記指標付ポイ
ンタの相当する一部を前記補助記憶装置から検索し、(1
C)前記第１トリーデータ構造内の指標付ポインタの前記
選択された部分を前記第２トリーデータ構造から検索さ
れた前記指標付ポインタへ組み合わせ、(1D)前記予定さ
れた順序で前記補助記憶装置内へこの組み合わされた指
標ポインタを記憶して、且つ(1E)前記第２トリーデータ
構造からの指標付ポインタと組み合わされた指標付ポイ
ンタを前記第１トリーデータ構造から除去することによ
り、周期的に組み合わせるステップ、を具えており、そ
れにより付加されたデータベース記録に対する指標付ポ
インタはバッチで補助記憶装置へ書き込まれ、それによ
って前記補助記憶装置を効率よくアクセスする。
【００１３】ここに記載した好適な一実施例は、主ラン
ダムアクセス記憶装置と補助記憶装置とを有するコンピ
ュータシステムにより維持されるファイルによって、非
常に高い挿入速度によるデータベースの低費用指標付け
を許容するデータベース指標付け技法を提供する。その
データベースへ付加される各項目に対する記録は、補助
記憶装置（ディスク記憶装置）内の順次編成ファイル内
へ記憶され、新しい記録への指標付ポインタは主ランダ
ムアクセス記憶装置内へ記憶された小Ｂトリー内へ記憶
さる。そのデータベースに対する全指標ファイルは、第
２の、補助記憶装置内の大Ｂトリーである。この全指標
ファイルの葉ノードはパックされて、指標を付けられた
順序で記憶される。
【００１４】周期的に、メモリ常駐小Ｂトリーの一部分
が指標値の範囲を選択し且つ指標値のこの選択された範
囲内の全部の指標付ポインタを補助記憶装置から検索す
ることにより、大Ｂトリーの相当する部分と組み合わさ
れる。指標値のその選択された範囲内の第１Ｂトリー内
の指標付ポインタは検索された記録へ組み合わされ、指
標付ポインタのこの結果の組み合わせ集合は大Ｂトリー
の末尾において補助記憶装置の隣接する領域内に、指標
を付けられた順序で補助記憶装置内へ記憶される。結果
として、新しく付加されたデータベース記録に対する指
標付ポインタはバッチで補助記憶装置へ書き込まれ、そ
れにより補助記憶装置を非常に効果的にアクセスする。
【００１５】
【実施例】本発明のもっと詳細な理解は、添付の図面と
一緒に理解されるべき好適な典型的実施例の以下の説明
から得ることができる。
【００１６】図１を参照して、システムバス104 によ
り、補助記憶装置106(例えば磁気ディスク記憶デバイ
ス）、主記憶装置108(すなわち、高速の、ランダムアク
セス記憶装置）、仮想記憶装置110 、及びユーザインタ
フェース112 へ相互接続された中央処理ユニット102 を
有するコンピュータシステム100 が示されている。この
コンピュータシステム100 は、ネットワークインタフェ
ース120 によりこのコンピュータシステム100 へ接続さ
れている構内通信網又は広域ネットワークバス118によ
り、多数の他のコンピュータ114, 126と典型的に相互接
続されている。
【００１７】本発明は単一のコンピュータ100 によって
使用され得るけれども、もっと典型的には本発明は銀
行、航空会社及びその他広域分散形業務により使用され
るような、分散形計算システムに使用されるであろう。
多数の場所においてコンピュータはトランザクションに
関与し、且つこれらのトランザクションを実行する応用
プログラムが多くのデータを発生し、それらのトランザ
クションの内容、進行及び状態を記録する。この文脈に
おいて、システム100 はそれの仕事が全部の事象メッセ
ージを受信し、指標付けし且つ記憶することである分散
形計算システムにおけるノードとして見ることができ
る。
【００１８】補助記憶装置106 は典型的に「ディスクフ
ァーム」を含んでおり、そのディスクファームはデータ
とプログラムとを記憶するために使用されるディスク記
憶デバイス 122〜126 の集合体である。あらゆる単一の
一つのデバイスの制限されたデータ取扱能力の故、及び
記憶されるべきデータの大量の故に、複合ディスク記憶
デバイスがしばしば用いられる。あらゆる場合に、本発
明においては、逐次編成データファイル130 を記憶する
ために補助記憶装置106 が使用され、その逐次編成デー
タファイルがデータ記録が記憶される主データベースフ
ァイルである。補助記憶装置106 は「主指標」ファイル
132 を記憶するためにも用いられて、その「主指標」フ
ァイルはデータファイル130 へのキー付指標である。あ
らゆる普通のデータベース管理システムにおけると同様
に多い、データファイル130 内の記録をアクセスするた
めに、この指標は用いられる。例えば、代理人識別子
（これはメッセージを発生したユーザ又は計算代理人を
識別する）とタイムスタンプ（これはそのメッセージが
発生された時間を識別する）との連結であるキーを用い
てデータ記録は指標を付けられ得る。複数指標が必要な
場合には、個別の指標ファイル132 が各指標に対して発
生されるであろう。
【００１９】オペレーティングシステムソフトウエア14
4 、アクティビティを記録するデータベース管理プログ
ラム146 、及び目的は以下に説明される一時的指標148
と同時に、現在実行する応用プログラム142 が主記憶装
置108 内に記憶されている。ディスク入出力のための緩
衝記憶装置のような、このシステムに使用されるその他
のデータ構造も、主記憶装置内に置かれている。このデ
ータベース管理プログラム146 は、分散トランザクショ
ン処理システムを通じての適用業務により発生されたア
クティビティ記録（しばしばログメッセージと呼ばれ
る）を全部受信して、それらを逐次編成データファイル
130 内に記憶する。データベース管理プログラムは、コ
ンピュータシステム管理プログラムにより設定された指
標の数に依存して、各データ記録エントリに対する１個
以上の指標ポインタを発生し且つ記憶する。
【００２０】Ｂトリーデータ構造 データベース管理システム(database management syste
m; DBMS)は、データベース内に記憶された記録を早急に
アクセスするために、「Ｂトリー」と呼ばれるデータ構
造をしばしば使用する。そのようなデータ構造はこの技
術に熟達した人々には周知であるが、データベース管理
システム指標のために使用されるデータ構造にを熟知し
ていない読者のために、Ｂトリーデータ構造の短い概要
を次に与える。
【００２１】「Ｂトリー」なる語は文字通り「平衡した
木（トリー）」を表している。Ｂトリー指標は古典的な
２進トリーではなく、むしろ各葉でないノードがＮ個の
子供を有するＮ進トリーである。図２を参照して、我々
はほとんどあらゆるデータベース管理システムにおいて
見出されるＢトリーと類似する普通のＢトリーデータ構
造200 を示す。このトリーの頂点は根ノード202 であ
る。このトリーの底部には葉ノード206, 208がある。根
ノード202 と葉ノードとの間には中間ノード 210〜220
がある。根ノードと中間ノードとは集合的に「葉でない
ノード」と呼ばれる。
【００２２】この例においては、根ノード202 は100 個
のキー値 204-001〜204-100 を含んでいる。キー値は記
録の集合を指標付けするために用いられる値であり、且
つ典型的にはその記録を識別するために用いられる記録
内の１個以上のフィールドである。例えば、データベー
ス内の記録が次のように見える場合には、
【表１】 代理人 タイム 動作１ 動作２ パラメータ１ 001 000C10 "DUMP" "ABORT" 5444 FF6 88F11D "YES" "COMMIT" 1011 … データベースは３個の16進数字代理人フィールドをタイ
ムフィールドと連結することによりキーを付けられ得
て、上記の第１記録に対しては001-000C10のキー値とな
り、上記の第２記録に対してはFF6-88F11Dとなる。これ
らのキー値内に示されたハイフン「−」は記憶された値
には含まれておらず、ここでは単に読みやすさのために
示されていることは注意されたい。
【００２３】このトリーの葉でないノード内の各々の指
標値204 はポインタ値PTR を伴っており、そのポインタ
値がこのトリーの次に低いレベル内のもう一つのノード
（例えばノード210)を示す。各葉でないノードに記憶さ
れたキー値がそのノードより下のトリーの部分をほぼ等
しい片に分割するキー値の「間隔」を指示する。
【００２４】Ｂトリー200 の目的は記憶された順序で記
録の指標を維持するためである。我々のデータベースが
各々が独特のキー値を有する9,000,000 記録を含んでい
ると想定しよう。根ノード202 はこれらの記録を、言う
ならば、100 個のほぼ等しい大きさのグループに分割す
る。言い換えれば、根内のキー値がキー１〜キー100の
ラベルを付けられた場合、キー１とキー２との間のキー
値を有する記録の数はキー２とキー３との間のキー値を
有する記録の数とほぼ同じであり、以下同様である。
【００２５】根ノード内に作表されたキー値は増大する
順序で（減少する順序も使用され得るけれども）作表さ
れる。根内のキーＮとキーＮ＋１との値の間のキー値を
有する全部の記録が、キーＮに相当するトリーの第２レ
ベル内のノードを参照することにより見出される。かく
して001-022111（これは根ノード202 内の最初の二つの
キー値の間である）のキー値を有する記録が第２レベル
ノード210 をアクセスことにより見出され、その第２レ
ベルノードは根内の第１キーに相当し、且つその時特定
された記録への葉ノード内のポインタを見出すためにそ
の第２レベルノード210 内のエントリを用いる。
【００２６】このトリー200 の第２レベル及び第３レベ
ルにおける葉でないノードは、根ノードと構造が同じで
あり、100 個のほぼ等しい大きさにされた部分集合にそ
のデータベースのそれらの部分を各々分割する。各ノー
ドはエントリの予定された最小数と最大数とを有する。
例えば、ノードは最小７エントリ及び最大100 エントリ
を各々が有することを許容され得る。かくして、この例
においては、トリーの第２レベルにおいては100 ノード
だけであり、トリーの第３レベル220 においては10,000
ノードだけであり得る。このトリーの第３レベルにおけ
るノード220 は百万葉ノード 206〜208 だけを示す。
【００２７】この例での葉ノード206 は各々、逐次編成
データファイル130 内の100 データ記録までを表現す
る、100 データ対までを含んでいる。各データ対は逐次
編成データファイル130 内の記録へのキー値とポインタ
とを具えている。このポインタ値はディスクアドレス値
と等価であるが、典型的には記録の位置を指示する中間
ポインタである。
【００２８】この文書の目的に対して、「指標付ポイン
タ」は、ポインタ値と対にされた指標値、又は情報のあ
らゆる等価データ構造又はユニットを具えている値の対
を意味すると定義される。
【００２９】各トリーノード内に記憶された100 個のデ
ータ値を有する図４に示した４レベルトリーを用いて、
１億記録までに対する指標を記憶することができる。１
億記録以上の記録が指標付けされねばならぬ場合には、
ノードの大きさが増大され得る（例えば、ノードの大き
さを二倍にすることにより、４レベルトリーの容量は16
億記録に増大する）か、又はトリー200 が５レベルトリ
ーに拡張され、その拡張が100 億記録まで取り扱えるよ
うにするかのいずれかである。
【００３０】真実のシステムのノード内に記憶されるキ
ー値の実際の数は、システムのメモリページサイズ（各
ノードが典型的にディスクメモリの１ページを占有す
る）、各キー値により占有されるバイトの数、及び指標
付けされているデータベースの予言された最大寸法のよ
うな要素に依存することは注意されるべきである。
【００３１】図２のトリー200 から項目を付加し及び削
除するための手順は、この技術に熟達した人々には周知
である。基本的に、新しいエントリを挿入するための正
しい場所はトリーを追跡し、正しい葉ノードが見出され
るまで、新しいエントリに相当するキー値範囲を有する
ノードを追跡することにより決定される。葉ノードが新
しいエントリのための空間を有する場合には、新しいエ
ントリは単純にその葉ノードへ加えられる。葉ノードが
一杯である場合には、新しいエントリに対する空間を作
り出すために存在する葉ノードに沿ってエントリが偏移
されるか、又は新しい葉ノードが作り出されてもよい。
必要な場合には、相当する親ノード内に記憶されたキー
値間隔が、トリーノードの内容へのトラックを維持する
ために調整される。
【００３２】エントリの削除は率直である。エントリは
そのエントリの葉ノードから削除される。各ノードに対
するエントリの最小許容数が存在するので、削除はこの
トリー内のノードの数を収縮させ得る。
【００３３】上述のように、図２に使用された指標値と
ノード寸法とは、Ｂトリーデータ構造を説明する目的の
ためにのみ設計されたものである。千人のテラーと自動
テラーマシンを有する銀行に対するような、実際の応用
においては、指標値は典型的に少なくとも10バイト長さ
（例えば、代理人識別に対して４バイト、及びタイムス
タンプ値に対して６バイト）であり、且つ葉ノード及び
葉でないノードの両方におけるポインタは各々多分４バ
イト長さ（32ビットアドレスを与えるために）である。
かくして100 エントリを有する各葉はメモリ記憶装置の
約1400バイトを占有する。
【００３４】小Ｂトリーと大Ｂトリー 本発明の背景で上述のように、図２に示したＢトリーデ
ータ構造200 についての問題点は、非常に高レベルのデ
ータ挿入を有するシステムにおいては、大きい指標ファ
イルがＢトリー200 を通して無作為に分散された位置へ
の多数の読取及び書込動作によって、極端に多数のディ
スク記憶デバイスを必要とし得ることである。更にその
上、主ランダムアクセス記憶装置108 内に全部の指標を
記憶することは実際的でない。例えば、６千万記録を記
憶し且つ14バイトの記憶装置を必要とする指標付ポイン
タを使用するシステムにおいて、指標ファイルの葉ノー
ドは840 メガバイトの記憶装置を必要とするであろう
し、それは主記憶装置内に記憶するためには費用がかか
り過ぎる。
【００３５】指標ファイルＢトリーの葉でないノード
は、葉ノードのための記憶空間の約１％を典型的に使用
するのみである。それ故に（約2.1 メガバイトの記憶装
置を必要とする）主記憶装置内に葉でないポインタの、
言うならば10％、あるいは25％でさえものコピーを維持
するのが非常に実際的である。
【００３６】図３及び図４を参照して、データベース管
理プログラム146 は次のように動作する。いつでも新し
いデータ記録が受信された場合には、その新しいデータ
記録は、逐次編成データファイル130 内に、補助記憶装
置内に記憶される（ステップ300)。新しい記録が、それ
らの指標値に関係なく、時間の順序でそのファイルの終
端へ常に書き込まれるから、これは「逐次編成」データ
ファイルと呼ばれている。幾つかのシステムにおいて
は、少数のそのような記録が、そのような記録の１全ペ
ージ又は幾つかの全ページがすでに記憶されてしまうま
で、又はトランザクションがそこへ関係する全部の記録
が安全に記憶される要求を「コミット」するまで、緩衝
記憶装置250 内へ一時的に記憶されてもよい。
【００３７】幾つかの記録が補助記憶装置ファイル130
内に記憶された後に、これらの記録のブロックが読み取
られ、且つ相当する指標付ポインタが作り出され且つ一
時的に、ここでは小Ｂトリー(SBT)148と呼ばれる指標フ
ァイル148 内で、主記憶装置内へ記憶される（ステップ
302)。以下にもっと詳細に説明されるであろう理由のた
めに、好適な実施例は二つの小Ｂトリー、SBT-1 148 及
びSBT-0 150 を使用している。さしあたっては、我々は
第２の小Ｂトリー150 が小Ｂトリーであるとだけ考えて
おこう。
【００３８】SBT 150 は、図２に示したＢトリーとよく
似たＢトリーである。新しい記録に対する指標付ポイン
タは主記憶装置内に記憶されるので、そのような指標付
ポインタの発生と記憶とは非常に速く、補助記憶装置の
使用に関してなんらの費用もこうむらない。
【００３９】小ＢトリーSBT 150 内に一次的に記憶され
た指標付ポインタを除いて、データベースファイル130
内の記録に対する指標付ポインタ全部が、ここでは大Ｂ
トリー(LBT) と呼ばれる主指標ファイル132 内に記憶さ
れる。大ＢトリーLBT 132 の最も重要な特徴は、指標付
ポインタが指標を付けられた順序で補助記憶装置内に記
憶され、且つディスクスペースを有効に使うようにパッ
クされることである。「指標を付けられた順序で……記
憶される」なる語はここでは補助記憶装置がアドレス順
に読み取られた場合に、大ＢトリーLBT 132 内の指標付
ポインタの指標値が、「循環」（これは以下に説明す
る）を除いて単調に増大又は減少することを意味すると
定義される。
【００４０】小ＢトリーSBT 150 の目的は、指標付ポイ
ンタを一時的に記憶し、且つ十分多数のこれらのポイン
タを回転する組み合わせ形の手順を用いて補助記憶装置
内のこれらの指標付ポインタの十分な記憶装置を可能に
するように記憶することである。説明の目的のために、
我々は記録挿入の約200 秒を表現している（記録は平均
で秒当たり100 記録で挿入されると想定して）どの一度
にも約20,000個の指標付ポインタをこのSBT 150 が保持
すると想定する。各ノードに記憶された100 項目を有す
る３レベルトリーを用いて、このSBT 150 は百万個の指
標付ポインタまで記憶できる。約20,000個だけを記憶す
るのだから、第２レベルの葉でないノードは非常にまば
らに送り込まれるだけである。それに反して、記録挿入
の一時的サージがある場合、又は（例えば、補助記憶装
置のテープバックアップを作るために）補助記憶装置内
のディスクが10分間利用できない場合には、十分な主記
憶装置が利用できるかぎり、３レベル小Ｂトリーが非常
に多数の指標付ポインタを容易に吸収できる。
【００４１】図３中に二つの小ＢトリーSBT がある意味
は新しく作り出された指標付ポインタが一方の小Ｂトリ
ーSBT 150 に記憶され、一方他方の小ＢトリーSBT 148
は大ＢトリーLBT 132 内へ組み合わされている。周期的
に、SBT-1 148 がLBT 132 内へ完全に組み合わされてし
まい、且つSBT-1 の内容が削除された後に、SBT-0 とSB
T-1 との定義が交換される (ステップ304)。この交換の
後に、全部の続いて作り出された指標付ポインタが（交
換の後に空の権利である）SBT-0 内に記憶されて、且つ
データベース管理システムプログラム146 がSBT-1 の内
容をLBT 132 内に組み合わせることを準備する。
【００４２】SBT-1 をLBT 内へ組み合わせる前に、ディ
スクポインタがそのLBT ファイルの始まりと末尾とへ設
定される。二つのポインタPTR A とPTR C とが、組み合
わせを実行する前のLBT へ始まりと端末とを示す。これ
らの二つのポインタが組み合わせ動作を通して保持され
るので、この組み合わせ過程の中間にコンピュータシス
テムが崩壊した場合に、指標記憶処理中にこのよく定義
された点へバックアップすることが可能であり、且つそ
れで順次編成データファイル130 内に記憶された記録を
用いて全部の続いて発生された指標付ポインタを再生す
る。
【００４３】SBT 148 をLBT 内へ組み合わせる処理は多
数回反復されるステップ 306〜316を有する段において
なされる。例えば、各２秒毎にこのシステムはSBT 148
内の指標付ポインタの１％をLBT 132 内へ組み合わせる
ことができる。これをなすために、データベース管理シ
ステムプログラム146 が指標値の範囲I1〜I2を選択し
て、その範囲内のSBT 内の指標付ポインタ全部を（主記
憶装置内の丁度一つのアレイである）BUFFER Aと呼ばれ
る緩衝記憶装置252 内へコピーする。ポインタSTがBUFF
ER Aへ未だコピーされていない最低の指標値のトラック
を維持する (ステップ306)。SBT 148 内の全部の指標付
ポインタがこの時保持されるので、これらの項目の何れ
に対する探索でもLBT 132 へのSBT 148 の組み合わせを
完了する前に実行され得る。
【００４４】次に、ステップ308 において、指標値のこ
の同じ範囲に対するLBT 132 内の補助記憶装置内の全部
の指標付ポインタが、ここではBUFFER Bと呼ばれるもう
一つの緩衝記憶装置254 内へコピーされる。効率のため
に、指標付ポインタが、ポインタPTR B により示される
ページによりスタートするページのユニットでBUFFERB
内へコピーされる。このコピーするステップの後に、PT
R B がLBT 132 の最初にまだコピーされていないページ
を示すように進められる。
【００４５】ステップ310 において、BUFFER AとBUFFER
Bとの内容が組み合わされ、且つ組み合わされたポイン
タが指標を付けられた順序でBUFFER C 256内へ記憶され
る。指標値I2より大きい指標値を有するBUFFER B内のあ
らゆるポインタが、次の組み合わせ動作の間（すなわ
ち、次のステップ 306〜316 通過の間）使用するために
BUFFER B内に残されていることは注目されたい。さしあ
たって、我々はステップ310 もポインタが指標ファイル
から削除されるステップであると言う事実を知らないで
もよい。
【００４６】LBT ファイル132 の葉でないノードの幾つ
かのコピーが、主記憶装置緩衝記憶装置260 内に維持さ
れている。緩衝記憶装置260 内に記憶された葉でないノ
ードの部分は設計的な選択事項であるが、典型的には補
助記憶装置へ葉でないノードをコピーすることを許容
し、且つＮ回の組み合わせサイクル毎に（例えば、10組
み合わせサイクル毎に１回）葉でないノードの新しい部
分集合を読むことを許容するのに十分大きい。かくし
て、SBT 148 の１％がステップ 306〜316 を通る各ルー
プの間に組み合わされる場合には、多分LBT の葉でない
ノードの15〜20％があらゆる１回において緩衝記憶装置
260 内に保持されるであろう。
【００４７】ステップ310 の間に、SBT 148 からの項目
がLBT 132 からの項目と組み合わされるので、緩衝記憶
装置260 内のLBT の葉でないポインタは、補助記憶装置
内のPTR C の位置に記憶されるはずの組み合わされたデ
ータを反映するために更新される。
【００４８】ステップ312 において、BUFFER C内の全部
一杯のページが、PTR D により示されるLBT ファイル13
2 の終端において補助記憶装置内へコピーされる。BUFF
ER C内に残っているあらゆる指標付ポインタがその緩衝
記憶装置の始まりへ動かされる。これらのポインタは次
の組み合わせ動作の間LBT 132 内に記憶されて、その間
別のポインタがBUFFER Cへ加えられる。BUFER C の全ペ
ージが補助記憶装置へコピーされた後に、PTR D がLBT
ファイル132 の新しい終端を示すために更新される。
【００４９】組み合わせ過程の間にシステム障害がある
場合には、新しく組み合わされたデータが補助記憶装置
内に確かに記憶されるまで、PTR A とPTR B との間のデ
ータが解放されないので、補助記憶装置内のデータはな
んらも失われない。
【００５０】ステップ314 において、組み合わせ動作の
少しの通過毎に１回、緩衝記憶装置260 内の変形された
葉でないノードが補助記憶装置へコピーされ、且つ次の
少しの組み合わせ動作に対して必要なその他の葉でない
ノードが緩衝記憶装置260 内へコピーされる。
【００５１】SBT 148 の全部が、まだLBT 132 内へ組み
合わされてしまっていない場合には(ステップ316)、組
み合わせ過程を通る次のループが、ステップ306 におい
て再スタートする。全部のSBT 148 がLBT ファイル132
内へ組み合わされてしまうまで、組み合わされる指標値
の範囲がこのループの各通過の間進められる。それか
ら、ステップ318 において、BUFFER B及びBUFFER C内の
LBT からのあらゆる残っている項目は、（ページが部分
的にのみ満たされる場合でさえも）LBT ファイル132 の
終端においてディスクへコピーされる。SBT 148 内のあ
らゆるものがLBTファイル132 内へ今やコピーされてし
まったので、SBT 148 内の全部のエントリが削除され
る。PTR A とPTR B との間のディスク空間が解放され、
且つポインタPTR A とPTR C とがLBT ファイル132 の始
まりと末尾とを示すためにリセットされる。
【００５２】第１SBT 148 をLBT 132 内へ組み合わせる
処理の間に、多くの新しい指標付ポインタが発生され且
つ第２SBT 150 内へ記憶される。一旦この組み合わせ処
理が完成されると、二つの小ＢトリーSBT の定義の交換
により、ステップ304 において全体の処理が再スタート
する。
【００５３】代わりの一実施例においては、二つの小Ｂ
トリー 148と150 とを用いる代わりに、このシステムは
０かあるいは１のいずれかに等しい特殊マーカを有する
指標付ポインタ毎にマーキングすることにより、単一の
SBT を用いることもできる。第１組み合わせ通路の間
に、０のマークを付けられた指標付ポインタはLBT 132
内へ組み合わされ、且つSBT 148 内に記憶された全部の
新しい指標付ポインタは１のマークを付けられる。最初
の組み合わせが完成された後に、１のマークを付けられ
た項目はLBT 132 内へ組み合わされて、且つSBT 148 内
に記憶された新しい指標付ポインタは０のマークを付け
られる。各次の組み合わせの間には、０と１とのマーク
を付けられたポインタの役割が交換される。
【００５４】データベースからのデータの削除 好適な実施例はデータベース及び指標ファイル130, 132
から記録を削除するための二つの機構を与えている。最
初に、ユーザが削除されるべき特定の記録を指定でき
る。この場合には、「削除注釈エントリ(DN)」270 が、
指定された記録の指標値に相当するSBT 148 内の位置に
おいて、SBT 内に記憶される。この削除注釈エントリは
その項目内に特殊削除ビットフラグが設定される以外
は、新しい記録に対する指標付ポインタと正確に同じよ
うに見える。
【００５５】削除注釈エントリを含んでいるSBT 葉ノー
ドがLBT 132 内へ組み合わされる場合には、同じ指標値
を有する削除注釈エントリと指標付ポインタとが、「相
互に相殺」し、且つ整合指標付ポインタは削除される
(ステップ308 参照) 。相当する記録も順次編成データ
ファイル130 から削除される。しかしながら、データ記
録の削除は削除フィルタ指定が維持されるかぎり延期さ
れ得る。
【００５６】第２に、ユーザ（又は応用プログラム）は
データベースから除去されるべきである項目の１個以上
のフィルタ範囲を指定できる。例えば、応用プログラム
が30日以上古いトランザクション日付を有する全部の記
録が削除されるべきであることを指定できる。この指定
されたフィルタ範囲は、削除フィルタリスト272 内に記
憶される。SBT とLBT とからの記録が組み合わされる時
はいつでも、フィルタ274 が各指標付ポインタをリスト
272 内のフィルタ範囲と比較し、且つあらゆる削除フィ
ルタ範囲内に落ち込む項目を削除する。相当する記録も
順次編成データファイル130 から削除されてもよい（ス
テップ310 参照）。
【００５７】関係事項 図３において、本発明により実行される回転する組み合
わせが、LBT ファイル132 の終端における空間を使用し
且つLBT ファイル132 の始まりにおける空間を解放する
ことは注意されたい。最後には利用できるディスク記憶
装置の終端に到達して、その場合にはこのファイルはデ
ィスクのアドレス空間の始まりにおけるメモリの捨てら
れたブロックを再利用するように循環する。結果とし
て、LBT ファイル132 は完全には隣接していない。しか
しながら、最も古く記憶された組み合わされたページか
ら次の順次の指標値までの飛び越しが常にあるから、こ
のファイルは実際に決して完全に論理的に隣接しないこ
とは注意されねばならない。「循環」アドレシングの使
用は、コンピュータプログラミングの技術に熟達した人
々には周知であり、且つそのシステムのユーザに対して
「透過」であると一般に考えられる。かくして、最大ア
ドレスの後の「次の」論理的アドレスが最低アドレスで
あるから、LBT ファイル132 は指標を付けられた順序で
記憶されるべきとまだ考えられる。
【００５８】メモリ常駐SBT 148 内のノードはあらゆる
大きさのノードを有することができる。このトリーは決
してディスク上に駐在しないから、ページサイズのノー
ドに固執する必要はない。それ故にSBT 内のノードは
（例えば、２又は３レベルのみを有するトリーを用い
て）典型的にはトリーの深さを最小化することにより、
中央処理ユニット効率を最大化するように寸法決めされ
る。
【００５９】あらゆる種類の整合動作がデータベース上
で実行される時はいつでも、典型的には記録の指定され
た集合を読み取るために、このシステムはSBT 148(及び
二つのSBT が使用されている場合はSBT 150)とLBT 132
との両方の整合範囲探索を実行しなくてはならない。こ
れは正常なＢトリーの場合を越えるわずかな中央処理ユ
ニットオーバーヘッドを意味する。指標が発生される方
法により独特な指標値が補償されるから、SBT 148 内に
所望の値を置かれた場合に指標付探索は完成される。最
も頻繁な探索が近頃に挿入された記録に対してである場
合には、これはメモリ常駐ＢトリーSBT 148 が貴重な緩
衝機能を満たすことを意味する。
【００６０】本発明の多重要素Ｂトリーは、指標値への
独特値制約条件を維持するための適当なデータ構造では
なく、そこで挿入は重複がないことを保証するために探
索動作により先立たれねばならないことは注意された
い。探索動作は挿入動作よりも効率がよくないので、そ
のような要求が多重要素Ｂトリーを使用する価値を大き
く害する。
【００６１】キー値を変形できるデータベースにおける
記録へなされることを必要とするあらゆる変形は、挿入
により引き継がれる削除動作により取り扱われ得る。
【００６２】組み合わせ手順を通る通路を作るための、
図４内のステップ302 における標準は、実際には、SBT
148 内の指標付ポインタエントリの数のモニタリングす
ることによって、及びSBT 内の指標付ポインタの数が指
定された数を越える時はいつでも組み合わせをトリガす
ることにより、典型的にトリガされるであろう。この種
類の標準がディスクアクセスを最小化し、且つ（一般に
利用できる主記憶装置108 の量に基づいて）前もって選
択された最良の大きさに近いSBT 148 を維持するように
組み合わせが実行される速度にも歩調を合わせる。
【００６３】補助記憶装置内に記憶された大Ｂトリー13
2 は、100 ％充満した葉ノード、及び効果的なディスク
アーム使用のための連続な多重ページブロック内に一緒
にパックされたトリーの各レベル上のノードのキー順序
系列により、順次のディスクアクセスに対して最良化さ
れる。新しい指標付ポインタの補助記憶装置内の大Ｂト
リー内への挿入は、メガバイト範囲で典型的である多重
ページブロック書込によって、非常に効果的に実行され
る。
【００６４】本発明の背景において論じた銀行業務シス
テム例を参照し直して、12バイトの記憶装置を必要とす
る各指標付ポインタを有する、秒当たり100 個の指標付
ポインタ挿入を取り扱うために、本発明により要求され
るディスク使用速度を考えよう。1200バイトの新しい指
標付ポインタデータが秒当たりに発生される。我々はこ
のシステムが4096バイトのページサイズを有するディス
クを使用すること、及び組み合わせ動作は１％だけ指標
値のあらゆる選択された範囲内に記憶されたデータの量
を典型的に増加させることを想定する。これは各組み合
わせ動作中にディスクへ書き込まれるデータの99％が古
いデータであることを意味する。組み合わせ動作が２秒
毎に１回行われる場合には、大Ｂトリーへ2400バイトの
データを加えることは、平均して、ディスクから58又は
59ページのブロックを読み取ること、及びそれから59ペ
ージのブロックをディスクへ書き込み返すことを必要と
する。しかしながら、二つのブロックの各々は各組み合
わせが二つだけの入出力動作（ディスクアーム運動）を
必要とするであろうことを意味する隣接するディスク位
置内に記憶される。かくして、この例においては、秒当
たり100 個の新しい指標付ポインタを挿入することは、
平均で秒当たり１ディスク入出力動作のみの必要とす
る。標準の従来技術Ｂトリーを用いて要求される秒当た
り200 ディスク入出力動作と比較した場合に、本発明の
利点は極めて明らかである。
【００６５】ディスク記憶デバイスは秒当たり25入出力
動作まで典型的に取り扱えるので、ディスク入出力動作
について少なくとも８個のディスク記憶デバイスを必要
とする従来技術システムとは似ない、単一の、非常に大
きいディスク記憶デバイスが大きいＢトリーを記憶する
ために使われ得る。従来技術システムと本発明との両方
において、指標ファイル132 は、幾分かはデータベース
ファイルの大きい寸法の故に、及び幾分かはデータがデ
ータベースへ挿入される且つデータベースから検索され
る速度を最大化するために、ディスクすなわち順次編成
データファイル130 を記憶するために使用されるディス
クと異なるディスク記憶デバイス上へ典型的に記憶され
る。
【００６６】銀行業務システム例に本発明を使用する
と、新しい項目挿入は単一ディスク記憶デバイスの入出
力能力の約４％だけを占有し、ディスクデバイスはなお
探索動作及び同様のものに対して残された十分な量の入
出力能力を有していることを意味する。更にその上、自
動日付されたデータベースエントリの削除は、あらゆる
付加的なディスク入出力動作を要求することなく本発明
により自動的に取り扱われ、従来技術の標準Ｂトリー解
決法と比較した場合に、補助記憶装置資源の本発明の使
用法において本発明をまさにもっと効率的にする。
【００６７】その他の態様 図５を参照して、二つ以上のＢトリーを使用することも
可能である。例えば、これもディスク上に記憶された中
間Ｂトリー (intermediate B-tree; IBT) 350が、メモ
リ常駐小ＢトリーSBT 148 と大Ｂトリー132 との間に挿
入され得る。この多重レベル機構を用いて、小Ｂトリー
SBT 148 からのデータがローリングベースで中間Ｂトリ
ーIBT 350 内へ組み合わされ得て、且つ中間ＢトリーIB
T 350 からのデータはもっと遅いローリングベースで大
ＢトリーLBT 132 内へ個別に組み合わされ得る。３レベ
ル構造の利点は、大Ｂトリーのページが読み取られるこ
とを必要とし且つ新しい記録と組み合わされた後にディ
スクへ再び書き込まれることを必要とする速度が実質的
に低減され得ることである。あらゆる一回においてデー
タベース内に保持される十分10億を越えるエントリを有
する高挿入速度データベースに対しては、多分これだけ
が正当化されるであろうし、その場合には、非常に多数
のページが挿入されるべき新しいデータの各ページに対
して、読み取られ且つディスクへ再び書き込まれること
を必要とするであろう。この多重レベル構造の欠点は、
データベース内の項目を見出し且つ読み取ることが、多
くのあるいはほとんどの探索のために３個のＢトリーを
アクセスする必要により、非効率的となることである。
【００６８】十分大きいデータベースに対しては、４個
あるいはそれ以上のレベルのＢトリーが使用され得て、
各レベルが連続するローリングベースで次のレベルでの
Ｂトリー内へ組み合わされる。
【００６９】本発明は少しの特定の態様を参照して説明
されてきたが、それらの記載は本発明を図解するもので
あり且つ本発明を制限するように解釈されるべきではな
い。添付の特許請求の範囲により定義されたような本発
明の真の精神と範囲とから離れることなく、この技術に
熟達した人々には種々の変形が生じるであろう。
【００７０】特に、好適な実施例において用いられたＢ
トリー構造は、置換データ構造が主データベース内の記
録を参照するために記憶された順序を定義するかぎり、
その他のデータ構造により置き換えられることができ
る。例えば、ハッシュテーブルが指標付ポインタを記憶
するための好適な実施例のＢトリーの場所に用いられ得
る。このハッシュテーブル内のエントリは指標を付けら
れた順序の代わりにハッシュ指標順序で記憶される。小
さいメモリ常駐ハッシュテーブルは、ハッシュ指標順序
で進行する組み合わせ手順により、補助記憶装置内に記
憶されたより大きいハッシュテーブル内へ周期的に組み
合わされる。
【図面の簡単な説明】
【図１】本発明の好適な実施例によるコンピュータシス
テムのブロック線図である。
【図２】Ｂトリーデータ構造のブロック線図である。
【図３】大きいデータベースへ指標付ポインタを記憶す
るために好適な実施例に用いられた過程の概念的ブロッ
ク線図である。
【図４】指標付ポインタを記憶するために好適な実施例
に用いられた過程のフローチャートである。
【図５】本発明に統合される指標緩衝計画の３レベル版
に対する概念的ブロック線図である。
【符号の説明】
100 コンピュータシステム 102 中央処理ユニット 104 システムバス 106 補助記憶装置 108 主記憶装置 110 仮想記憶装置 112 ユーザインタフェース 114, 116 他のコンピュータ 118 構内通信網又は広域ネットワークバス 120 ネットワークインタフェース 122, 124, 126 ディスク記憶デバイス 130 順次編成データファイル 132 「主指標」ファイルすなわち大Ｂトリー 142 応用プログラム 144 オペレーティングシステムソフトウエア 146 アクティビティ記録データベース管理プログラム 148 一時的指標ファイルすなわち小ＢトリーSBT-1 150 小ＢトリーSBT-0 200 通常のＢトリーデータ構造 202 根ノード 204-001 〜204-100 100 のキー値 206, 208 葉ノード 210, 212, 220 中間ノード 250 緩衝記憶装置 252 緩衝記憶装置Ａ 254 緩衝記憶装置Ｂ 256 緩衝記憶装置Ｃ 260 主記憶装置緩衝記憶装置 270 削除注釈エントリDN 272 削除フィルタリスト 274 フィルタ 300 〜318 ステップ 350 中間Ｂトリー(IBT)
フロントページの続き (72)発明者 ダイエター ゴーリック アメリカ合衆国 カリフォルニア州 94306 パロ アルト ポール アヴェニ ュー 757 (72)発明者 パトリック イー オニール アメリカ合衆国 マサチューセッツ州 02173 レキシントン ホイッティアー ロード ７

Claims (17)

    【特許請求の範囲】
  1. 【請求項１】主ランダムアクセス記憶装置と補助記憶装
    置とを有するコンピュータシステム内にエントリするデ
    ータベースを記憶し且つ維持する方法であって、前記コ
    ンピュータシステムにより実行される方法のステップ
    は、 要求に際して、データベースファイル内に新しい記録を
    記憶するステップ、 主記憶装置内に記憶されている第１トリーデータ構造内
    へ前記新しい記録への指標付ポインタを記憶するステッ
    プ、 補助記憶装置内に第２トリーデータ構造を記憶し、前記
    第２トリーデータ構造は指標付ポインタが前記第１トリ
    ーデータ構造内に記憶される記録以外の全部の前記デー
    タベースファイル内の記録への指標付ポインタを含んで
    おり、そこで前記第２トリーデータ構造内の前記指標付
    ポインタは前記補助記憶装置内に予定された順序で記憶
    されるステップ、 前記第１トリーデータ構造の一部を前記第２トリーデー
    タ構造内へ、(1A)前記第１トリーデータ構造内の指標付
    ポインタの一部を選択し、(1B)前記第２トリーデータ構
    造内の前記指標付ポインタの相当する一部を前記補助記
    憶装置から検索し、(1C)前記第１トリーデータ構造内の
    指標付ポインタの前記選択された部分を前記第２トリー
    データ構造から検索された前記指標付ポインタへ組み合
    わせ、(1D)前記予定された順序で前記補助記憶装置内へ
    この組み合わされた指標ポインタを記憶し、且つ(1E)前
    記第２トリーデータ構造からの指標付ポインタと組み合
    わされた指標付ポインタを前記第１トリーデータ構造か
    ら除去することにより、周期的に組み合わせるステッ
    プ、を具えており、 それにより付加されたデータベース記録に対する指標付
    ポインタはバッチで補助記憶装置へ書き込まれ、それに
    よって前記補助記憶装置を効率よくアクセスする、 ことを特徴とするコンピュータシステム内にエントリす
    るデータベースを記憶し且つ維持する方法。
  2. 【請求項２】前記周期的に組み合わせるステップが、ス
    テップ(1A)〜(1E)を実行する前に、 (1F)前記第１トリーデータ構造内の指標付ポインタの前
    記選択された部分を周期的に変更するステップを含んで
    いるので、前記第１トリーデータ構造内に記憶された全
    部の指標付ポインタが前記第２トリーデータ構造内へ組
    み合わされる、ことを特徴とする請求項１記載のコンピ
    ュータシステム内にエントリするデータベースを記憶し
    且つ維持する方法。
  3. 【請求項３】指定された指標値を有する前記データベー
    スファイル内の指定された記録を、(2A)前記指定された
    記録への指標付ポインタに対する前記第一トリーデータ
    構造を探索し、(2B)前記指標付ポインタが前記第１トリ
    ーデータ構造内に見出された場合には、前記データファ
    イルから前記指定された記録を削除し且つ前記第１トリ
    ーデータ構造から前記指標付ポインタを削除し、且つ(2
    C)さもなければ前記指定された指標値を示す削除注釈エ
    ントリを主記憶装置内に記憶することにより、削除する
    各要求に応答するステップを更に具え、 前記周期的に組み合わせるステップが、ステップ(1C)を
    実行する間に、(1G)前記削除注釈エントリの一つにより
    指定された指標値に整合する指標値を有する前記第２ト
    リーデータ構造内の各検索された指標付ポインタを削除
    し、且つ前記削除された指標付ポインタに相当する前記
    データベースファイル内の記録を削除するステップを含
    んでいる、 ことを特徴とする請求項１記載のコンピュータシステム
    内にエントリするデータベースを記憶し且つ維持する方
    法。
  4. 【請求項４】前記ステップ(2C)が、前記削除注釈エント
    リを具えているデータを、前記指定された指標値に従っ
    て、前記第１トリーデータ構造内に記憶するステップを
    含んでおり、且つ前記ステップ(1G)が、前記第１トリー
    データ構造からの指標付ポインタを前記検索された指標
    付ポインタに組み合わせる場合に、前記第１トリーデー
    タ構造内で削除注釈エントリにより指定された指標値と
    整合する指標値を有する各検索された指標付ポインタを
    削除し、且つ前記削除される指標付ポインタに相当する
    前記データベースファイル内の記録を削除するステップ
    を含んでいる、 ことを特徴とする請求項３記載のコンピュータシステム
    内にエントリするデータベースを記憶し且つ維持する方
    法。
  5. 【請求項５】主ランダムアクセス記憶装置と補助記憶装
    置とを有するコンピュータシステム内にエントリするデ
    ータベースを記憶し且つ維持する方法であって、前記コ
    ンピュータシステムにより実行される方法は、 要求に際して、データベースファイル内に新しい記録を
    記憶するステップ、 主記憶装置内に記憶されている第１トリーデータ構造内
    へ前記新しい記録への指標付ポインタを記憶するステッ
    プ、 補助記憶装置内に第２トリーデータ構造を記憶し、前記
    第２トリーデータ構造は指標付ポインタが前記第１トリ
    ーデータ構造内に記憶される記録以外の全部の前記デー
    タベースファイル内の記録への指標付ポインタを含んで
    おり、そこで前記第２トリーデータ構造内の前記指標付
    ポインタは前記補助記憶装置内に指標を付けられた順序
    で記憶されるステップ、 前記第１トリーデータ構造の一部を前記第２トリーデー
    タ構造内へ、(1A)指標値の範囲を選択し、(1B)指標値の
    前記選択された範囲内で前記第２トリーデータ構造内の
    全部の指標付ポインタを前記補助記憶装置から検索し、
    (1C)指標値の前記選択された範囲と整合する前記第１ト
    リーデータ構造内の指標付ポインタを前記検索された指
    標付ポインタへ組み合わせ、(1D)指標を付けられた順序
    で前記補助記憶装置内へ前記組み合わされた指標ポイン
    タを記憶し、且つ(1E)前記第２トリーデータ構造からの
    指標付ポインタと組み合わされた指標付ポインタを前記
    第１トリーデータ構造から除去することにより、周期的
    に組み合わせるステップ、を具えており、 それにより付加されたデータベース記録に対する指標付
    ポインタは選択された指標値範囲内でバッチで補助記憶
    装置へ書き込まれ、それによって前記補助記憶装置を効
    率よくアクセスする、 ことを特徴とするコンピュータシステム内にエントリす
    るデータベースを記憶し且つ維持する方法。
  6. 【請求項６】前記周期的に組み合わせるステップが、ス
    テップ(1A)〜(1E)を実行する前に、 (1F)指標値の前記選択された範囲を周期的に変更するス
    テップを含んでいるので、前記第１トリーデータ構造内
    に記憶された全部の指標付ポインタが前記第２トリーデ
    ータ構造内へ組み合わされ、更に、 指定された指標値を有する前記データベースファイル内
    の指定された記録を、(2A)前記指定された記録への指標
    付ポインタに対する前記第一トリーデータ構造を探索
    し、(2B)前記指標付ポインタが前記第１トリーデータ構
    造内に見出された場合には、前記データファイルから前
    記指定された記録を削除し且つ前記第１トリーデータ構
    造から前記指標付ポインタを削除し、且つ(2C)さもなけ
    れば前記指定された指標値を示す削除注釈エントリを主
    記憶装置内に記憶することにより、削除する各要求に応
    答するステップを更に具え、 前記周期的に組み合わせるステップが、ステップ(1C)を
    実行する間に、(1G)前記削除注釈エントリの一つにより
    指定された指標値に整合する指標値を有する前記第２ト
    リーデータ構造内の各検索された指標付ポインタを削除
    し、且つ前記削除された指標付ポインタに相当する前記
    データベースファイル内の記録を削除するステップを含
    んでいる、 ことを特徴とする請求項５記載のコンピュータシステム
    内にエントリするデータベースを記憶し且つ維持する方
    法。
  7. 【請求項７】前記ステップ(2C)が、前記削除注釈エント
    リを具えているデータを、前記指定された指標値に従っ
    て、前記第１トリーデータ構造内に記憶するステップを
    含んでおり、且つ前記ステップ(1G)が、前記第１トリー
    データ構造からの指標付ポインタを前記検索された指標
    付ポインタに組み合わせる場合に、前記第１トリーデー
    タ構造内で削除注釈エントリにより指定された指標値と
    整合する指標値を有する各検索された指標付ポインタを
    削除し、且つ前記削除される指標付ポインタに相当する
    前記データベースファイル内の記録を削除するステップ
    を含んでいる、 ことを特徴とする請求項６記載のコンピュータシステム
    内にエントリするデータベースを記憶し且つ維持する方
    法。
  8. 【請求項８】主ランダムアクセス記憶装置と補助記憶装
    置とを有するコンピュータシステム内にエントリするデ
    ータベースを記憶し且つ維持する方法であって、前記コ
    ンピュータシステムにより実行される方法は、 前記補助記憶装置内へデータベースファイル内の記録の
    集合を記憶し、前記ファイル内の各記録はフィールドの
    集合を含んでおり、そこで前記フィールドの指定された
    集合が前記記録の指標値であると指定されるステップ
    と、 前記ファイル内の前記記録の第１部分集合への指標付ポ
    インタを表現する第１トリーデータ構造を主ランダムア
    クセス記憶装置内に記憶し、前記第１トリーデータ構造
    は各々が前記ファイル内の記録への多様な指標付ポイン
    タを含んでいる多様な葉ノードを含んでいるステップ
    と、 前記記録の第２部分集合への指標付ポインタを表現して
    いる第２トリーデータ構造を補助記憶装置内に記憶し、
    前記記録の前記第２部分集合は前記記録の前記第１部分
    集合内に含まれない前記ファイル内の記録を具えてお
    り、前記第２トリーデータ構造は多様な葉ノードを含ん
    でおり、前記第２トリーデータ構造内の前記葉ノードは
    指標値の重複しない集合を有する指標付ポインタを含ん
    でおり、そこで前記葉ノードが指標を付けられた順序で
    前記補助記憶装置内へ記憶されるステップと、 各新しい記録を前記ファイル内へ記憶し且つ前記新しい
    記録への指標付ポインタを前記第１トリーデータ構造内
    へ記憶することにより、新しい記録を前記記録の指標値
    に従って主ランダムアクセス記憶装置内へ記憶する要求
    に応答するステップと、及び前記第１トリーデータ構造
    の一部を前記第２トリーデータ構造内へ、(1A)指標値の
    範囲を選択し、(1B)指標値の前記選択された範囲内の全
    部の指標付ポインタを前記補助記憶装置内の前記第２ト
    リーデータ構造から検索し、(1C)指標値の前記選択され
    た範囲と整合する前記第１トリーデータ構造内の指標付
    ポインタを前記検索された指標付ポインタ内へ組み合わ
    せ、(1D)指標を付けられた順序で葉ノード内に前記補助
    記憶装置内の前記組み合わされた指標ポインタを記憶
    し、且つ(1E)前記第２トリーデータ構造からの指標付ポ
    インタと組み合わされた指標付ポインタを前記第１トリ
    ーデータ構造から除去することにより、周期的に組み合
    わせるステップと、を具えており、 それにより付加されたデータベース記録に対する指標付
    ポインタは選択された指標値範囲内でバッチで補助記憶
    装置へ書き込まれ、それによって前記補助記憶装置を効
    率よくアクセスする、 ことを特徴とするコンピュータシステム内にエントリす
    るデータベースを記憶し且つ維持する方法。
  9. 【請求項９】指定された指標値を有する前記データベー
    スファイル内の指定された記録を、(2A)前記指定された
    記録への指標付ポインタに対する前記第一トリーデータ
    構造を探索し、(2B)前記指標付ポインタが前記第１トリ
    ーデータ構造内に見出された場合には、前記データファ
    イルから前記指定された記録を削除し且つ前記第１トリ
    ーデータ構造から前記指標付ポインタを削除し、且つ(2
    C)さもなければ前記指定された指標値を示す削除注釈エ
    ントリを主記憶装置内に記憶することにより、削除する
    各要求に応答するステップを更に具え、 前記周期的に組み合わせるステップが、ステップ(1C)を
    実行する間に、(1G)前記削除注釈エントリの一つにより
    指定された指標値に整合する指標値を有する前記第２ト
    リーデータ構造内の各検索された指標付ポインタを削除
    し、且つ前記削除された指標付ポインタに相当する前記
    データベースファイル内の記録を削除するステップを更
    に含んでいる、 ことを特徴とする請求項８記載のコンピュータシステム
    内にエントリするデータベースを記憶し且つ維持する方
    法。
  10. 【請求項１０】前記ステップ(2C)が、前記削除注釈エン
    トリを具えているデータを、前記指定された指標値に従
    って、前記第１トリーデータ構造内に記憶するステップ
    を含んでおり、且つ前記ステップ(1G)が、前記第１トリ
    ーデータ構造からの指標付ポインタを前記検索された指
    標付ポインタに組み合わせる場合に、前記第１トリーデ
    ータ構造内で削除注釈エントリにより指定された指標値
    と整合する指標値を有する各検索された指標付ポインタ
    を削除し、且つ前記削除される指標付ポインタに相当す
    る前記データベースファイル内の記録を削除するステッ
    プを含んでいる、 ことを特徴とする請求項９記載のコンピュータシステム
    内にエントリするデータベースを記憶し且つ維持する方
    法。
  11. 【請求項１１】主ランダムアクセス記憶装置と、補助記
    憶装置、及び前記主記憶装置と第２の補助記憶装置とへ
    結合された中央処理ユニットを有するデータベース管理
    システムであって、該データベース管理システムは、 補助記憶装置内へ少なくとも部分的に記憶される多数の
    記録を含んでいるデータベースファイルと、 前記データベースファイル内の前記記録に対する指標で
    あって、 主記憶装置内に記憶される第１トリーデータ構造であっ
    て、前記データベースファイル内の記録の部分集合への
    指標付ポインタを含んでいる第１トリーデータ構造、及
    び補助記憶装置内に記憶される第２トリーデータ構造で
    あって、指標付ポインタが前記第１トリーデータ構造内
    に記憶されている記録以外の前記データベースファイル
    内の全部の記録への指標付ポインタを含んでおり、そこ
    で前記第２トリーデータ構造内の前記指標付ポインタが
    補助記憶装置内へ予定された順序で記憶される、第２ト
    リーデータ構造、を具えている前記データベースファイ
    ル内の前記記録に対する指標と、及び前記中央処理ユニ
    ットによって実行されるデータベース処理プログラムで
    あって、 新しい記録を前記データベースファイル内に記憶し、且
    つ前記新しい記録への指標付ポインタを前記第１トリー
    データ構造内へ記憶するための新記録記憶手段と、及び
    前記第１トリーデータ構造の一部分を前記第２トリーデ
    ータ構造内へ、(1A)指標値の範囲を選択し、(1B)前記第
    ２トリーデータ構造内の前記指標付ポインタの相当する
    部分を前記補助記憶装置から検索し、(1C)前記第２トリ
    ーデータ構造から検索された前記指標付ポインタ内へ前
    記第１トリーデータ構造内の指標付ポインタの前記選択
    された部分を組み合わせ、(1D)前記予定された順序で前
    記補助記憶装置内へ前記組み合わされた指標ポインタを
    記憶し、且つ(1E)前記第２トリーデータ構造からの指標
    付ポインタと組み合わされた指標付ポインタを前記第１
    トリーデータ構造から除去することにより、周期的に組
    み合わせるためのトリー組合せ手段、を含んでいるデー
    タベース管理プログラム、を具えており、 それによって、付加されるデータベース記録に対する指
    標付ポインタがバッチで補助記憶装置へ書き込まれ、そ
    れにより補助記憶装置を効率よくアクセスすることを特
    徴とするデータベース管理システム。
  12. 【請求項１２】前記第１トリーデータ構造からの指標付
    ポインタを前記第２トリーデータ構造内に組み合せる前
    に、前記第１トリーデータ構造内の指標付ポインタの前
    記選択された部分を周期的に変えるための手段を前記ト
    リー組合せ手段が含んでいるので、前記第１トリーデー
    タ構造内に記憶される全部の指標付ポインタが前記第２
    トリーデータ構造内へ組み合わされ、前記システムは更
    に、 指定された指標値を有する前記データベースファイル内
    の指定された記録を削除する要求に応答し、(2A)前記指
    定された記録への指標付ポインタに対する前記第１トリ
    ーデータ構造を探索し、(2B)前記指標付ポインタが前記
    第１トリーデータ構造内に見出された場合には、前記デ
    ータファイルから前記指定された記録を削除し、且つ前
    記第１トリーデータ構造から前記指標付ポインタを削除
    し、且つ(2C)さもなければ、前記指定された指標値を示
    す削除注釈エントリを主記憶装置内に記憶する削除手段
    を含んでおり、 前記トリー組合せ手段は前記削除注釈エントリの一つに
    より指定された指標値と整合する指標値を有する前記第
    ２トリーデータ構造内の各検索された指標付ポインタを
    削除し、且つ前記削除された指標付ポインタに相当する
    前記データベースファイル内の記録を削除する削除フィ
    ルタ手段を含んでいる、ことを特徴とする請求項11記載
    のデータベース管理システム。
  13. 【請求項１３】前記削除注釈エントリを具えているデー
    タを、前記の指定された指標値に従って、前記第１トリ
    ーデータ構造内へ記憶するための手段を前記削除手段が
    含んでおり、且つ前記削除フィルタ手段が前記第１トリ
    ーデータ構造内の削除注釈エントリにより指定される指
    標値と整合する指標値を有する各検索された指標付ポイ
    ンタを削除し、且つ前記削除される指標付ポインタに相
    当する前記データベースフィルタ内の記録を削除する手
    段を含んでいる、ことを特徴とする請求項12記載のデー
    タベース管理システム。
  14. 【請求項１４】主ランダムアクセス記憶装置と、補助記
    憶装置、及び前記主記憶装置と第２の補助記憶装置とへ
    結合された中央処理ユニットを有するデータベース管理
    システムであって、該データベース管理システムは、 補助記憶装置内へ少なくとも部分的に記憶される多数の
    記録を含んでいるデータベースフィルタと、 前記データベースファイル内の前記記録に対する指標で
    あって、 主記憶装置内に記憶される第１トリーデータ構造であっ
    て、前記データベースファイル内の記録の部分集合への
    指標付ポインタを含んでいる第１トリーデータ構造、及
    び、 補助記憶装置内に記憶された第２トリーデータ構造であ
    って、指標付ポインタが前記第１トリーデータ構造内に
    記憶されている記録以外の前記データベースファイル内
    の全部の記録への指標付ポインタを含んでおり、そこで
    前記第２トリーデータ構造内の前記指標付ポインタは補
    助記憶装置内に指標を付けられた順序で記憶れれる前記
    第２トリーデータ構造、を含む前記記録に対する指標
    と、及び前記中央処理ユニットによって実行されるデー
    タベース管理プログラムであって、 新しい記録を前記データベースファイル内に記憶し、且
    つ前記新しい記録への指標付ポインタを前記第１トリー
    データ構造内に記憶するための新記録記憶手段、及び前
    記第１トリーデータ構造の一部分を前記第２トリーデー
    タ構造内へ、(1A)指標値の範囲を選択し、(1B)指標値の
    前記選択された範囲内の前記第２トリーデータ構造内の
    全部の指標付ポインタを補助記憶装置から検索し、(1C)
    指標値の前記選択された範囲と整合する前記第１トリー
    データ構造内の指標付ポインタを前記検索された指標付
    ポインタ内へ組合せ、(1D)前記補助記憶装置内へ指標を
    付けられた順序で前記組み合わされた指標ポインタを記
    憶し、且つ(1E)前記第２トリーデータ構造からの指標付
    ポインタと組み合わされた指標付ポインタを前記第１ト
    リーデータ構造から除去することにより、周期的に組み
    合わせるためのトリー組合せ手段、を含んでいるデータ
    ベース管理プログラムと、を具えており、 それによって、付加されるデータベース記録に対する指
    標付ポインタがバッチで補助記憶装置内へ書き込まれ、
    それにより補助記憶装置を効率よくアクセスすることを
    特徴とするデータベース管理システム。
  15. 【請求項１５】前記第１トリーデータ構造からの指標付
    ポインタを前記第２トリーデータ構造内へ組み合わせる
    前に、指標値の前記選択された範囲を周期的に変えるた
    めの手段を前記トリー組み合わせ手段が含んでいるの
    で、前記第１トリーデータ構造内に記憶される全部の指
    標付ポインタが前記第２トリーデータ構造内へ組み合わ
    され、前記データベース管理プログラムは更に、 指定された指標値を有する前記データベースファイル内
    の指定された記録を削除する要求に応答し、(2A)前記指
    定された記録への指標付ポインタに対する前記第１トリ
    ーデータ構造を探索し、(2B)前記指標付ポインタが前記
    第１トリーデータ構造内に見出された場合には、前記デ
    ータファイルから前記指定された記録を削除し、且つ前
    記第１トリーデータ構造から前記指標付ポインタを削除
    し、且つ(2C)さもなければ、前記指定された指標値を示
    す削除注釈エントリを主記憶装置内に記憶する削除手段
    を含んでおり、 前記トリー組合せ手段は前記削除注釈エントリの一つに
    より指定された指標値と整合する指標値を有する前記第
    ２トリーデータ構造内の各検索された指標付ポインタを
    削除し、且つ前記削除された指標付ポインタに相当する
    前記データベースファイル内の記録を削除する削除フィ
    ルタ手段を含んでいる、ことを特徴とする請求項14記載
    のデータベース管理システム。
  16. 【請求項１６】前記削除注釈エントリを具えているデー
    タを、前記の指定された指標値に従って、前記第１トリ
    ーデータ構造内へ記憶するための手段を前記削除手段が
    含んでおり、且つ前記削除フィルタ手段が前記第１トリ
    ーデータ構造内の削除注釈エントリにより指定された指
    標値に整合する指標値を有する各検索された指標付ポイ
    ンタを削除し、且つ前記削除される指標付ポインタに相
    当する前記データベースフィルタ内の記録を削除するた
    めの手段を含んでいる、ことを特徴とする請求項15記載
    のデータベース管理システム。
  17. 【請求項１７】主ランダムアクセス記憶装置と、補助記
    憶装置、及び前記主記憶装置と第２の補助記憶装置とへ
    結合された中央処理ユニットを有するデータベース管理
    システムであって、該データベース管理システムは、 補助記憶装置内へ少なくとも部分的に記憶される多数の
    記録を含んでいるデータベースファイルと、 前記データベースファイル内の前記記録に対する指標で
    あって、 主記憶装置内に記憶される第１データ構造であって、前
    記データベースファイル内の記録の部分集合への指標付
    ポインタを含んでいる第１データ構造、及び、 補助記憶装置内に記憶された第２データ構造であって、
    指標付ポインタが前記第１データ構造内に記憶されてい
    る記録以外の前記データベースファイル内の全部の記録
    への指標付ポインタを含んでおり、そこで前記第２デー
    タ構造内の前記指標付ポインタは補助記憶装置内に予定
    された順序で記憶れれる前記第２データ構造、を含む前
    記記録に対する指標と、及び前記中央処理ユニットによ
    って実行されるデータベース管理プログラムであって、 新しい記録を前記データベースファイル内に記憶し、且
    つ前記新しい記録への指標付ポインタを前記第１データ
    構造内に記憶するための新記録記憶手段、及び前記第１
    データ構造の一部分を前記第２データ構造内へ、(1A)指
    標値の範囲を選択し、(1B)前記第２データ構造内の前記
    指標付ポインタの相当する部分を前記補助記憶装置から
    検索し、(1C)前記第１データ構造内の指標付ポインタの
    前記選択された部分を前記第２データ構造から検索され
    た前記指標付ポインタ内へ組合せ、(1D)前記補助記憶装
    置内へ前記予定された順序で前記組み合わされた指標ポ
    インタを記憶し、且つ(1E)前記第２データ構造からの指
    標付ポインタと組み合わされた指標付ポインタを前記第
    １データ構造から除去することにより、周期的に組み合
    わせるための組み合わせ手段、を含んでいるデータベー
    ス管理プログラムと、を具えており、 それによって、付加されるデータベース記録に対する指
    標付ポインタがバッチで補助記憶装置内へ書き込まれ、
    それにより補助記憶装置を効率よくアクセスすることを
    特徴とするデータベース管理システム。
JP4167824A 1991-06-27 1992-06-25 コンピュ―タシステム内にエントリするデ―タベ―スを記憶し且つ維持する方法及びデ―タベ―ス管理システム Expired - Lifetime JP2515950B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/722007 1991-06-27
US07/722,007 US5204958A (en) 1991-06-27 1991-06-27 System and method for efficiently indexing and storing a large database with high data insertion frequency

Publications (2)

Publication Number Publication Date
JPH0628231A true JPH0628231A (ja) 1994-02-04
JP2515950B2 JP2515950B2 (ja) 1996-07-10

Family

ID=24900156

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4167824A Expired - Lifetime JP2515950B2 (ja) 1991-06-27 1992-06-25 コンピュ―タシステム内にエントリするデ―タベ―スを記憶し且つ維持する方法及びデ―タベ―ス管理システム

Country Status (3)

Country Link
US (1) US5204958A (ja)
EP (1) EP0522363A3 (ja)
JP (1) JP2515950B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2024519674A (ja) * 2021-05-26 2024-05-21 マイクロソフト テクノロジー ライセンシング，エルエルシー ツリーベースのデータ構造

Families Citing this family (171)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5430869A (en) * 1991-05-29 1995-07-04 Hewlett-Packard Company System and method for restructuring a B-Tree
US5764877A (en) * 1991-06-25 1998-06-09 Digital Equipment Corporation Media recovery with time-split B-trees
US7299240B1 (en) 1992-04-10 2007-11-20 Intellisync Corporation Method for translating computer data from one record structure to another
EP0567668A1 (en) * 1992-04-27 1993-11-03 International Business Machines Corporation A computer system for retrieval of information
US5727196A (en) * 1992-05-21 1998-03-10 Borland International, Inc. Optimized query interface for database management systems
US5408654A (en) * 1992-05-27 1995-04-18 Cdb Software, Inc. Method to reorganize an index file without sorting by changing the physical order of pages to match the logical order determined from the index structure
US5517641A (en) * 1992-05-27 1996-05-14 Cdb Software, Inc. Restartable method to reorganize DB2 tablespace records by determining new physical positions for the records prior to moving using a non sorting technic
US5508502A (en) * 1992-05-29 1996-04-16 Olympus Optical Co., Ltd. Information recording/regenerating method and information management system capable of managing a plurality of items of information efficiently
US5446881A (en) * 1992-09-25 1995-08-29 At&T Corp. Database storage and retrieval method using a declining stage size and repetitive searches
JP2865500B2 (ja) * 1992-09-30 1999-03-08 富士通株式会社 ファイル格納管理方法
US5418947A (en) * 1992-12-23 1995-05-23 At&T Corp. Locating information in an unsorted database utilizing a B-tree
US5685003A (en) * 1992-12-23 1997-11-04 Microsoft Corporation Method and system for automatically indexing data in a document using a fresh index table
US5613105A (en) * 1993-06-30 1997-03-18 Microsoft Corporation Efficient storage of objects in a file system
US5560007A (en) * 1993-06-30 1996-09-24 Borland International, Inc. B-tree key-range bit map index optimization of database queries
US5446887A (en) * 1993-09-17 1995-08-29 Microsoft Corporation Optimal reorganization of a B-tree
DE69331741T2 (de) * 1993-10-04 2002-10-02 Siemens Ag Verfahren und Vorrichtung zum schnellen Zugriff auf Dateneinheiten einer sortierten Liste und Datenbankträger für dieses Verfahren und/oder diese Vorrichtung
GB2283591B (en) * 1993-11-04 1998-04-15 Northern Telecom Ltd Database management
WO1995016237A1 (en) * 1993-12-10 1995-06-15 Intelligence Quotient International Limited Incremental backup system
US5499360A (en) * 1994-02-28 1996-03-12 Panasonic Technolgies, Inc. Method for proximity searching with range testing and range adjustment
JP3441807B2 (ja) * 1994-09-19 2003-09-02 株式会社日立製作所 Ｂ木インデクスの管理方法およびシステム
WO1996013015A2 (en) 1994-10-14 1996-05-02 United Parcel Service Of America, Inc. Multi-stage parcel tracking system
US5684990A (en) * 1995-01-11 1997-11-04 Puma Technology, Inc. Synchronization of disparate databases
US5794242A (en) * 1995-02-07 1998-08-11 Digital Equipment Corporation Temporally and spatially organized database
EP0826181A4 (en) 1995-04-11 2005-02-09 Kinetech Inc IDENTIFYING DATA IN A DATA PROCESSING SYSTEM
US6493762B1 (en) * 1995-05-08 2002-12-10 International Business Machines Corporation Index allocation for data broadcasting
US5701469A (en) * 1995-06-07 1997-12-23 Microsoft Corporation Method and system for generating accurate search results using a content-index
JPH0916607A (ja) * 1995-06-26 1997-01-17 Hitachi Ltd データベース管理システムにおけるインデクス管理方法
US5644763A (en) * 1995-06-28 1997-07-01 Sybase, Inc. Database system with improved methods for B-tree maintenance
US5918224A (en) * 1995-07-26 1999-06-29 Borland International, Inc. Client/server database system with methods for providing clients with server-based bi-directional scrolling at the server
US5809494A (en) * 1995-11-16 1998-09-15 Applied Language Technologies, Inc. Method for rapidly and efficiently hashing records of large databases
US5918234A (en) * 1995-11-22 1999-06-29 F.M.E. Corporation Method and apparatus for redundant postage accounting data files
US5802219A (en) * 1995-11-27 1998-09-01 Sun Microsystems, Inc. Methods and apparatus for table lookup transformation of digital images
US5758353A (en) * 1995-12-01 1998-05-26 Sand Technology Systems International, Inc. Storage and retrieval of ordered sets of keys in a compact 0-complete tree
US6427147B1 (en) * 1995-12-01 2002-07-30 Sand Technology Systems International Deletion of ordered sets of keys in a compact O-complete tree
US5974455A (en) * 1995-12-13 1999-10-26 Digital Equipment Corporation System for adding new entry to web page table upon receiving web page including link to another web page not having corresponding entry in web page table
GB2311392B (en) * 1996-03-22 1998-03-04 Digital Equipment Corp A method of maintaining information in a memory of a computer system
US5842196A (en) * 1996-04-03 1998-11-24 Sybase, Inc. Database system with improved methods for updating records
US5893088A (en) * 1996-04-10 1999-04-06 Altera Corporation System and method for performing database query using a marker table
US6006227A (en) * 1996-06-28 1999-12-21 Yale University Document stream operating system
US5832484A (en) * 1996-07-02 1998-11-03 Sybase, Inc. Database system with methods for parallel lock management
JPH11513160A (ja) * 1996-07-08 1999-11-09 フィリップス エレクトロニクス ネムローゼ フェンノートシャップ 反復探索実行方法
US5787435A (en) * 1996-08-09 1998-07-28 Digital Equipment Corporation Method for mapping an index of a database into an array of files
US6374232B1 (en) * 1996-08-29 2002-04-16 Oracle Corp. Method and mechanism for retrieving values from a database
US5943676A (en) 1996-11-13 1999-08-24 Puma Technology, Inc. Synchronization of recurring records in incompatible databases
US7302446B1 (en) 1996-11-13 2007-11-27 Intellisync Corporation Synchronizing databases
US6044381A (en) * 1997-09-11 2000-03-28 Puma Technology, Inc. Using distributed history files in synchronizing databases
US6212529B1 (en) * 1996-11-13 2001-04-03 Puma Technology, Inc. Synchronization of databases using filters
US5937401A (en) * 1996-11-27 1999-08-10 Sybase, Inc. Database system with improved methods for filtering duplicates from a tuple stream
US5848405A (en) * 1997-04-21 1998-12-08 Oracle Corporation Method and apparatus for identifying new data by address ranges
US6286011B1 (en) * 1997-04-30 2001-09-04 Bellsouth Corporation System and method for recording transactions using a chronological list superimposed on an indexed list
US6006027A (en) * 1997-08-20 1999-12-21 Synopsys, Inc. Method and apparatus for event simulation
US6122645A (en) * 1997-08-25 2000-09-19 Lucent Technologies, Inc. System and method for physically versioning data in a main memory database
CA2307226A1 (en) * 1997-11-03 1999-05-14 Top Info Outsourcing Services (Proprietary) Limited Data storage and retrieval using unique identifiers
US6792432B1 (en) 1998-03-31 2004-09-14 Sybase, Inc. Database system with methods providing high-concurrency access in B-Tree structures
US6272486B1 (en) * 1998-04-16 2001-08-07 International Business Machines Corporation Determining the optimal number of tasks for building a database index
US6314421B1 (en) 1998-05-12 2001-11-06 David M. Sharnoff Method and apparatus for indexing documents for message filtering
US6112209A (en) * 1998-06-17 2000-08-29 Gusack; Mark David Associative database model for electronic-based informational assemblies
US6067548A (en) * 1998-07-16 2000-05-23 E Guanxi, Inc. Dynamic organization model and management computing system and method therefor
CA2244626A1 (en) 1998-07-31 2000-01-31 Kom Inc. A hardware and software system
CN1194319C (zh) * 1998-08-11 2005-03-23 古庄晋二 对表格式数据进行查找、列表及分类的方法和装置
US6631366B1 (en) 1998-10-20 2003-10-07 Sybase, Inc. Database system providing methodology for optimizing latching/copying costs in index scans on data-only locked tables
US6363387B1 (en) 1998-10-20 2002-03-26 Sybase, Inc. Database system providing methodology for enhancing concurrency using row update bit and deferred locking
US6606626B1 (en) 1998-10-20 2003-08-12 Sybase, Inc. Database system with lock manager enhancement for improving concurrency
US6591269B1 (en) * 1999-05-19 2003-07-08 Sybase, Inc. Database system with methodology for online index rebuild
US7035880B1 (en) * 1999-07-14 2006-04-25 Commvault Systems, Inc. Modular backup and retrieval system used in conjunction with a storage area network
US7395282B1 (en) * 1999-07-15 2008-07-01 Commvault Systems, Inc. Hierarchical backup and retrieval system
US6438562B1 (en) * 1999-08-24 2002-08-20 Oracle Corporation Parallel index maintenance
US20040225865A1 (en) * 1999-09-03 2004-11-11 Cox Richard D. Integrated database indexing system
US6334123B1 (en) 1999-09-03 2001-12-25 Whamtech, Inc. Index relational processor
US6829695B1 (en) 1999-09-03 2004-12-07 Nexql, L.L.C. Enhanced boolean processor with parallel input
US6532476B1 (en) 1999-11-13 2003-03-11 Precision Solutions, Inc. Software based methodology for the storage and retrieval of diverse information
US6772141B1 (en) 1999-12-14 2004-08-03 Novell, Inc. Method and apparatus for organizing and using indexes utilizing a search decision table
US7003641B2 (en) * 2000-01-31 2006-02-21 Commvault Systems, Inc. Logical view with granular access to exchange data managed by a modular data and storage management system
US6721767B2 (en) * 2000-01-31 2004-04-13 Commvault Systems, Inc. Application specific rollback in a computer system
US7155481B2 (en) 2000-01-31 2006-12-26 Commvault Systems, Inc. Email attachment management in a computer system
US6658436B2 (en) * 2000-01-31 2003-12-02 Commvault Systems, Inc. Logical view and access to data managed by a modular data and storage management system
US6490578B1 (en) 2000-04-05 2002-12-03 Sybase, Inc. Database system with methodology for high-performance date
US6678692B1 (en) * 2000-07-10 2004-01-13 Northrop Grumman Corporation Hierarchy statistical analysis system and method
GB2372598A (en) * 2001-02-26 2002-08-28 Coppereye Ltd Organising data in a database
US7359920B1 (en) 2001-04-18 2008-04-15 Intellisync Corporation Communication protocol for synchronization of personal information management databases
US6778977B1 (en) * 2001-04-19 2004-08-17 Microsoft Corporation Method and system for creating a database table index using multiple processors
US6859808B1 (en) * 2001-05-31 2005-02-22 Oracle International Corporation Mapping logical row identifiers for primary B+tree-like structures to physical row identifiers
US20030028506A1 (en) * 2001-06-29 2003-02-06 Lin Yu Deferred index building systems, methods and computer program products for storing temporally spaced apart bursts of data records in a database
US6751627B2 (en) * 2001-07-23 2004-06-15 Networks Associates Technology, Inc. Method and apparatus to facilitate accessing data in network management protocol tables
US6763347B1 (en) * 2001-10-19 2004-07-13 Nick Zhang Indexing management for hierarchical main memory
JP2003141158A (ja) * 2001-11-06 2003-05-16 Fujitsu Ltd 順序を考慮したパターンを用いた検索装置および方法
US7249118B2 (en) * 2002-05-17 2007-07-24 Aleri, Inc. Database system and methods
US7647354B2 (en) * 2002-05-24 2010-01-12 Oracle International Corporation High-performance change capture for data warehousing
US7454569B2 (en) 2003-06-25 2008-11-18 Commvault Systems, Inc. Hierarchical system and method for performing storage operations in a computer network
US7577806B2 (en) * 2003-09-23 2009-08-18 Symantec Operating Corporation Systems and methods for time dependent data storage and recovery
US7827362B2 (en) * 2004-08-24 2010-11-02 Symantec Corporation Systems, apparatus, and methods for processing I/O requests
US7577807B2 (en) * 2003-09-23 2009-08-18 Symantec Operating Corporation Methods and devices for restoring a portion of a data store
US7725760B2 (en) * 2003-09-23 2010-05-25 Symantec Operating Corporation Data storage system
US7287133B2 (en) 2004-08-24 2007-10-23 Symantec Operating Corporation Systems and methods for providing a modification history for a location within a data store
US7631120B2 (en) 2004-08-24 2009-12-08 Symantec Operating Corporation Methods and apparatus for optimally selecting a storage buffer for the storage of data
US7904428B2 (en) * 2003-09-23 2011-03-08 Symantec Corporation Methods and apparatus for recording write requests directed to a data store
US7991748B2 (en) * 2003-09-23 2011-08-02 Symantec Corporation Virtual data store creation and use
US7730222B2 (en) * 2004-08-24 2010-06-01 Symantec Operating System Processing storage-related I/O requests using binary tree data structures
US7546324B2 (en) 2003-11-13 2009-06-09 Commvault Systems, Inc. Systems and methods for performing storage operations using network attached storage
JP4444677B2 (ja) * 2004-01-20 2010-03-31 クラリオン株式会社 検索データの更新方法および更新システム
JPWO2005086003A1 (ja) * 2004-03-08 2008-01-24 アネックスシステムズ株式会社 データベース・システム
US7483906B2 (en) * 2004-04-14 2009-01-27 Microsoft Corporation Method and system for renaming consecutive keys in a B-tree
US7689633B1 (en) * 2004-09-15 2010-03-30 Data Domain, Inc. Network file system-based data storage system
EP1681641A3 (en) * 2005-01-13 2007-04-04 International Business Machines Corporation Incremental indexing
US7792839B2 (en) * 2005-01-13 2010-09-07 International Business Machines Corporation Incremental indexing of a database table in a database
US20070022148A1 (en) * 2005-07-20 2007-01-25 Akers David G Reserving an area of a storage medium for a file
US20070091926A1 (en) * 2005-10-21 2007-04-26 Apostolopoulos John G Method for optimizing portions of data from a plurality of data streams at a transcoding node
US20070118547A1 (en) * 2005-11-22 2007-05-24 Monish Gupta Efficient index versioning in multi-version databases
US20070214139A1 (en) * 2006-03-10 2007-09-13 Roach James A System and method for mapping data in a multi-valued data structure
US8185576B2 (en) 2006-03-14 2012-05-22 Altnet, Inc. Filter for a distributed network
US8108355B2 (en) * 2006-10-27 2012-01-31 Hewlett-Packard Development Company, L.P. Providing a partially sorted index
KR100878142B1 (ko) * 2006-12-19 2009-01-13 연세대학교 산학협력단 플래시 메모리 상에서의 효율적인 동작을 위한 수정된ｂ-트리 인덱스 구성 방법
US8719809B2 (en) * 2006-12-22 2014-05-06 Commvault Systems, Inc. Point in time rollback and un-installation of software
US20080201290A1 (en) * 2007-02-16 2008-08-21 International Business Machines Corporation Computer-implemented methods, systems, and computer program products for enhanced batch mode processing of a relational database
US9449047B2 (en) 2007-06-19 2016-09-20 Sybase, Inc. Dynamic modification of schemas in streaming databases
US8745012B2 (en) 2007-08-10 2014-06-03 Sybase, Inc. Log-structured store for streaming data
KR100911413B1 (ko) 2007-11-08 2009-08-11 한국과학기술정보연구원 데이터베이스와 정보검색 통합을 위한 문서단위 동적색인관리 특성을 갖는 정보검색 시스템 및 그 방법
US9112886B2 (en) * 2007-12-27 2015-08-18 Verizon Patent And Licensing Inc. Method and system for providing centralized data field encryption, and distributed storage and retrieval
US20090254594A1 (en) * 2008-04-02 2009-10-08 Microsoft Corporation Techniques to enhance database performance
US20090259617A1 (en) * 2008-04-15 2009-10-15 Richard Charles Cownie Method And System For Data Management
US20090276470A1 (en) * 2008-05-05 2009-11-05 Vijayarajan Rajesh Data Processing System And Method
US20100146003A1 (en) * 2008-12-10 2010-06-10 Unisys Corporation Method and system for building a B-tree
US20100257175A1 (en) * 2009-04-02 2010-10-07 Yahoo!, Inc., a Delaware corporation Method, system, or apparatus for joining one or more events
US8180763B2 (en) * 2009-05-29 2012-05-15 Microsoft Corporation Cache-friendly B-tree accelerator
US8412688B1 (en) 2009-06-29 2013-04-02 Emc Corporation Delegated reference count base file versioning
US8200633B2 (en) * 2009-08-07 2012-06-12 International Business Machines Corporation Database backup and restore with integrated index reorganization
US10564944B2 (en) * 2010-01-07 2020-02-18 Microsoft Technology Licensing, Llc Efficient immutable syntax representation with incremental change
US8996563B2 (en) 2010-04-06 2015-03-31 Tokutek, Inc. High-performance streaming dictionary
US9021198B1 (en) 2011-01-20 2015-04-28 Commvault Systems, Inc. System and method for sharing SAN storage
US8375012B1 (en) 2011-08-10 2013-02-12 Hewlett-Packard Development Company, L.P. Computer indexes with multiple representations
US8930375B2 (en) * 2012-03-02 2015-01-06 Cleversafe, Inc. Splitting an index node of a hierarchical dispersed storage index
US9465829B2 (en) * 2012-04-30 2016-10-11 Sap Se Partial merge
US11010415B2 (en) 2012-04-30 2021-05-18 Sap Se Fixed string dictionary
US9171020B2 (en) 2012-04-30 2015-10-27 Sap Se Deleting records in a multi-level storage architecture
US9465844B2 (en) 2012-04-30 2016-10-11 Sap Se Unified table query processing
US10162766B2 (en) 2012-04-30 2018-12-25 Sap Se Deleting records in a multi-level storage architecture without record locks
US9165010B2 (en) 2012-04-30 2015-10-20 Sap Se Logless atomic data movement
US8930374B2 (en) 2012-06-29 2015-01-06 Nokia Corporation Method and apparatus for multidimensional data storage and file system with a dynamic ordered tree structure
US9218411B2 (en) 2012-08-07 2015-12-22 International Business Machines Corporation Incremental dynamic document index generation
US9405482B2 (en) * 2012-12-21 2016-08-02 Commvault Systems, Inc. Filtered reference copy of secondary storage data in a data storage system
US9760609B2 (en) * 2013-11-22 2017-09-12 Here Global B.V. Graph-based recommendations service systems and methods
US10152527B1 (en) 2015-12-28 2018-12-11 EMC IP Holding Company LLC Increment resynchronization in hash-based replication
US9857990B1 (en) 2016-03-24 2018-01-02 EMC IP Holding Company LLC Fast startup for modular storage systems
US10705907B1 (en) 2016-03-24 2020-07-07 EMC IP Holding Company LLC Data protection in a heterogeneous random access storage array
US10101934B1 (en) 2016-03-24 2018-10-16 Emc Corporation Memory allocation balancing for storage systems
US10324782B1 (en) 2016-03-24 2019-06-18 Emc Corporation Hiccup management in a storage array
WO2018056992A1 (en) 2016-09-22 2018-03-29 Visa International Service Association Techniques for in-memory key range searches
WO2018056993A1 (en) * 2016-09-22 2018-03-29 Visa International Service Association Techniques for in-memory data searching
US10152371B1 (en) 2016-09-30 2018-12-11 EMC IP Holding Company LLC End-to-end data protection for distributed storage
US10223008B1 (en) 2016-09-30 2019-03-05 EMC IP Holding Company LLC Storage array sizing for compressed applications
US10255172B1 (en) 2016-09-30 2019-04-09 EMC IP Holding Company LLC Controlled testing using code error injection
US10452312B2 (en) * 2016-12-30 2019-10-22 Intel Corporation Apparatus, system, and method to determine a demarcation voltage to use to read a non-volatile memory
US10706106B2 (en) 2017-02-09 2020-07-07 Micron Technology, Inc. Merge tree modifications for maintenance operations
US10725988B2 (en) * 2017-02-09 2020-07-28 Micron Technology, Inc. KVS tree
US10719495B2 (en) 2017-02-09 2020-07-21 Micron Technology, Inc. Stream selection for multi-stream storage devices
US10706105B2 (en) 2017-02-09 2020-07-07 Micron Technology, Inc. Merge tree garbage metrics
US10783186B2 (en) 2017-08-31 2020-09-22 Micron Technology, Inc. Heterogenous key-value sets in tree database
US10915546B2 (en) 2018-10-10 2021-02-09 Micron Technology, Inc. Counter-based compaction of key-value store tree data block
US11100071B2 (en) 2018-10-10 2021-08-24 Micron Technology, Inc. Key-value store tree data block spill with compaction
US10852978B2 (en) 2018-12-14 2020-12-01 Micron Technology, Inc. Key-value store using journaling with selective data storage format
US11048755B2 (en) 2018-12-14 2021-06-29 Micron Technology, Inc. Key-value store tree with selective use of key portion
US10936661B2 (en) 2018-12-26 2021-03-02 Micron Technology, Inc. Data tree with order-based node traversal
KR102128037B1 (ko) * 2019-03-18 2020-06-29 주식회사 로그프레소 다계층 메모리 구조에 최적화된 데이터 인덱스 방법 및 그 방법에 의해 인덱스된 데이터의 검색 방법
US11487731B2 (en) * 2019-07-24 2022-11-01 Vmware, Inc. Read iterator for pre-fetching nodes of a B-tree into memory
CN114692839B (zh) * 2020-12-25 2025-09-23 中科寒武纪科技股份有限公司 数据处理装置、数据处理方法及相关产品
CN113297432B (zh) * 2021-06-01 2023-11-07 阿里巴巴新加坡控股有限公司 用于分区拆分与合并的方法、处理器可读介质和系统
US11954345B2 (en) 2021-12-03 2024-04-09 Samsung Electronics Co., Ltd. Two-level indexing for key-value persistent storage device
US12411831B2 (en) * 2021-12-20 2025-09-09 International Business Machines Corporation Database index performance improvement
CN114296655B (zh) * 2021-12-30 2024-02-02 杭州海康威视系统技术有限公司 一种针对分布式存储系统的数据存储方法及装置
CN114791913B (zh) * 2022-04-26 2024-09-13 北京人大金仓信息技术股份有限公司 数据库的共享内存缓冲池处理方法、存储介质与设备
CN115017842B (zh) * 2022-08-09 2022-12-02 北京星途探索科技有限公司 气动数据的插值方法及装置、电子设备、存储介质

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4468728A (en) * 1981-06-25 1984-08-28 At&T Bell Laboratories Data structure and search method for a data base management system
US4611272A (en) * 1983-02-03 1986-09-09 International Business Machines Corporation Key-accessed file organization
US4677550A (en) * 1983-09-30 1987-06-30 Amalgamated Software Of North America, Inc. Method of compacting and searching a data index
US4945475A (en) * 1986-10-30 1990-07-31 Apple Computer, Inc. Hierarchical file system to provide cataloging and retrieval of data
US5089952A (en) * 1988-10-07 1992-02-18 International Business Machines Corporation Method for allowing weak searchers to access pointer-connected data structures without locking
IT1229678B (it) * 1989-04-27 1991-09-06 Sgs Thomson Microelectronics Generatore di corrente variabile indipendente dalla temperatura.

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2024519674A (ja) * 2021-05-26 2024-05-21 マイクロソフト テクノロジー ライセンシング，エルエルシー ツリーベースのデータ構造

Also Published As

Publication number Publication date
EP0522363A2 (en) 1993-01-13
EP0522363A3 (en) 1993-12-01
JP2515950B2 (ja) 1996-07-10
US5204958A (en) 1993-04-20

Similar Documents

Publication Publication Date Title
JP2515950B2 (ja) コンピュ―タシステム内にエントリするデ―タベ―スを記憶し且つ維持する方法及びデ―タベ―ス管理システム
US7257690B1 (en) Log-structured temporal shadow store
US5640561A (en) Computerized method and system for replicating a database using log records
CA2941074C (en) Managing storage of individually accessible data units
US6898688B2 (en) Data management appliance
US7036043B2 (en) Data management with virtual recovery mapping and backward moves
US8667274B2 (en) System and method for WORM data storage
EP1461700B1 (en) Appliance for management of data replication
US6654868B2 (en) Information storage and retrieval system
JP2002525755A (ja) アクティブｄｂｍｓテーブルを再編成するための方法及び装置
EP1836622B1 (en) Methods and apparatus for managing deletion of data
JP2014197425A (ja) 個別にアクセス可能なデータユニットの記憶の取り扱い方法
KR20010000136A (ko) 대용량 서지정보 검색 서비스 시스템
Verma et al. A new approach to version management for databases
KR100577518B1 (ko) 어드레스인덱스를 이용한 파일 백업 및 검색 방법
JPH0418646A (ja) データベース処理方式
JP3890212B2 (ja) 情報格納システム及び情報格納方法
JPH0877205A (ja) リレーショナルデータベース管理システム
JPH1196058A (ja) Ｔ木インデックス構築方法及び装置及びｔ木インデックス構築プログラムを格納した記憶媒体
JPH04155548A (ja) ログ管理・復旧処理方式
Gorman Managing the Very Large Database
HK1202172B (zh) 單獨可訪問數據單元的管理存儲
HK1181484B (en) Method, system and computer system for managing data
HK1127140A (en) Managing storage of individually accessible data units
HK1127140B (en) Managing storage of individually accessible data units