JPH0432420B2 - - Google Patents

Info

Publication number
JPH0432420B2
JPH0432420B2 JP58238027A JP23802783A JPH0432420B2 JP H0432420 B2 JPH0432420 B2 JP H0432420B2 JP 58238027 A JP58238027 A JP 58238027A JP 23802783 A JP23802783 A JP 23802783A JP H0432420 B2 JPH0432420 B2 JP H0432420B2
Authority
JP
Japan
Prior art keywords
page
node
data
pages
index
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.)
Expired - Lifetime
Application number
JP58238027A
Other languages
English (en)
Other versions
JPS59146356A (ja
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 filed Critical
Publication of JPS59146356A publication Critical patent/JPS59146356A/ja
Publication of JPH0432420B2 publication Critical patent/JPH0432420B2/ja
Granted 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/9017—Indexing; Data structures therefor; Storage structures using directory or table look-up
    • 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/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching

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)

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明はコンピユータ・システムのためのフア
イル編成技術に係り、更に具体的には本発明は最
少回数のアクセス試行によつてデイスクの様な２
次記憶システムに於けるデータのアクセスを行な
う技術に係る。 〔従来技術〕 大型コンピユータ・システムに於ける２次的記
憶装置はコンピユータの主記憶装置との間におい
て大量のデータの記憶、更新及び検索を行う。フ
アイルと称せられるその様なデータの編成はアク
セス動作を有効なものにするために重要である。
更に、特にデイスクの様なランダム・アクセス２
次的記憶装置におけるフアイルに新しいデータ要
素を挿入し、該フアイルからデータ要素を削除す
る事が出来る事が重要である。その様なフアイル
を“ダイナミツク”フアイルと称する。 周知の様にその様なフアイルを構成するために
多数の技術が提案された。現在Ｂ−Treeインデ
ツクス構成が市販装置の標準である。D.Comer
の“The Ubiquitous Ｂ−Tree”と題する論文
（Computing Surveys，Vol.11No.２，June 1979，
pp.1−137）にＢ−Treeについての説明がみられ
る。 ダイナミツク・フアイルに適した最近のフアイ
ル編成技法は、拡張可能（extendible）ハツシン
グである。固定寸法のフアイルとか寸法が増大す
るフアイルとかのための外部記憶装置に存在する
大型フアイルをアクセスするための高速法として
拡散可能ハツシングを用いうる様にする多数の技
法が開発された。たとえば、R.Fagin等の
“Extendible Hashing−Ａ Fast Access
Method for Dymanic Files”と称する論文
（ACM Trans.Data Base Syst.Vol.4，No.３，
September，1979，pp.315−344）には通常のハ
ツシングと異なり、フアイルと同様に伸長し、収
縮する構成を有する拡張可能ハツシングのアクセ
ス技術が開示されている。Fagin等の方法はハツ
シユ関数とデータを記憶するデイスク・アドレス
の間にインデツクスを用いる事によつて、データ
のアドレス空間からハツシユ・アドレス空間を分
離する。それによつてインデツクス項を識別する
ために初期に必要とされるビツトよりも更に多数
のビツトが生じる。しかしながら、Fagin等の場
合、フアイルが十分に大きく、インデツクスの小
部分のみが主記憶装置に於て適合すると、２デイ
スク・アクセス／データ・アクセスを必要とす
る。 Litwinの“Linear Virtual Hashing：Ａ
New Tool for Files and Tables
Implementation”，（Proc.6th Int′l.Cont.on
Very Lage Data Bases，Montreal，1980，
pp.213−223）に於ては、キイのハツシユ・アド
レスが、そのページのオーバフローしたデータに
関するハツシユ・アドレスを変更する事なく或る
予じめ定義した順序で変更される、線形ハツシン
グ関数と称するダイナミツク・ハツシング関数を
開示している。これはフアイルのために割り振つ
たスペースを現在のフアイルの端部へ連接したペ
ージを付加する事によつて線形的に伸長させる利
点を有する。 しかしながら、Litwinは、空間を有効に利用
するためには、有効ではい、隣接した連続的なア
ドレス空間の存在を仮定した。彼はデイスク・ア
ドレスに対するページ番号をマツピングする方法
を説明しているが、彼のデイスク空間を利用する
方法は、デイスク・アクセスに於てフアイルに付
加的な１次ページ（Primary page）を付加する
ためのコストが典型例として３アクセス／ページ
を要するという結果を呈する。更に、用いられる
オーバフロー・ページの数及びパフオーマンスは
本発明と比べて好ましいものではない。 G.Martinの“Spiral Storage；Incrementally
Augmentable Hash Addressed Storage”
（Theory of Computation，Report No.．27，
U.of warwick，Conventry，England，Merch
1979）に於ては、キイがアドレス空間内にマツピ
ングされ、よつてキイがその空間のある部分に於
いて他の部分よりも濃密となるハツシング技術が
開示されている。フアイル伸長の際に、より濃密
な空間を占めるために用いたキイは新しい、より
濃密でない空間に拡散される。Martinはキイを
均一でなくエクスポネンシヤルに空間にキイをマ
ツピングするハツシユ関数を用いている。しかし
ながら、ハツシユ関数により生じた相対的ページ
を実際のデイスク・アドレスへマツピングする。
Martinの方法は複雑であり、デイスク・アクセ
ス／付加した１次ページに関して高価につく。更
に、オーバフロー・レコードを処理する彼の方法
は特に不成功サーチの場合において好ましくない
パフオーマンスを呈するリハツシング
（rehashing）を含む。 これらの拡張可能ハツシング技術はフアイル伸
長もしくは収縮に対処するための完全なフアイル
再編成及びリハツシングを必要としない。加え
て、それらの技術はＢ−Treeの様な３インデツ
クス法によつて呈せられるものよりもより高速の
ランダム・アクセスが可能である。更にそれらの
技術は限定された形の順次性即ちキイ・オーダー
でなく或る順序でフアイルのレコードを順序付け
る能力を与える。しかしながら、これらのハツシ
ング法のいずれもがそれだけでは、フアイル・ア
ドレツシングに於て必要とされる利点を組合わさ
れたもの即ち単一デイスク・アクセス、下方に存
在するデイスク空間の直接的な記憶管理及び衝突
に対処するためのリハツシングの必要性の回避等
を可能とし得ない。 上記Martinの論文におけるスパイラル記憶の
例外は別として、全ての拡張可能なハツシング技
法の特徴はパフオーマンスが変動する点にある。
ハツシユ関数はハツシングされたキイをフアイル
のページ全体に均一に分布させる。即ち、これら
のページが均一に満たされ、ほとんど同時に完全
にいつぱいになる。更にフアイルが成長する短い
期間に於て、フアイル・ページの大多数が全てオ
ーバフローし、それらのエントリは２ページに分
割しなければならない。その結果、利用度
（utilization）は50％及びほとんど100％の間の変
化を呈し短い分割期間に於て突然50％に低下す
る。更に挿入を行なうコストは低利用度の場合比
較的低いが、分割期間に於ては極めて多数の挿入
がページ分割に先行するので相当高くなる。最後
に、もしもその技法に於てオーバフロー・レコー
ドが通常の方法で要求されるならば、オーバフロ
ーの生じる頻度は利用度が100％に近付くにつれ
て劇的に増加する。これによつて、オーバフロ
ー・レコードのアクセスが増々共通してくるの
で、デイスク・アクセスに関して挿入及びサーチ
のコストの急峻な増加が生じる。 〔発明の目的及び概要〕 本発明の目的は殆どの場合単一アクセスでもつ
て選択された（任意の）キイからデータを検索す
るための技術を提供する事にある。 本発明の他の目的は大きな再編成もしくはリハ
ツシングを行う事なくフアイルの寸法の変更を可
能にする技術を提供する事である。 本発明の更に他の目的は、直接的な技法によつ
て、記憶スペースが有効に使われる様に方法それ
自体の一部として物理的なデイスク空間を管理す
る技術を提供する事である。 本発明の更に他の目的は、キイの挿入及びサー
チのコストが、フアイルが伸長するかあるいは収
縮する際に変動しないアクセス技術を提供する事
にある。 本発明は、フアイル構成が２つのレベル即ちイ
ンデツクス・レベル及びデータ・レベルのみから
なる様なキイ・アクセス（インデツクス）型フア
イルの編成技術に係る。両方のレベルは、ページ
のランダム・アクセスを支援するページ編成２次
記憶媒体に永久的に記憶される。インデツクス・
レベルは固定された、指定可能な数のページを有
する様に設計され、フアイルが使用中の場合は全
体がコンピユータの記憶装置内に記憶される。フ
アイルが寸法を変えるにつれて、各インデツク
ス・エントリをして数が増大（縮小）するデー
タ・ページを有するデータ・ノードを参照させる
事によつて固定寸法のインデツクスが可能にな
る。インデツクス・エントリによつて参照した１
より多い数のデータ・ページのアクセスを回避す
る事はサーチ・アーギユメント（サーチ引数）の
ビツトを用いるアドレス計算によつて達成され
る。この計算に含まれるビツトの数は次の様に与
えられる。 log2（インデツクス項によつて参照されたペー
ジの数） ここでその様なページの数は２のｎ乗である。 最大のバツフア寸法としては、データのアクセ
スを支援するためにフアイル（及びアクセス）方
法に関連する主記憶装置のページの数を示す寸法
が選択される。このバツフアは拡張可能ハツシン
グに於ける様にフアイルに対するインデツクスを
含むが、そのインデツクスはバツフア寸法内に含
まれる様に制限される。インデツクス・レベルの
存在によつて記憶管理がより容易になる。インデ
ツクスがその限度まで伸長すると、データ・ノー
ドに於けるページの数を二倍にし、よつてインデ
ツクス・エントリによつて参照されたページの数
も同様にして二倍化する事によつて、更にフアイ
ルの伸長を行わせる。 必要に応じて、記憶装置の利用度が適度に高く
なる事を保証するためにオーバフロー・ページが
用いられる。オーバフロー・ページに関する新規
な技法によつて、不成功サーチが２デイスク・ア
クセスよりも多数のアクセスを必要とする事が僅
少であつて、しかもオーバフロー・ページのため
の空間利用度を高くしうる事が保証される。 その方法はフアイルのキイを不均一に分布させ
るハツシング関数、ｈ（key）、の選択を含む。次
にこの関数の結果を、キイ空間の１つの境界付近
に於て他の境界に於けるよりも２倍の数のキイが
存在する様に他の関数、exhash（key）、を用いて
エクスポネンシヤルに分布させる。 この新規な改良した形態の拡張可能ハツシング
を境界付けたインデツクス・エクスポネンシヤ
ル・ハツシング（bounded index exponential
hashing）“BEH”と称することにする。これは
１デイスク・アクセスに近いフアイルの任意レコ
ードへのランダム・アクセスとフアイル寸法によ
つて変動しないパフオーマンスとを提供する点に
於て他の伸長可能ハツシング技法よりもすぐれた
利点を有する。それは実施がまわりくどくなくて
直接的であり、しかもこのパフオーマンスを達成
するのに一定の指定しうる量の主記憶しか必要と
しない。その基礎となる物理的なデイスク記憶が
容易に管理され、不成功サーチに於ては２アクセ
スより多いアクセスを用いるのがまれである事を
保証する様にレコード・オーバフローが処理され
る。 〔実施例〕 以下の説明に於いて、本技術分野に於いて標準
的に用いられる次の様な用語を用いる。フアイル
はレコードの集合体であつて、各レコードはキイ
によつて識別される。アクセス法は、その内部に
フアイルをマツピングできる論理的記憶構成とこ
の構成を管理するのに必要なアルゴリズムとを含
む。その方法は１つもしくは複数の２次記憶装置
の通常固定された寸法のページと称する記憶単位
の集合体を管理する。アクセス方法を指定するた
めに、複数のページ間の関係、ページの内部構造
並びにフアイル更新（レコードの挿入、削除もし
くは変更）のためのアルゴリズム及び検索が記述
されねばならない。“アクセス”という用語は更
新もしくは検索の任意の動作を意味する。ページ
はページ間につながるアクセス路に従つてアクセ
スされる。一般的にはページはレコードと他のペ
ージに対するポインタを含むインデツクス・エン
トリとを含む。もしもページがインデツクス・エ
ントリのみを含むならば、それを登録簿（もしく
はインデツクス）ページと称する。もしもページ
が複数のキイとそれらに関連するレコードのみを
含むならば、それをデータ・ページもしくはデー
タ・リーフと称する。 総括 本発明に従つて、フアイルのキイを出来るだけ
均一に分布されるハツシング関数ｈ（key）が選
択される。J.L.Carter等の“Universal Classes
of Hash Functions”という題名の論文（J.
Computers and System Science，Vol.18，No.
２，April，1979，pp.143−144）に於いて示され
る様な或る一群の汎用ハツシング関数から選択し
たハツシング関数を用いると、ハツシングされた
キイが均一に分布される確率が非常に高くなる。
例えば次の様なハツシング関数が適している。 (1) ｈ（key）＝（（m*key）＋ｎ）mod ｐ）mod
ｂ ここでｐは基数であり、ｂはハツシユ空間の
寸法であり、ｍ及びｎは整数であるものとす
る。 ハツシユ・アドレス空間（ｈの領域）は実用
上24ビツト以上のハツシユ・アドレスを生じる
ので、フアイルの全体的な予定された伸長分を
収容するものでなければならない。これらアド
レスは０と１の間の24ビツト（もしくはそれ以
上）の小数点部として解釈される。 次にハツシユ関数(1)の結果を次の関数を用い
てエクスポネンシヤルに分布させる。 (2) exhash（key）＝2h(key)−１ ここで、ｈ（key）は汎用（universal）ハツ
シユ関数を適用した結果である。式(1)の目的は
フアイルが伸長する場合のパフオーマンスの変
動を回避して均一なパフオーマンスを保証する
ためである。このステツプの後で、ハツシユ関
数のエクスポネンシヤル特性はそのアクセス法
にはそれ以上導入されない。パフオーマンスは
影響されるが、アルゴリズムは影響されない。 関数exhash（key）は均一に分布したハツシ
ングされた０ないし１の範囲のキイを０ないし
１の範囲の値に再マツピング（remap）する。
ただし、ハツシングされたキイの頻度はこの範
囲にわたつて変動する。エクスポネンシヤル・
ハツシングを用いてハツシングされた０付近の
キイは、１付近のハツシングされたキイの２倍
の頻度である。任意所定の利用度を有するペー
ジの相対的頻度を一定にし、オーバフローに於
ける及び分割頻度に於ける変動を除去する事が
できるので、デイスク・アクセス動作を一定に
する事ができる。 本発明では他の拡張可能なハツシング技法の
重要な特性を変更する事なく、エクスポネンシ
ヤル・ハツシングが用いられる。即ち、エクス
ポネンシヤルにハツシングしたキイ値をデータ
及びインデツクス・エントリと共に記憶させる
事が出来、フアイルに於けるページ内部のサー
チを支援するために用いる事が出来る。更に重
要な事は、ページがオーバフローする場合、記
憶したハツシングされたキイのビツトが、２ペ
ージにわたるオーバフロー・ページ上のエント
リをどの様に分割する（split）がを決定する
事である。 その分割は多くの拡散可能なハツシング法に
必要とされるものと同種のデイジタル分割であ
る。kpを、所定のページに記憶される全ての
ハツシングされたキイ値（すなわちexhash
（key）の結果）のプレフイツクス（接頭部）
であるとする。ページが一杯でしかもなお１つ
のキイを挿入したい場合、ページの内容は次の
様にして２つのページの間で分割される。kp
〓“０”のプレフイツクスを有するハツシング
されたキイに関連するページの内容（インデツ
クスもしくはデータ）がそれらのページの一方
に配置され、kp〓“１”のプレフイツクスを
有するハツシングされたキイに関連する内容が
他のページ上に配置される。 第１図はコンピユータの主記憶装置１に於け
るBEHインデツクス（BEH INDEX）物理的
配置、２次記憶装置２（例えばデイスク・メモ
リ）に連続したページのブロツクとして配置し
たデータ・ノードを図示する。ページの数は２
のｎ乗である。 第２，１図はデータ・ノード３の２倍化
（doubling）の前のBEH編成フアイルの状態を
示する。この段階に於て、インデツクス・レベ
ルのコピーが主（１次）コンピユータ記憶装置
のバツフア内にあり、データ・レベルはデイス
クの様な２次記憶装置内にある。説明を簡単に
するためにページ単位で４のインデツクス寸法
を仮定する。 Ａ フアイル・サーチ 実施例に於てはフアイルは次の様にサーチ
（探索）する。exhash（ARG）−−ARGはデー
タが所望される探索キイである−−の先頭（若
しくは最初）の２ビツトを、ARGのデータの
探索が連続するところのインデツクス・ページ
を選択するために用いる。図に示すフアイルに
於いて、exhash（ARG）の最初の２ビツトを
用いて、“01”インデツクス・ページが選択さ
れる。exhash（ARG）の他ビツト、（例えばビ
ツト２ないし５）は、もしも探索が成功である
ならば、ARGのためのデータが存在するペー
ジを参照するインデツクス・ページ“01”に於
けるデイスク・アドレス、“PTR”、を見出す
ために用いる。PTRによつて参照されたペー
ジが読取られ、“ARG”が存在するかどうかを
決定するために、探索され、もしも存在するな
らば、それと関連するデータを戻す。第２，１
図に於けるデータ・レベルのノード（ページ）
は“01”〓“101”で始まるexhash（ARG）の
値に関するデータを含む。データ・レベル・ペ
ージに於けるDiはARG＝Kiに関するデータで
あつて、exhash（ARG）＝“01”〓“101”〓
“011′＝“01101011”である。データ・ノードの
２倍化前後のフアイル探索は本明細書のフアイ
ル動作（fileoperation）の項で説明する。 Ｂ バツフアが充填した後の伸長 データ・ノード（頁）がオーバフローし、そ
れを参照するインデツクス・ページ自体が充満
しているものと仮定する。標準的な拡張可能ハ
ツシング法に於いては、これが引金となつてデ
ータ・ページの分割が行なわれる。よつてイン
デツクス・ページはオーバフローする。インデ
ツクス・オーバフローはインデツクス寸法を２
倍化する事によつて処理され、これによつて入
来する挿入引数（arguments）に対して
exhashを適用する場合の記憶された結果の未
使用サフイツクス（接尾部）であるIDの第１
ビツトに基いて、インデツクスの各ページのエ
ントリを２ページに分離させる。即ち、インデ
ツクスは８ページに増え、それをアクセスする
のに３ビツトのexhash（ARG）が必要となる。 本発明のBHFハツシングに於ては、インデ
ツクス寸法は増えない。むしろ、そのノードの
２つのノードへの分割ではなくて、オーバフロ
ーを収容する様にデータ・ノードの寸法が２倍
になる。即ち、多種ページ・データ・ノードが
フアイルの寸法が伸長されるにつれて発生す
る。その後のページ・オーバフローも後続する
付加的なデータ・ノードの２倍化を生じうる。
丁度分割がそうであつた様に、２倍化は記憶し
たハツシングされたキイ値の次のビツトの値に
基いてページの間に於てエントリを分ける。こ
の場合、(a)インデツクス・レベルに於けるエン
トリがデータ・ノード（この寸法も指示され
る）を参照する事並びに(b)ARGに関連するデ
ータを有するデータ・ノードのページを選択す
るために、探索手順がこの寸法及び適当なビツ
トを利用する事が必要である。 (b)の故にこの寸法をlog2（ページで示したノ
ード寸法）とする事は有用である。何故なら、
これはその選択を行なう場合に用いられる
exhash（ARG）のビツトの数であるからであ
る。第２，２図はexhash（ARG）を含むノー
ドが２倍化したのちのBEHフアイルを示す。 ノードの元の寸法に関係なく、ノードの２倍
化によつてノードの各ページの内容を２倍化し
たノードの２つのページの間に於てノードの各
ページの内容が分割される。第２，１図及び第
２，２図の例に於て、ノードは１ページから２
ページになつている。新規な２倍化したノード
の２つのページにわたるページ内容の分割は丁
度大抵の拡張可能なハツシング法に於いて分割
が実行される様にして、ハツシングされたキイ
値の適当な２進値に基いて実施される。即ち、
もしもkpが元のノードのページの全てのハツ
シングされたキイ値のプレフイツクス（接頭
部）であるならば、これらの値を含む２倍化し
たノードの２つの隣接するページはkp〓“０”
がページの１つの全てのハツシングされたキイ
値のプレフイツクスであり、そしてkp〓“１”
が他方のページの全てのハツシングされたキイ
値のプレフイツクスである様になる。第２，１
図、第２，２図の例に於いて、第２，１図のデ
ータ・ノードに関してkp＝“01”〓“101”で
ある。この値はノードの各ページに関してでは
なく第２，２図のデータ・ノードに関してハツ
シングされたキイ・プレツクスとして連続す
る。第１（第０番）のページに関するハツシン
グされたキイ・プレフイツクスは“01”〓
“101”〓“０”であつて、第２（１番）のペー
ジに関するハツシングされたプレフイツクスは
“01”〓“101”〓“１”である。 ２倍化の時点に於て、元のページに関連する
全ての情報が上記の様に２つの新規なページ間
に於いて分割される。この場合、元のページの
直接的な内容のみならずもしも十分な空間があ
つたならば、元のページに於いて含まれたであ
ろうところの任意のオーバフロー情報をも含
む。即ち、典型例としてノードの２倍化によつ
てその様なオーバフロー情報が２つの新しいペ
ージ内に吸収される。 Ｃ フアイルの初期伸長 フアイルの初期伸長は、ページに於けるイン
デツクスがバツフア内に含まれうる限りに於い
て、伸長可能なハツシングのインデツクス２倍
化技法を用いて実施しうる。データ・ノード２
倍化を用いて全ての後続するフアイル伸長が処
理される。１は１ページ・インデツクスでもつ
て始まり、そのインデツクス・ページがデー
タ・ページを指す全ての所要のインデツクス・
エントリをもはや保持し得なくなるまで、“レ
コード”を挿入する。この時点に於いて、イン
デツクスは２倍になり、“０”ビツトで始まる
全てのエントリはインデツクスのページ０を介
してインデツクスされ、“１”ビツトで始まる
全てのエントリはページ１を介してインデツク
スされる。続いて、それらのインデツクス・ペ
ージの１つがオーバフローすると、拡散可能ハ
ツシングの場合の様に再びインデツクスが２倍
化される。この２倍化はページで示すインデツ
クス寸法がバツフア寸法によつて許容される最
大寸法と等しくなる場合に停止する。更にフア
イルが伸長する場合はデータ・ノード２倍化が
用いられる。 フアイル動作 Ａ 探索（サーチ） 探索方法即ち所与のキイに関連するデータを
見付け出す方法を後で示す表のSEARCHプ
ログラムによつて示す。そのプログラムを説明
する。ARGの値としてSEARCHへキイを供給
する。キイに関連するデータの主記憶装置に於
けるアドレスが、もしもARGが見出されると、
Ｄ ADRに於いてGEARCHによつて戻され
る。もしもARGが見出されるならば、変数
FOUNDがSEARCHが戻される時に真（true）
へセツトされ、さもない場合はそれが偽
（false）へセツトされる。SEARCHは次の操
作によつて開始される。 CAll SEARCH（ARG，Ｄ ADR，
FOUND） 以下はどの様にしてこのSEARCH手順がそ
の目的を達成するかの説明である。 (1) EXHASHを用いてサーチ・アーギユメン
トARGをそのハツシングした値へ変換；その
値をHKと称する。 HK：＝EXHASH（ARG） (2) Ｐをインデツクス・ページの開始２次記憶装
置アドレスとし、Ｉ SIZEをインデツクスの
ページ数で示す寸法の２を底とする対数とす
る。 (3) ARGに対するデータへ導びくインデツク
ス・エントリを見出すためのインデツクス・ペ
ージＱを計算；それはHKの先頭からＩ SIZE
で設定された数のビツトをとり、それらをＰに
加える、即ち、 Ｑ：＝Ｐ＋SUBSTR（HK，Ｏ，Ｉ SIZE）* によつて見出される。 (4) 主記憶装置に於けるページの開始アドレスを
捜出する事によつて記憶アドレスへデイスク・
アドレスＱを変換。 Ｉ ADDR＝LOCATE（Ｑ） （これは、フアイルのインデツクス・ページ
が既に主記憶装置内にあるため、２次記憶装置
からデータを読取る事を行わないでも可能であ
る。） (5) Ｉ ADDRにより指定（point）されたペー
ジに於けるHKに関するインデツクス・エント
リを捜出する。インデツクス・エントリはイン
デツクス・ページを捜出するのに用いたHKの
部分を含む必要がないので、次の操作のみが必
要である。 HK REST＝SUBSTR（HK，Ｉ SIZE，*） これはHKの先頭からＩ SIZEで指定された数
のビツトを取り除く。HK RESTに関してイ
ンデツクス・エントリを捜出する結果として得
られるのは３つの量である。 LEN…インデツクス・エントリを捜出す
るのに費やしたHK RESTのビツトの数； SIZE…インデツクス・エントリによつて
参照したデータ・ノードに於けるページ数の
２を底とするす対数； PTR…インデツクス・エントリによつて
参照されるデータ・ノードの第１（０番）の
頁のデイスク・アドレス。 よつて、CALL IFIND（HK REST，Ｉ
ADDR，SIZE，PTR）が実施される。 (6) インデツクス・エントリを識別するのに用い
たHK RESTのビツト（即ちLENで指定され
た数のビツト）の次のSIZEで指定された数の
ビツトを用いて、ARGに関するデータを捜出
すべきデータ・ページのデイスク・アドレスを
計算。 PAGE DISP＝SUBSTR（HK REST，
LEN，SIZE） 及び DATA PAGE＝PTR＋PAGE DISD (7) ２次記憶装置からメモリ内へDATA
PAGEに於て指定したデータ・ページを読取
り、DATA ADDRに於けるそのメモリ・ア
ドレスをレポート。 CALL READ（DATA PAGE，DAHA
ADDR） 注…データ・ページのオーバフローが生じる
場合を除いて、このREADのための呼出しは
２次記憶の読取が要求される唯一の個所であ
る。 (8) メモリ内へ読込まれたデータ・ページに於い
てARGを捜出。もしもARGが見出されるなら
ば、FOUNDが真（true）にセツトされ、そう
でないならば、偽（false）にセツトされる。
そのノードに関してオーバフローが存在するな
らば、OVERFLOWが真にセツトされ、そう
でないならば、偽にセツトされる。もしもオー
バフローが真ならば、Ｏ PAGEはオーバフロ
ー・ページのデイスク・アドレスへセツトされ
る。もしもARGが見出されるならば、そのデ
ータのアドレスがＤ ADR内にされる。すな
わち、 CALL DFIND（ARG，Ｄ ADR，
FOUND，OVERF LOW，Ｏ PAGE） (9) もしもARGのデータが捜出されたならば、
SEARCH手順の結果としてＤ ADDを戻し、
FOUNDを真へセツトする。すなわち、 IF FOUND THEN RETURN (10) もしもARGのデータが捜出されず、オーバ
フロー・ページもないならば、ARGのデータ
はフアイルに存在しない。SEARCH手順の結
果としてRETURN FOUNDが偽へセツトさ
れる。即ち IF NOT（OVERFLOW）THEN
RETURN (11) もしもARGは捜出されないが、ARGに関す
るデータが配置されるオーバフロー・ページが
存在するならば、ARGのデータのためのオー
バフロー・ページ（もしくは複数ページ）を探
索。 オーバフロー・ページがPAGE DISPによ
つてノード内に於て指定されるので、DAGE
DISD並びにARG及びＯ PAGEを供給しな
ければならない。予期される結果は量Ｄ
ADR及びFOUNDのための適当なセツテイン
グである。即ち、 CALL OFIND（ARG，Ｏ PAGE，PAGE
DISP，Ｄ ADR，FOUND） （OFINDは、オーバフローが普通でない状態
であるので、通常は呼出されない事に注目された
い。更に、もしもそれが呼出されるならば、それ
は通常２次記憶装置からのページの単一の読取の
みを含む。） ＊ SUBSTARはストリング・アーギユメン
ト（例えばHK）、ストリングに於けるスタ
ート位置（例えば０）及びサブストリングの
ための長さ（例えばＩ SIZE）を取る関数
手続きであつて、ストリング・アーギユメン
トの“スタート”位置ないし“スタート＋長
さ−１”からなるストリングを戻す関数手続
きである。もしも＊が長さとして与えられる
ならば、指定されたサブストリングはアーギ
ユメント・ストリングの残部を含む。 【表】 Ｂ 更新（Updating） 挿入及び削除は共に、まず指定されたエントリ
を探索し、それが存在しあるいは存在する予定の
ページを捜出する事によつて進行する。大抵の場
合、これらの更新オペレーシヨンは予期された方
法で即ち、挿入に関しては前には存在しなかつた
キイ値を有する新規なレコードを包含し、そして
削除に関しては、指定されたキイ値にマツチする
キイを有するレコードを除去する事によつてその
ページを変更する。 これらのケースに於て、オーバフロー・レコー
ドが不在である場合、両オペレーシヨン共に単一
の読取のみを要し、続いてデイスクへの更新した
ページの単一の書き戻しが行なわれる。オーバフ
ロー・レコードの存在は書込の前に第２の読取を
必要とする。もしも挿入がページの分割（split）
を必要とするならば、データ・ノードの寸法が２
倍化され、よつて２つのページにわたつてそのペ
ージの各々のエントリを散す。その様なマルチ・
ページ２倍化は、ページが隣接しているので、各
Ｉ／Ｏ動作の間に多重ページを読取り、書込む事
によつて極めて有効に行なう事ができる。 Ｃ 順次読取（ハツシング・キイ順） ハツシングはキイ順の順次サーチを支援し得な
い。しかしながら、順次アクセスが望ましく、し
かもキイ順位が重要でない場合がある。この場
合、BEHハツシングはノード内のページの連続
性に関する非常に好ましい特性を有する。これは
単一のＥ／Ｏ読取による複数のページのブロツク
の読取とその結果の緩衝記憶を可能にする。これ
らの条件の下でデイスク・アームの移動も大きく
減じられる事は云う迄もない。 オーバフローの処理 オーバフロー・エントリを収容するのにもつぱ
ら用いるページの数の適当な選択によつて、適度
なレベルにフアイル利用度（utilization）を維持
する事を保証するために、オーバフローを処理す
る具体的方法を説明する。これによつてフアイル
の良好な一定の性能が保証される。 Ａ 連続したページのオーバフロー １オーバフロー・ページはデータ・ノードの各
2nの隣接したページと関連している。数nは個定
されないが、ノードの利用度が増加するにつれて
変わる。利用度とデイスク・アクセスのパフオー
マンスの間の良好な妥協点を見出すために、非常
に小さなページ寸法を除いて、１オーバフロー・
ページ／４データ・ページよりも多数のオーバフ
ロー・ページを有する必要はない。オーバフロ
ー・ページは、長さｎのビツト・ストリングと連
結された共通プレフイツクスｘがその関連する１
次ページ（primary pages）の１つの共通接頭部
kpを生じる様に、共通接頭部ｘを有するエント
リを含む。 オーバフロー・ページが連続した１ページと関
連するという事実は同じ基本的な理由からノード
２倍化及び逐次サーチに関して重要な含意を有し
ている。これらの事例の両方に於いて、常に多数
のページをアクセスしなければならないが故に多
重ページＩ／Ｏオペレーシヨンを実施する事が可
能である。即ち、別個のＩ／Ｏオペレーシヨンの
数を大幅に減らす事ができる。しかしながら顕著
な節減を呈するには、これらのページの関連する
オーバフロー・エントリをアクセスする場合の多
数のＩ／Ｏオペレーシヨンを回避する事が必要で
ある。この編成は、2nの連続したページに対する
オーバフロー・ページをアクセスするために１つ
の付加的Ｉ／Ｏオペレーシヨンを必要とする。こ
れによつて、１次ページのためのＩ／Ｏオペレー
シヨンに於ける節減はオーバフロー・ページが含
まれた後にも真の節減となる。 Ｂ オーバフロー・ページのトリー ノードの或るページがまずオーバフローする場
合、それはそのノードに於ける指定されたページ
−−多分、もしも存在するならば最初のオーバフ
ロー・ページに対する基準をうるための第１ペー
ジ（ページ・ゼロ）−−を参照しなければならな
い。もしもその様なオーバフロー・ページが存在
しないならば、１が割付けられ、それに対するポ
インタが限在オーバフローしていないページのた
めに両方のページ・ゼロに及びオーバフローして
いるページに記憶される。この初期オーバフロ
ー・ページは、更に多数のオーバフロー・ページ
が必要とされる様に、オーバフロー・エントリの
数が増大するに従つて成長するオーバフロー・ペ
ージのトリ−の根としての働きをする。 オーバフロー・ページ自体がオーバフローする
場合は常に、ページ上のエントリがキイのビツト
に基いて現在ページ及び新規に割付けたページの
２つのページに分割される。即ち、オーバフロ
ー・ページは１次ページに於けるエントリがそう
である様に正確にデイジタルに分割される。２つ
のページの各々は元のオーバフロー・ページによ
つてサービスされた１次ページの1/2のためのオ
ーバフロー・ページとして働らく。新しいオーバ
フロー・ページに対するポインタが元のオーバフ
ロー・ページに記憶され、そしてその挿入によつ
て分割を生じた１次ページに適宜記憶される。
（新規なオーバフロー・ページを共有する他の１
次ページはそのオーバフロー・ポインタが直ちに
更新されない事に注目されたい。むしろそれはオ
ーバフロー・ページに対するアクセスを必要とす
る１次ページに対する次のアクセスに於いて行な
われる。）第３図はこのプロセスが行なわれる方
法を示す。第３図に示す様にこの成長プロセスは
Ｏトリ−と称するトリーが存在するまで連続しう
る。第３図に於いて４は暗黙２進トリ−を、５は
根（root）を、６はキイ・プレフイツクス（kp）
を有するデータ・ノードの１次ページを、７はＯ
トリー・ページを示す。 １つの１次ページが（特にページ寸法が小さい
場合に）１オーバフロー・ページよりも多いオー
バフロー・ページを有した状態で終る様に、Ｏト
リ−を十分に成長させる事が可能である。この成
長はＯトリ−構成と正確に同じ方法で進行するこ
とができる。しかしながら、１次ページ自体はそ
のオーバフロー・エントリを含む全てのページに
直接指向されるべきである。即ち、１次ページは
単に１ポインタよりはむしろそのオーバフローペ
ージの各々に対する小さいインデツクスを含む必
要がある。このインデツクスはオーバフロー・ペ
ージ・アドレスのみでなく、各々その様なページ
に於けるエントリのキイ・スペースも指示すべき
である。この情報によつてサーチのデイスク・ア
クセス・コストは２アクセスよりも大とならない
様に続けて制限できる。 他のノードの源もしくは先祖として働くＯトリ
−の各ノードもまたリーフ・ノードとして働き、
よつてＯトリー構造は不在（missing）リンクを
有する。特に、第３図に於いてＯトリーを構成し
てある様に、トリ−の左端ページへの全てのリン
クは削除されている。これによつてスペースとサ
ーチ時間の両方が節約される。 Ｃ Ｏトリーのサーチ １ページが一杯である場合、各々の連続する挿
入によつてエントリがオーバフロー・ページに配
置される事になる。オーバフロー・ページは次の
様に見出される。オーバフロー・ページに対する
ポインタはノードの第１ページへあるいは実際の
オーバフロー・ページへ指向される。もしもその
ページがノードの第１ページならば、このページ
に於けるポインタはＯトリーの根を参照する。ポ
インタに従う事によつてＯトリーの根へ達し、状
態はあたかも１次ページにおけるオーバフロー・
ポインタが最初にオーバフロー・ページをポイン
タ表示したかの様な状態と同じになる。もしもオ
ーバフロー・ページに関連する接頭部もしくはプ
レフイツクスがエントリのプレフイツクスである
ならば、そのページは１次ページに対する正確な
オーバフロー・ページであり、エントリはこのペ
ージに挿入出来る（あるいはもしもオペレーシヨ
ンがサーチであるならば、このページにおいて見
出す事が出来る）。もしもそうでないならば、そ
のページにおけるインデツクスは、エントリのた
めのオーバフロー・ページが指定されるＯトリー
における次のノードへのポインタを見出すために
アクセスしなければならない。アーギユメント・
キイにおいて１ビツトに遭隅する場合においての
み間接路（indirections）が用いられる。横断し
たリンクの数は平均してＯトリーによつて表現し
た暗黙２進トリー４（第３図）の高さの1/2であ
る。 １次ページがサーチもしくは挿入の際にそのオ
ーバフロー・ページの動いた事を見出すと常にそ
れは新しいオーバフロー・ページを参照するため
にそのオーバフロー・ページ・ポインタを更新す
る。（オーバフロー・ページはＯトリーが成長し、
そしてオーバフロー・ページが分割されるにつれ
て“移動”する。）すなわち、時々付加的オーバ
フロー・ページへのエクストラ・アクセスが生じ
る。 エクストラ・アクセスにおける不利点を減じる
事が可能である。ノード２が２倍にされる場合に
初期オーバフロー・ページ（単数もしくは複数）
を割振る事によつて、ノードの第１ページに対す
る初期参照を省く事ができる。よつて１次ページ
は、Ｏトリーの根へ直接向う様に初期設定する事
ができる。更に、Ｏトリーの高さは選択された数
（例えば６）をけつして越えない様にクリツプす
ることができる。これはわずかに１／ノードでは
なくノードの64ページ毎にオーバフロー・ページ
を割振る事によつて達成する事ができる。 ノードを２倍化する場合 Ｏトリーは増々多くのオーバフロー・エントリ
を収容する様に成長しうるダイナミツク構造であ
るので、エントリを挿入できないが故にノードを
２倍化しなければならない固定点は存在しない。
ななわち２倍化を生ぜしめる場合を定義する事が
必要である。それを実施する場合、フアイルの寸
法が既知である時には、２倍化が行なわれるべき
exhash（ARG）の領域内にある２倍化境界
（frontier）ｘを定める事ができるという事実が
用いられる。ｘの値はフアイル寸法と共に変化す
る。その結果、フアイルが成長するにつれて、ｘ
の値は異なつたデータ・ノード内に含まれる事に
なる。現にｘの値を含むノードが、２倍化される
べきノードである。もしもフアイルが収縮するな
らば、このプロセスは逆行でき、よつて表示され
たノードの1/2化が行なわれる。 ｘの値を決定するために、フアイルに含まれる
エントリ（レコード）Ｅの数のカウントを保持し
なければならない。このカウントは主記憶バツフ
アにおけるフアイルのためのインデツクスと共に
保持することができる。 次の固定量もｘの値の決定の一助となる。 (1) Ｉ：インデツクス項の数、従つてデータ・ノ
ードの数。 (2) Ｍ：データ・ページ上に含む事のできるデー
タ・エントリ（レコード）の数。もしもレコー
ドの寸法が変可ならば、これは平均値である。 (3) ｎ：exhash（key）＝“11…１”の為のインデ
ツクス・エントリ即ちインデツクスの最後のエ
ントリに関する寸法。この寸法は2nページのデ
ータ・ノードを示す。 (4) ｕ：オーバフロー・ページの存在が無視され
るならば、フアイル利用度。これは所望された
利用度である。オーバフローの無視によつて生
じたエラーはｕから75ないし80％の値に関して
は非常に小さい。 単純な下記計算によつて、どのノードを２倍化
すべきかを指示する値ｘを計算することができ
る。 ｘ＝Ｅ／I*2n*M*ｕ−１ ｘの値は、 ΔE＝2n*M*ｕエントリ の挿入後即ち１つの付加的データ・ノードを滴す
ための十分なデータの挿入後にノード境界を横切
るであろう。ΔEの値は、最後のインデツクス・
エントリのデータ・ノード寸法が2nページから
2n+1ページへ増加したのちに２倍化する。この時
点に於いて、ｘの値は“11…１”から“０…０”
へと、即ち最後のインデツクス・エントリの参照
から第１のインデツクス・エントリの参照へと変
化する。 ノードを２倍化するための信号はそのＯトリー
の状態態によつて与えられず、フアイルの特性即
ちｘの値によつて与えられる。 デイスク記憶管理 BEHフアイルのためのインデツクス・レベル
を有するための２つの理由がある。第１の理由は
フアイルのノードを非直接記憶装置内に於いてマ
ツピングされる事を可能にし、データを記憶する
ためにスペースが必要とされる前にフアイルへデ
イスクの大きなブロツクを予じめ割振りする事に
よつて生じる記憶装置の利用度に関する不利点を
回避するためである。第２の理由は、ノード２倍
化（もしくはノード1/2化）の間に、あるいは順
次読取のために、多重ページ読取及び書込を可能
にし、よつてこれらのオペレーシヨンのパホーマ
ンスを改良するためである。 BEH編成フアイルはノード２倍化によつて成
長するので（あるいはノード1/2化によつて収縮
するので、）それらのフアイルは下記の文献に示
される“buddy”法と称せられる記憶管理技法か
ら導かれる方法によつて管理される。 D.Knuth著The Art of Computer
Programming Vol.1，Fundamental
Algorithms，Addison Weslqy，（1977）。 “buddy”割振り法は単位が２のｎ乗の寸法で
ある記憶装置のブロツクに対して機能する。各々
の異つた寸法のブロツクのために別個の自由リス
トが維持される。もしもあるブロツク寸法が要求
され、その寸法のブロツクが無いならば、所望寸
法のブロツクを提供するためにより大きなブロツ
クが分割される（必要ならその分割片が再び分割
片が再び分割される）。ブロツクが自由になると、
より大きなブロツクを作るために自由になつたブ
ロツクがよれと合体できるかについての決定を行
うためにブロツクの“buddy”を調べなければな
らない。任意の合体したブロツクは更に合体する
ための候補でもある。このプロセスの故に、その
方法にその様な名が付けられた。 自由な状態のブロツクに対する“buddy”はア
ドレスが下記の様にして決定される自由ブロツク
と同寸法のブロツクである。もしも各デイスク・
アドレスがｌビツト長で、自由ブロツクが2k単
位の記憶（ページ）を有するならば、“buddy”
は自由ブロツクと共通のプレフイツクス（その長
さはｌ−ｋ−１）を共有するであろう。この共通
プレフイツクスに続く“buddy”に於けるビツト
は自由ブロツクに於ける対応するビツトの補数で
ある。もしも合体が生じると、結果物は寸法が
2k+1の自由ブロツクである。 BEFフアイルに於いて、全てのノードは２の
ｎ乗のページ数を有する。よつてブロツク内では
スペースの無駄がない。更に、フアイルの成長
（もしくは収縮）は前のブロツクの寸法を２倍化
（もしくは1/2化）する、あるブロツク寸法から他
のブロツク寸法への漸次変化を要求する様に行な
われる。ブロツク寸法を変える動作はｘの値で指
示された境界（frontier）において生じる。この
領域におけるブロツクは、所定寸法のブロツクの
各自由リスト上のいくつかのブロツクが大きくな
る事なく、フアイル成長の際に容易に合体され
る。フアイルの収縮に於いては、ブロツクの分割
は長さの短いこれらのリストを保存する。 主メモリの場合と異なり、デイスク記憶を管理
する場合は、“buddy”それ自体が自由か、そし
て丁度自由になつたブロツクと合体できるかを見
るために“buddy”それ自体に指向する事を避け
たい。もしもそれが行なわれると、それは各々の
自由なオペレーシヨンのためにエクストラなデイ
スク・アクセスを要求するであろう。この理由か
ら、その方法によつて要求された全てのブツクキ
ーピング操作は管理される記憶装置から完全に分
離され、よつてそれは主メモリ内に保持すること
ができる。利用可能なブロツクの各寸法のための
短い自由リストの故に、適当な寸法ブロツクを有
する自由リストを単にサーチすることによつて
“buddy”を容易に見出す事ができる。もしもこ
れらのリストが非常に短いならば、順次サーチが
適当である。もしもリストが幾分長いならば、
“buddy”を見付けるのに２進デイジタル・トリ
ー（trie）を用いる事ができる。いずれの場合に
於ても、必要とされる技法は複雑ではない。
【図面の簡単な説明】
第１図は主メモリに於けるインデツクス・レベ
ルの配置及び２次メモリに於けるデータ・ノー
ド・レベルの配置を示す図である。第２，１図及
び第２，２図は夫々、データ・ノード２倍化の前
及び後のフアイルの構成を示す図である。第３図
はオーバフロー・ページの関連するトリー（Ｏト
リー）と共にデータ・ノードの構成を示すブロツ
ク図である。 １…コンピユータ・メモリ、２…デイスク・メ
モリ、３…データ・ノード、４…暗黙２進トリ
ー、５…根、６…１次ページ、７…Ｏトリー・ペ
ージ。

Claims (1)

  1. 【特許請求の範囲】 １ 主記憶装置及び２次記憶装置を有するコンピ
    ユータ・システムにおいてキイによつて識別され
    る複数のデータを含むキイ・アクセス型フアイル
    を管理する方法であつて、 キイのハツシング値に従つて配列されたデータ
    を含む所定数のページをそれぞれ有する複数のノ
    ードから成るデータ・レベルを上記２次記憶装置
    に記憶し、 フアイルの使用時に、上記複数のノードのそれ
    ぞれに対応して、上記２次記憶装置における対応
    するノードの開始アドレスと該ノードに属するペ
    ージの数を反映する寸法情報とをそれぞれ含む複
    数のインデツクス・エントリから成り、主記憶装
    置に納まるように寸法が制限されたインデツク
    ス・レベルを上記主記憶装置に記憶し、 フアイルの寸法の変化につれて、上記データ・
    レベルにおける任意のノードに属する上記所定数
    のページの容量限度を越えて該ノードにデータを
    挿入する必要があるときには、該ノードに属する
    ページの数を上記所定数の２倍にするように追加
    のページを該ノードに割当てることによつて、該
    ノードを拡張し、且つ該拡張に応じて該ノードに
    対応するインデツクス・エントリの寸法情報を変
    更する ことを特徴とするキイ・アクセス型フアイル管理
    方法。 ２ 上記ノードに属するページの数が２のｎ乗で
    あり（ｎは整数）、且つ各インデツクス・エント
    リに含まれている寸法情報が対応するノードに関
    するｎを示すことを特徴とする特許請求の範囲第
    １項記載のキイ・アクセス型フアイル管理方法。 ３ 更に、上記キイを用いて所望のデータを探索
    するステツプを有し、該ステツプが、 上記キイのハツシング値の先頭の所定のビツト
    をアドレスとして用いて上記インデツクス・レベ
    ルにおける１つのインデツクス・エントリを選択
    し、 該インデツクス・エントリに含まれている寸法
    情報によつて示される数をｎとして、上記キイの
    ハツシング値の上記所定のビツトの次のｎ個のビ
    ツトを該インデツクス・エントリに含まれている
    開始アドレスに加えて、該インデツクス・エント
    リに対応するノードにおける所望のデータを含む
    ページのアドレスを生成する ことを含む特許請求の範囲第２項記載のキイ・ア
    クセス型フアイル管理方法。
JP58238027A 1983-02-03 1983-12-19 キイ・アクセス型ファイル管理方法 Granted JPS59146356A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US06/463,469 US4611272A (en) 1983-02-03 1983-02-03 Key-accessed file organization
US463469 2003-06-17

Publications (2)

Publication Number Publication Date
JPS59146356A JPS59146356A (ja) 1984-08-22
JPH0432420B2 true JPH0432420B2 (ja) 1992-05-29

Family

ID=23840200

Family Applications (1)

Application Number Title Priority Date Filing Date
JP58238027A Granted JPS59146356A (ja) 1983-02-03 1983-12-19 キイ・アクセス型ファイル管理方法

Country Status (2)

Country Link
US (1) US4611272A (ja)
JP (1) JPS59146356A (ja)

Families Citing this family (79)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3577938D1 (de) * 1984-09-12 1990-06-28 Bbc Brown Boveri & Cie Suchverfahren fuer speicheradressen und adressvergleichsschaltung.
JPS61245256A (ja) * 1985-04-23 1986-10-31 Mitsubishi Electric Corp 情報格納方式
US5047918A (en) * 1985-12-31 1991-09-10 Tektronix, Inc. File management system
US4763244A (en) * 1986-01-15 1988-08-09 Motorola, Inc. Paged memory management unit capable of selectively supporting multiple address spaces
US5265244A (en) * 1986-02-14 1993-11-23 International Business Machines Corporation Method and system for facilitating processing of statistical inquires on stored data accessible through a data access structure
US4774657A (en) * 1986-06-06 1988-09-27 International Business Machines Corporation Index key range estimator
DE3636426A1 (de) * 1986-10-25 1988-05-05 Standard Elektrik Lorenz Ag Verfahren zur eingabe von stellbefehlen in ein rechnergesteuertes stellwerk
US4945475A (en) * 1986-10-30 1990-07-31 Apple Computer, Inc. Hierarchical file system to provide cataloging and retrieval of data
US4827462A (en) * 1987-03-26 1989-05-02 International Business Machines Corporation Modular data storage directories for large-capacity data storage units
US5119291A (en) * 1987-03-26 1992-06-02 International Business Machines Corporation Modular data storage directories for large-capacity data storage units wherein the index to the records in a sector is located in the next adjacent sector
US5058002A (en) * 1987-06-23 1991-10-15 Mitsubishi Denki Kabushiki Kaisha Page splitting method and apparatus for a database stored in a plurality of memory storage units
US5307494A (en) * 1987-08-05 1994-04-26 Fuji Xerox Co., Ltd. File name length augmentation method
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
US4989132A (en) * 1988-10-24 1991-01-29 Eastman Kodak Company Object-oriented, logic, and database programming tool with garbage collection
JPH02130647A (ja) * 1988-11-11 1990-05-18 Toshiba Corp 索引木構造の更新方式
US5218696A (en) * 1989-07-24 1993-06-08 International Business Machines Corporation Method for dynamically expanding and rapidly accessing file directories
US5339398A (en) * 1989-07-31 1994-08-16 North American Philips Corporation Memory architecture and method of data organization optimized for hashing
US5202986A (en) * 1989-09-28 1993-04-13 Bull Hn Information Systems Inc. Prefix search tree partial key branching
US5257365A (en) * 1990-03-16 1993-10-26 Powers Frederick A Database system with multi-dimensional summary search tree nodes for reducing the necessity to access records
US5095423A (en) * 1990-03-27 1992-03-10 Sun Microsystems, Inc. Locking mechanism for the prevention of race conditions
US5261088A (en) * 1990-04-26 1993-11-09 International Business Machines Corporation Managing locality in space reuse in a shadow written B-tree via interior node free space list
JPH0490054A (ja) * 1990-08-03 1992-03-24 Toshiba Corp 画像記憶検索装置
EP0483424A1 (en) * 1990-10-30 1992-05-06 International Business Machines Corporation Key hashing in data processors
US5293595A (en) * 1990-12-17 1994-03-08 Unisys Corporation Paging system using extension tables for conflict resolution
US5339411A (en) * 1990-12-21 1994-08-16 Pitney Bowes Inc. Method for managing allocation of memory space
US5764877A (en) * 1991-06-25 1998-06-09 Digital Equipment Corporation Media recovery with time-split B-trees
US5204958A (en) * 1991-06-27 1993-04-20 Digital Equipment Corporation System and method for efficiently indexing and storing a large database with high data insertion frequency
US5519858A (en) * 1992-01-10 1996-05-21 Digital Equipment Corporation Address recognition engine with look-up database for storing network information
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
US5613105A (en) * 1993-06-30 1997-03-18 Microsoft Corporation Efficient storage of objects in a file system
JP3234075B2 (ja) * 1993-11-30 2001-12-04 ローム株式会社 立体映像再生装置
US5680566A (en) * 1995-03-03 1997-10-21 Hal Computer Systems, Inc. Lookaside buffer for inputting multiple address translations in a computer system
JP3549608B2 (ja) * 1995-04-04 2004-08-04 富士通株式会社 識別子による階層構造データの構造判定方法および装置
US6427147B1 (en) 1995-12-01 2002-07-30 Sand Technology Systems International Deletion of ordered sets of keys in a compact O-complete tree
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
US5806065A (en) * 1996-05-06 1998-09-08 Microsoft Corporation Data system with distributed tree indexes and method for maintaining the indexes
US5919247A (en) 1996-07-24 1999-07-06 Marimba, Inc. Method for the distribution of code and data updates
SE513248C2 (sv) * 1997-12-19 2000-08-07 Ericsson Telefon Ab L M Metod för hantering av datastrukturer
US6675173B1 (en) * 1998-01-22 2004-01-06 Ori Software Development Ltd. Database apparatus
KR100285265B1 (ko) * 1998-02-25 2001-04-02 윤덕용 데이터 베이스 관리 시스템과 정보 검색의 밀결합을 위하여 서브 인덱스와 대용량 객체를 이용한 역 인덱스 저장 구조
GB9811574D0 (en) * 1998-05-30 1998-07-29 Ibm Indexed file system and a method and a mechanism for accessing data records from such a system
US6105032A (en) * 1998-06-05 2000-08-15 Ip-First, L.L.C. Method for improved bit scan by locating a set bit within a nonzero data entity
IL126472A0 (en) * 1998-10-07 1999-08-17 Nds Ltd Secure communications system
US6189036B1 (en) 1998-11-05 2001-02-13 International Business Machines Corporation User access to objects in group based access control based on result of greatest common divisor of assigned unique prime numbers of user and object
JP2001352321A (ja) 2000-04-06 2001-12-21 Sony Corp 情報処理システム、情報処理方法、および情報記録媒体、並びにプログラム提供媒体
EP1207707B1 (en) * 2000-11-17 2008-08-13 Sony Deutschland GmbH Transmission of carry-on objects using a wireless ad-hoc networking environment
US6804677B2 (en) * 2001-02-26 2004-10-12 Ori Software Development Ltd. Encoding semi-structured data for efficient search and browsing
JP2002319932A (ja) * 2001-04-19 2002-10-31 Sony Corp 情報記録装置、情報再生装置、および情報記録方法、情報再生方法、並びにプログラム
US7054872B1 (en) * 2001-05-29 2006-05-30 Oracle International Corporation Online tracking and fixing of invalid guess-DBAs in secondary indexes and mapping tables on primary B+tree structures
US7246102B2 (en) * 2001-12-21 2007-07-17 Agere Systems Inc. Method of improving the lookup performance of three-type knowledge base searches
US7287033B2 (en) 2002-03-06 2007-10-23 Ori Software Development, Ltd. Efficient traversals over hierarchical data and indexing semistructured data
US7058642B2 (en) * 2002-03-20 2006-06-06 Intel Corporation Method and data structure for a low memory overhead database
US7533245B2 (en) 2003-08-01 2009-05-12 Illinois Institute Of Technology Hardware assisted pruned inverted index component
JP4444677B2 (ja) * 2004-01-20 2010-03-31 クラリオン株式会社 検索データの更新方法および更新システム
US8595214B1 (en) * 2004-03-31 2013-11-26 Google Inc. Systems and methods for article location and retrieval
US8583657B2 (en) * 2004-05-06 2013-11-12 Oracle International Corporation Method and apparatus for using a hash-partitioned index to access a table that is not partitioned or partitioned independently of the hash partitioned index
US20060198312A1 (en) * 2005-02-01 2006-09-07 Schondelmayer Adam H Network diagnostic systems and methods for altering the format and bandwidth of network messages
US20060200711A1 (en) * 2005-02-01 2006-09-07 Schondelmayer Adam H Network diagnostic systems and methods for processing network messages
US20060198319A1 (en) * 2005-02-01 2006-09-07 Schondelmayer Adam H Network diagnostic systems and methods for aggregated links
US20060198318A1 (en) * 2005-02-01 2006-09-07 Schondelmayer Adam H Network diagnostic systems and methods for statistical triggering
US8107822B2 (en) 2005-05-20 2012-01-31 Finisar Corporation Protocols for out-of-band communication
US20080075103A1 (en) * 2005-05-20 2008-03-27 Finisar Corporation Diagnostic device
US20070211697A1 (en) * 2006-03-13 2007-09-13 Finisar Corporation Method of analyzing network with generated traffic
US20060264178A1 (en) * 2005-05-20 2006-11-23 Noble Gayle L Wireless diagnostic systems
US20070038880A1 (en) * 2005-08-15 2007-02-15 Noble Gayle L Network diagnostic systems and methods for accessing storage devices
US7899057B2 (en) * 2006-04-28 2011-03-01 Jds Uniphase Corporation Systems for ordering network packets
US8213333B2 (en) 2006-07-12 2012-07-03 Chip Greel Identifying and resolving problems in wireless device configurations
US20080097954A1 (en) * 2006-10-20 2008-04-24 Microsoft Corporation Ranged lookups
US8526821B2 (en) * 2006-12-29 2013-09-03 Finisar Corporation Transceivers for testing networks and adapting to device changes
US20100082636A1 (en) * 2008-09-25 2010-04-01 Nec Laboratories America, Inc. Methods and Apparatus for Content-Defined Node Splitting
US8190655B2 (en) * 2009-07-02 2012-05-29 Quantum Corporation Method for reliable and efficient filesystem metadata conversion
JP5439236B2 (ja) * 2010-03-12 2014-03-12 株式会社日立製作所 計算機システムおよびアプリケーションプログラムの実行方法
US10558705B2 (en) 2010-10-20 2020-02-11 Microsoft Technology Licensing, Llc Low RAM space, high-throughput persistent key-value store using secondary memory
US8396858B2 (en) 2011-08-11 2013-03-12 International Business Machines Corporation Adding entries to an index based on use of the index
US9442840B2 (en) 2012-12-19 2016-09-13 Qualcomm Incorporated Virtual boundary codes in a data image of a read-write memory device
US20140173187A1 (en) * 2012-12-19 2014-06-19 Qualcomm Incorporated Virtual boundary codes in a data image of a read-write memory device
WO2016048263A1 (en) 2014-09-22 2016-03-31 Hewlett Packard Enterprise Development Lp Identification of content-defined chunk boundaries

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3681781A (en) * 1970-09-04 1972-08-01 Goodyear Aerospace Corp Storing and retrieval method
US4096567A (en) * 1976-08-13 1978-06-20 Millard William H Information storage facility with multiple level processors
US4257097A (en) * 1978-12-11 1981-03-17 Bell Telephone Laboratories, Incorporated Multiprocessor system with demand assignable program paging stores
US4325120A (en) * 1978-12-21 1982-04-13 Intel Corporation Data processing system
US4240143A (en) * 1978-12-22 1980-12-16 Burroughs Corporation Hierarchical multi-processor network for memory sharing
US4290105A (en) * 1979-04-02 1981-09-15 American Newspaper Publishers Association Method and apparatus for testing membership in a set through hash coding with allowable errors
US4295124A (en) * 1979-08-13 1981-10-13 National Semiconductor Corporation Communication method and system
US4468728A (en) * 1981-06-25 1984-08-28 At&T Bell Laboratories Data structure and search method for a data base management system

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
ACM TRANS.DATABASE SYST=1979 *
AN INTRODUCTION TO DATABASE SYSTEMS THIRD EDITION=1981 *

Also Published As

Publication number Publication date
JPS59146356A (ja) 1984-08-22
US4611272A (en) 1986-09-09

Similar Documents

Publication Publication Date Title
JPH0432420B2 (ja)
CN111221776B (zh) 面向非易失性内存的文件系统的实现方法、系统及介质
US7287131B1 (en) Method and apparatus for implementing a fully dynamic lock-free hash table
KR940005775B1 (ko) 디스크 파일 개방 방법
US8521790B2 (en) Increasing efficiency of data storage in a file system
US6654772B1 (en) Multi-volume extent based file system
US6349308B1 (en) Inverted index storage structure using subindexes and large objects for tight coupling of information retrieval with database management systems
US5991862A (en) Modified indirect addressing for file system
US6895418B1 (en) Versatile indirection in an extent based file system
US6473774B1 (en) Method and apparatus for record addressing in partitioned files
US12430291B2 (en) Directory management method and system for file system based on Cuckoo hash and storage medium
US7702628B1 (en) Implementing a fully dynamic lock-free hash table without dummy nodes
US6697795B2 (en) Virtual file system for dynamically-generated web pages
US11886401B2 (en) Database key compression
US7370054B1 (en) Method and apparatus for indexing a hash table which is organized as a linked list
US20140324875A1 (en) Index for fast batch updates of large data tables
JPH1131096A (ja) データ格納検索方式
Lomet Bounded index exponential hashing
US20020124133A1 (en) Method and system for optimizing data storage and retrieval by an audio/video file system using hierarchical file allocation table
CN114238226B (zh) 一种基于simd指令的nvm本地文件管理系统及方法
US8156126B2 (en) Method for the allocation of data on physical media by a file system that eliminates duplicate data
CN108804571B (zh) 一种数据存储方法、装置以及设备
EP0117906B1 (en) Key-accessed file organization
KR20190089420A (ko) 서브 인덱스 저장 방식의 데이터 구축 및 관리 시스템
Zobel et al. Storage Management for Files of Dynamic Records.